Sparse grid

<h2 id="curse-of-dimensionality">Curse of dimensionality</h2>
<p>The standard way of representing multidimensional functions are tensor or full grids. The number of basis functions or nodes (grid points) that have to be stored and processed <a href="/facts/Exponential_function/ewlYxvR2">depend exponentially</a> on the number of dimensions.
</p><p>The <a href="/facts/Curse_of_dimensionality/dk7SnY6L">curse of dimensionality</a> is expressed in the order of the integration error that is made by a quadrature of level 
  
    
      
        l
      
    
    {\displaystyle l}
  
, with 
  
    
      
        
          N
          
            l
          
        
      
    
    {\displaystyle N_{l}}
  
 points. The function has regularity 
  
    
      
        r
      
    
    {\displaystyle r}
  
, i.e. is 
  
    
      
        r
      
    
    {\displaystyle r}
  
 times differentiable. The number of dimensions is 
  
    
      
        d
      
    
    {\displaystyle d}
  
.
</p><p>
  
    
      
        
          |
        
        
          E
          
            l
          
        
        
          |
        
        =
        O
        (
        
          N
          
            l
          
          
            −
            
              
                r
                d
              
            
          
        
        )
      
    
    {\displaystyle |E_{l}|=O(N_{l}^{-{\frac {r}{d}}})}

</p>
<h2 id="smolyaks-quadrature-rule">Smolyak's quadrature rule</h2>
<p>Smolyak found a computationally more efficient method of integrating multidimensional functions based on a <a href="/facts/Univariate/PYwC7u5H">univariate</a> quadrature rule 
  
    
      
        
          Q
          
            (
            1
            )
          
        
      
    
    {\displaystyle Q^{(1)}}
  
. The 
  
    
      
        d
      
    
    {\displaystyle d}
  
-dimensional Smolyak integral 
  
    
      
        
          Q
          
            (
            d
            )
          
        
      
    
    {\displaystyle Q^{(d)}}
  
 of a function 
  
    
      
        f
      
    
    {\displaystyle f}
  
 can be written as a recursion formula with the <a href="/facts/Tensor_product/7K3pR1ap">tensor product</a>.
</p><p>
  
    
      
        
          Q
          
            l
          
          
            (
            d
            )
          
        
        f
        =
        
          (
          
            
              ∑
              
                i
                =
                1
              
              
                l
              
            
            
              (
              
                
                  Q
                  
                    i
                  
                  
                    (
                    1
                    )
                  
                
                −
                
                  Q
                  
                    i
                    −
                    1
                  
                  
                    (
                    1
                    )
                  
                
              
              )
            
            ⊗
            
              Q
              
                l
                −
                i
                +
                1
              
              
                (
                d
                −
                1
                )
              
            
          
          )
        
        f
      
    
    {\displaystyle Q_{l}^{(d)}f=\left(\sum _{i=1}^{l}\left(Q_{i}^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f}

</p><p>The index to 
  
    
      
        Q
      
    
    {\displaystyle Q}
  
 is the level of the <a href="/facts/Discretization/JvjSzwyk">discretization</a>. If a 1-dimension integration on level 
  
    
      
        i
      
    
    {\displaystyle i}
  
 is computed by the evaluation of 
  
    
      
        O
        (
        
          2
          
            i
          
        
        )
      
    
    {\displaystyle O(2^{i})}
  
 points, the error estimate for a function of regularity 
  
    
      
        r
      
    
    {\displaystyle r}
  
 will be

|
        
        
          E
          
            l
          
        
        
          |
        
        =
        O
        
          (
          
            
              N
              
                l
              
              
                −
                r
              
            
            
              
                (
                
                  log
                  ⁡
                  
                    N
                    
                      l
                    
                  
                
                )
              
              
                (
                d
                −
                1
                )
                (
                r
                +
                1
                )
              
            
          
          )
        
      
    
    {\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}

</p>
<h2 id="further-reading">Further reading</h2>
<ul><li>Pflüger, D.; Peherstorfer, B.; Bungartz, H. (2010). <a href="https://www.zora.uzh.ch/id/eprint/142226/1/Scheidegger_Econometrica%24ECTA12216.pdf">"Spatially adaptive sparse grids for high-dimensional data-driven problems"</a> (PDF). <i>Journal of Complexity</i>. 26 (5): 508–522. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jco.2010.04.001">10.1016/j.jco.2010.04.001</a>.</li>
<li>Brumm, J.; Scheidegger, S. (2017). <a href="https://www.zora.uzh.ch/id/eprint/142226/1/Scheidegger_Econometrica%24ECTA12216.pdf">"Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models"</a> (PDF). <i><a href="/facts/Econometrica/QxLdpqCG">Econometrica</a></i>. 85 (5): 1575–1612. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.3982%2FECTA12216">10.3982/ECTA12216</a>.</li>
<li>Garcke, Jochen (2012). <a href="https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf">"Sparse Grids in a Nutshell"</a> (PDF). In Garcke, Jochen; <a href="/facts/Michael_Griebel/3zLxXEFX">Griebel, Michael</a> (eds.). <i>Sparse Grids and Applications</i>. Springer. pp. 57–80. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-31702-6.</li>
<li>Zenger, Christoph (1991). <a href="https://www5.in.tum.de/pub/zenger91sg.pdf">"Sparse Grids"</a> (PDF). In Hackbusch, Wolfgang (ed.). <i>Parallel Algorithms for Partial Differential Equations</i>. Vieweg. pp. 241–251. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-528-07631-3.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.lrr.in.tum.de/~murarasu/ppopp027s-murarasu.pdf">A memory efficient data structure for regular sparse grids</a></li>
<li><a href="http://wissrech.iam.uni-bonn.de/research/projects/zumbusch/fd.html">Finite difference scheme on sparse grids</a></li>
<li><a href="https://web.archive.org/web/20120219044130/http://cumbia.informatik.uni-stuttgart.de/ger/research/fields/recent/sparse/">Visualization on sparse grids</a></li>
<li><a href="http://wissrech.iam.uni-bonn.de/research/pub/garcke/kdd.pdf">Datamining on sparse grids,  J.Garcke, M.Griebel (pdf)</a></li></ul>

Sparse grid open-in-new

Sparse grid