稀疏網格

稀疏網格是表示、積分或插值高維函數的數值計算技術。最初是由俄羅斯數學家Sergey A. Smolyak （Lazar Lyusternik的學生）基於稀疏張量積構造發展。高效實現此類網格的計算機算法後來由Michael Griebel和Christoph Zenger 開發。

維度詛咒

表示多維函數的標準方式是採用張量或完全網格。故用於存儲、運算的基函數或節點的數量與維數指數增加。即使以今天的計算能力，也不可能處理超過 4 或 5 維的函數。^{[來源請求]}

維度詛咒可以表示為使用${\displaystyle N_{l}}$個格點進行${\displaystyle l}$階積分積分誤差。若函數的正則性為${\displaystyle r}$，即${\displaystyle r}$次可微，維數為${\displaystyle d}$，則

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

Smolyak求積法則

Smolyak 發現了基於單變量求積規則${\displaystyle Q^{(1)}}$的計算上更為高效的多維函數積分方法。對${\displaystyle d}$維函數${\displaystyle f}$，Smolyak積分${\displaystyle Q^{(d)}}$一個函數的可以寫成具有張量積的遞歸公式：

${\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}$

${\displaystyle Q}$的下標是離散化的水平，我們不妨令一維${\displaystyle i}$階的積分要對${\displaystyle O(2^{i})}$個點求值。^[1]正則性為${\displaystyle r}$的函數的誤差估計是：

${\displaystyle |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. Garcke, Jochen; Griebel, Michael , 編. Sparse Grids and Applications (PDF). Springer. 2012: 57–80 [2022-01-07]. ISBN 978-3-642-31702-6. （原始內容 (PDF)存檔於2022-01-07）.
• Zenger, Christoph. Hackbusch, Wolfgang , 編. Parallel Algorithms for Partial Differential Equations (PDF). Vieweg. 1991: 241–251 [2022-01-07]. ISBN 3-528-07631-3. （原始內容 (PDF)存檔於2022-01-22）.

外部連結

• 一種用於常規稀疏網格的高效內存數據結構 （頁面存檔備份，存於網際網路檔案館）
• 稀疏網格上的有限差分格式 （頁面存檔備份，存於網際網路檔案館）
• 稀疏網格上的可視化
• 稀疏網格上的數據挖掘，J.Garcke、M.Griebel (pdf) （頁面存檔備份，存於網際網路檔案館）

1. Sparse Grid Basics. sparsegrids.org. [2022-01-10]. （原始內容存檔於2022-01-10）.