稀疏网格

稀疏网格是表示、积分或插值高维函数的数值计算技术。最初是由俄罗斯数学家Sergey A. Smolyak （Lazar Lyusternik的学生）基于稀疏张量积构造发展。高效实现此类网格的计算机算法后来由Michael Griebel和Christoph Zenger 开发。

维度诅咒

表示多维函数的标准方式是采用张量或完全网格。故用于存储、运算的基函数或节点的数量与维数指数增加。即使以今天的计算能力，也不可能处理超过 4 或 5 维的函数。

维度诅咒可以表示为使用$N_{l}$个格点进行$l$阶积分积分误差。若函数的正则性为$r$，即$r$次可微，维数为$d$，则

$|E_{l}|=O(N_{l}^{-{\frac {r}{d}}})$

Smolyak求积法则

Smolyak 发现了基于单变量求积规则$Q^{(1)}$的计算上更为高效的多维函数积分方法。对$d$维函数$f$，Smolyak积分$Q^{(d)}$一个函数的可以写成具有张量积的递归公式：

$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$

$Q$的下标是离散化的水平。$i$阶的$(1-d)$维积分要对$O(2^{i})$个点求值。正则性为$r$的函数的误差估计是：

$|E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)$

延伸阅读

• Brumm, J.; Scheidegger, S. Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models. Econometrica. 2017, 85 (5): 1575–1612. doi:10.3982/ECTA12216. 
• Garcke, Jochen. https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf (PDF). Garcke, Jochen; Griebel, Michael (编). Sparse Grids and Applications. Springer. 2012: 57–80. ISBN 978-3-642-31702-6. 
• Zenger, Christoph. https://www5.in.tum.de/pub/zenger91sg.pdf (PDF). Hackbusch, Wolfgang (编). Parallel Algorithms for Partial Differential Equations. Vieweg. 1991: 241–251. ISBN 3-528-07631-3. 

外部链接

• 一种用于常规稀疏网格的高效内存数据结构
• 稀疏网格上的有限差分格式
• 稀疏网格上的可视化
• 稀疏网格上的数据挖掘，J.Garcke、M.Griebel (pdf)