スパースグリッド

スパースグリッドは、高次元関数を表現、積分、または補間するための数値手法です。もともとは、ラザール・リュスターニクの弟子であったロシアの 数学者セルゲイ・A・スモリャクによって開発され、スパーステンソル積の構築に基づいています。その後、このようなグリッドを効率的に実装するためのコンピュータアルゴリズムが、マイケル・グリーベルとクリストフ・ゼンガーによって開発されました。

多次元関数を表現する標準的な方法は、テンソルまたはフル グリッドです。保存および処理する必要がある基底関数またはノード (グリッド ポイント) の数は、次元の数に指数 的に依存します。

次元の呪いは、点を持つレベル の求積法によって生成される積分誤差の順序で表現されます。関数は の規則性を持ち、つまり回微分可能です。次元数は です。 ${\displaystyle l}$${\displaystyle N_{l}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle d}$

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

スモリャクは、一変量求積法に基づいて、計算上より効率的な多次元関数の積分法を発見した。関数の次元スモリャク積分は、テンソル積を持つ再帰式として表すことができる。 ${\displaystyle Q^{(1)}}$${\displaystyle d}$${\displaystyle Q^{(d)}}$${\displaystyle 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}$

のインデックスは離散化のレベルです。レベル上の1次元積分が点の評価によって計算される場合、正則関数の誤差推定値は次のようになります。 ${\displaystyle Q}$${\displaystyle i}$${\displaystyle O(2^{i})}$${\displaystyle r}$${\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}$

• Brumm, J.; Scheidegger, S. (2017). 「アダプティブスパースグリッドを使用した高次元動的モデルの解決」(PDF) . Econometrica . 85 (5): 1575–1612. doi :10.3982/ECTA12216.
• ガルケ、ヨッヘン (2012)。 「スパースグリッドの概要」(PDF)。ガルケ、ヨッヘンでは。マイケル・グリーベル（編）。スパースグリッドとアプリケーション。スプリンガー。 57–80ページ。ISBN 978-3-642-31702-6。
• クリストフ・ゼンガー (1991)。 「スパースグリッド」(PDF)。ハックブッシュ、ヴォルフガング編（編）。偏微分方程式の並列アルゴリズム。見るeg。 241–251ページ。ISBN 3-528-07631-3。

• 規則的なスパースグリッドのためのメモリ効率の良いデータ構造
• 疎なグリッド上の差分スキーム
• 疎グリッド上の可視化
• スパースグリッドでのデータマイニング、J.Garcke、M.Griebel (pdf)