스파스 그리드

희소성 그리드는 고차원 함수를 표현, 통합 또는 보간하기 위한 숫자 기법이다. 그것들은 원래 러시아의 수학자 세르게이 A에 의해 개발되었다. 스몰랴크(Smolyak)는 라자르 류스터니크(Lazar Lysternik)의 제자로, 희박한 텐서(stensor) 제품구조에 기반을 두고 있다. 그러한 그리드의 효율적인 구현을 위한 컴퓨터 알고리즘은 후에 마이클 그리벨과 크리스토프 젠거에 의해 개발되었다.

차원성의 저주

다차원 함수를 나타내는 표준 방법은 텐서 또는 전체 그리드가 있다. 저장 및 처리해야 하는 기본 함수 또는 노드(그리드 포인트)의 수는 차원의 수에 따라 기하급수적으로 달라진다. 오늘날의 연산력으로는 4~5차원이^{[citation needed]} 넘는 기능을 처리할 수 없다.

차원성의 저주는 ${\displaystyle {레벨}_{}}$ $l{\displaystyle }$ ${\displaystyle l$의 4각형에 $의해{\displaystyle {}_{}}$ N l ${\$ 포인트로$$ 이루어지는 통합 오류의 순서로 표현된다. 함수는 규칙성 $r{\displaystyle }$ ${\displaystyle$ r$\},$ 즉 $r{\displaystyle }$ ${\displaystyle r}$배$$ 차이가 있다. 치수 수는 $d{\displaystyle }$ ${\displaystyle$ d$}$이다$.$

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

스몰랴크의 사분법칙

스몰랴크는 일변량 사분법 $규칙{\displaystyle {}^{}}$ ${\displaystyle {\mathrm{Q}}^{}}$( 1$){\$를 바탕으로 다차원 함수를 통합하는 계산적으로 더 효율적인 방법을 발견했다$.$ 함수 $f{\displaystyle }$ ${\displaystyle f}$의 d ${\displaystyle$ $Q^{(d$)} d {\$displaystyle$ $integrated{\displaystyle {}^{}}$ Q $){\$d$$$}}}$는 텐서 제품으로 재귀 공식으로 작성할 수 있다$$.

${\displaystyle Q_{l}^{(d)^{{f=\left(\sum _{i=1}^{l}\left(Q_{i}^{i}^{{i-1}^{{i-1}\right)\time Q_{l-i+1}^{d-1}\f}$

$Q{\displaystyle }$ ${\displaystyle Q}$에 대한 인덱스는 디스커트화 수준이다$$. $레벨{\displaystyle }$ $i{\displaystyle }$ ${\displaystyle i}$의 1차원 통합이 O${\displaystyle }$( ${\displaystyle 2^{}}$ i${\displaystyle {}^{}}$) ${\displaystyle O (2^{i}}})$ 포인트의$$ 평가에 의해 계산되는$$ 경우, $정규성{\displaystyle }$ r$${\$displaystyle$r}의 함수에 대한 오차 ${\displaystyle 추정치}$는 ${\displaystyle E_{}{}_{}}$l =${\displaystyle O}$ ${\displaystyle {(}^{}{}_{}^{}N{}_{}^{}}$ ${\displaystyle {l_{}}^{}}$ - ${\displaystyle r_{}^{}}$ -${\displaystyle {}_{}^{}{}^{}}$l${\displaystyle {{}_{}}^{}}$(${\displaystyle d^{}}$-${\displaystyle 1^{}}$ )${\displaystyle {}^{}}$(${\displaystyle {}^{}}$r${\displaystyle {}^{}}$+ 1${\displaystyle {}^{}}$) {${\displaystyle {\mathrm{displayle}}^{}}$)가$된다$$.$$_{l} =O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}}$

추가 읽기

• Brumm, J.; Scheidegger, S. (2017). "Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models". Econometrica. 85 (5): 1575–1612. doi:10.3982/ECTA12216.
• Garcke, Jochen (2012). "Sparse Grids in a Nutshell" (PDF). In Garcke, Jochen; Griebel, Michael (eds.). Sparse Grids and Applications. Springer. pp. 57–80. ISBN 978-3-642-31702-6.
• Zenger, Christoph (1991). "Sparse Grids" (PDF). In Hackbusch, Wolfgang (ed.). Parallel Algorithms for Partial Differential Equations. Vieweg. pp. 241–251. ISBN 3-528-07631-3.

외부 링크

• 일반 스파스 그리드를 위한 메모리 효율적인 데이터 구조
• 희소성 그리드의 유한 차이 계획
• 스파스 그리드의 시각화
• J.Garke, M.의 희소 그리드에서 데이터밍그리벨(pdf)