Fast calculation of coefficients in the Smolyak algorithm (Q5934369)

For the approximate evaluation of linear functionals (e.g.\ integrals) of a smooth multivariate function \(f\) on the \(d\)-cube, the algorithm of \textit{S. A. Smolyak} [Dokl. Akad. Nauk SSSR 148, 1042-1045 (1963; Zbl 0202.39901)] requires to evaluate a linear combination of function values. The evaluation of the coefficients may largely influence the cost of the algorithm. A divide and conquer strategy and an exploitation of the tensor product character of the problem can reduce this cost and make it small compared to \(dn\) (with \(n\) the number of function evaluations). This is illustrated for numerical integration.