View source for Smolyak algorithm

''Boolean method, discrete blending method, hyperbolic cross points method, sparse grid method, fully symmetric quadrature formulas''

Many high-dimensional problems are difficult to solve, cf. also [[Optimization of computational algorithms|Optimization of computational algorithms]]; [[Index transform|Information-based complexity]]; [[Curse of dimension|Curse of dimension]]. High-dimensional linear tensor product problems can be solved efficiently by the Smolyak algorithm, which provides a general principle to construct good approximations for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201601.png" />-dimensional case from approximations for the univariate case. The Smolyak algorithm is often optimal or almost optimal if approximations for the univariate case are properly chosen.

The original paper of S.A. Smolyak was published in 1963 [[#References|[a6]]]. There exist many variants of the basic algorithm for specific problems, see [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]]. For a thorough analysis with explicit error bounds see [[#References|[a8]]], for major modifications see [[#References|[a9]]]. The basic idea is here explained using the examples of multivariate integration and approximation. Assume one wishes to approximate, for smooth functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201602.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201603.png" /></td> </tr></table>

using finitely many function values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201604.png" />. Multivariate integration (the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201605.png" />) is needed in many areas even for very large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201606.png" />, and often a [[Monte-Carlo method|Monte-Carlo method]] or number-theoretic method (based on low-discrepancy sequences, see [[Discrepancy|Discrepancy]]) are used. Multivariate approximation (the second <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201607.png" />) is often part of the solution of operator equations using the [[Galerkin method|Galerkin method]], see [[#References|[a2]]], [[#References|[a4]]], [[#References|[a10]]].

For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201608.png" />, much is known about good quadrature or interpolation formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s1201609.png" /></td> </tr></table>

(Cf. also [[Quadrature formula|Quadrature formula]]; [[Interpolation formula|Interpolation formula]].) Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016010.png" /> for quadrature formulas and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016011.png" /> for approximation formulas. It is assumed that a sequence of such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016012.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016013.png" /> is given. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016014.png" />-functions the optimal order is

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016016.png" /> is a [[Norm|norm]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016017.png" />, as in (a2). The error <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016018.png" /> is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016020.png" />, respectively. In the multivariate case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016021.png" />, one first defines tensor product formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016022.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016023.png" /></td> </tr></table>

which serve as building blocks for the Smolyak algorithm. Then the Smolyak algorithm can be written as

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016024.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016025.png" /></td> </tr></table>

To compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016026.png" />, one only needs to know function values at the  "sparse grid" 

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016027.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016028.png" /> denotes the set of points used by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016029.png" />. For the tensor product norm

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016030.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

the error bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>

follows from (a1), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016032.png" /> is the number of points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016033.png" />. This is the basic result of [[#References|[a6]]]; see [[#References|[a8]]], [[#References|[a9]]] for much more explicit error bounds. The error bound (a3) should be compared with the optimal order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120160/s12016034.png" /> of tensor product formulas.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.-J. Delvos,   W. Schempp,   "Boolean methods in interpolation and approximation" , ''Pitman Res. Notes Math.'' , '''230''' , Longman  (1989)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  K. Frank,   S. Heinrich,   S. Pereverzev,   "Information complexity of multivariate Fredholm integral equations in Sobolev classes"  ''J. Complexity'' , '''12'''  (1996)  pp. 17–34</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.C. Genz,   "Fully symmetric interpolatory rules for multiple integrals"  ''SIAM J. Numer. Anal.'' , '''23'''  (1986)  pp. 1273–1283</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Griebel,   M. Schneider,   Ch. Zenger,   "A combination technique for the solution of sparse grid problems"  R. Beauwens (ed.)  P. de Groen (ed.) , ''Iterative Methods in Linear Algebra'' , Elsevier&amp; North-Holland  (1992)  pp. 263–281</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E. Novak,   K. Ritter,   "High dimensional integration of smooth functions over cubes"  ''Numer. Math.'' , '''75'''  (1996)  pp. 79–97</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  S.A. Smolyak,   "Quadrature and interpolation formulas for tensor products of certain classes of functions"  ''Soviet Math. Dokl.'' , '''4'''  (1963)  pp. 240–243</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  V.N. Temlyakov,   "Approximation of periodic functions" , Nova Science  (1994)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  G.W. Wasilkowski,   H. Woźniakowski,   "Explicit cost bounds of algorithms for multivariate tensor product problems"  ''J. Complexity'' , '''11'''  (1995)  pp. 1–56</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  G.W. Wasilkowski,   H. Woźniakowski,   "Weighted tensor-product algorithms for linear multivariate problems"  ''Preprint''  (1998)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A.G. Werschulz,   "The complexity of the Poisson problem for spaces of bounded mixed derivatives"  J. Renegar (ed.)  M. Shub (ed.)  S. Smale (ed.) , ''The Mathematics of Numerical Analysis'' , ''Lect. Appl. Math.'' , '''32''' , Amer. Math. Soc.  (1996)  pp. 895–914</TD></TR></table>