階層マトリックス
近似法

数値数学では、階層的行列（H 行列）[1] [2] [3] は非スパース行列のデータスパース近似として使用されます。次元のスパース行列は、非ゼロの要素のみを格納することにより 単位のストレージで効率的に表現できますが、非スパース行列では 単位のストレージが必要になるため、大規模な問題にこのタイプの行列を使用すると、ストレージと計算時間の点で法外なコストがかかります。 階層的行列は単位のストレージのみを必要とする近似を提供します。 は近似の精度を制御するパラメーターです。一般的な用途、たとえば積分方程式を離散化する場合、[4] [5] [6] [7] [8] [9]、 結果として得られる線形方程式のシステムの前処理を行う場合、[10] 、または楕円型偏微分方程式を解く場合、[11] [12] [13 ] [14]では、の精度を確保するには、に比例するランクで十分です。非スパース行列の他の多くのデータスパース表現と比較して、階層的行列には大きな利点がある。行列の乗算、因数分解、逆行列などの行列算術演算の結果を、演算で近似することができる。 [2] n {\displaystyle n} お （ n ） {\displaystyle O(n)} お （ n 2 ） {\displaystyle O(n^{2})} お （ n け ログ ⁡ （ n ） ） {\displaystyle O(nk\,\log(n))} け {\displaystyle k} ログ ⁡ （ 1 / ϵ ） γ {\displaystyle \log(1/\epsilon )^{\gamma }} γ {\displaystyle \gamma} ϵ {\displaystyle \epsilon } お （ n け α ログ ⁡ （ n ） β ） {\displaystyle O(nk^{\alpha }\,\log(n)^{\beta })} α 、 β ∈ { 1 、 2 、 3 } 。 {\displaystyle \alpha,\beta\in\{1,2,3\}.}

基本的な考え方

階層的行列は局所的な低ランク近似に依存します。 をインデックス集合とし、を近似する行列とします。多くの応用（上記参照）において、 を ランク行列で近似できるような部分集合を見つけることができます。この近似は、 を因子とする因数 分解形式で表すことができます。行列の標準的な表現では単位の記憶域が必要ですが、因数分解表現では単位のみで済みます。が大きすぎない場合、必要な記憶域は大幅に削減されます。 私 、 J {\displaystyle I,J} G ∈ R 私 × J {\displaystyle G\in {\mathbb {R} }^{I\times J}} t ⊆ 私 、 s ⊆ J {\displaystyle t\subseteq I,s\subseteq J} G | t × s {\displaystyle G|_{t\times}} け {\displaystyle k} G | t × s ≈ あ B ∗ {\displaystyle G|_{t\times}\approx AB^{*}} あ ∈ R t × け 、 B ∈ R s × け {\displaystyle A\in {\mathbb {R} }^{t\times k},B\in {\mathbb {R} }^{s\times k}} G | t × s {\displaystyle G|_{t\times}} お （ （ # t ） （ # s ） ） {\displaystyle O((\#t)(\#s))} お （ け （ # t + # s ） ） {\displaystyle O(k(\#t+\#s))} け {\displaystyle k}

行列全体を近似するために、行列は部分行列の族に分割されます。大きな部分行列は因数分解表現で保存され、小さな部分行列は効率を向上させるために標準表現で保存されます。 G {\displaystyle G}

低ランク行列は、パネルクラスタリングで使用される退化展開や、積分演算子を近似する高速多重極法 と密接に関連しています。この意味で、階層行列はこれらの手法の代数的対応物と考えることができます。

積分演算子への応用

階層的行列は積分方程式、例えば境界要素法に現れる単層および二重層ポテンシャル演算子を扱うのに効果的に用いられる。典型的な演算子は以下の形式を持つ。

G [ あなた ] （ × ） ＝ ∫ Ω κ （ × 、 y ） あなた （ y ） d y 。 {\displaystyle {\mathcal {G}}[u](x)=\int _{\Omega }\kappa (x,y)u(y)\,dy.}

ガラーキン法は次のような形式の行列要素を導く。

g i j = ∫ Ω ∫ Ω κ ( x , y ) φ i ( x ) ψ j ( y ) d y d x , {\displaystyle g_{ij}=\int _{\Omega }\int _{\Omega }\kappa (x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx,}

ここで、およびは有限要素基底関数の族である。核関数が十分に滑らかであれば、多項式補間によって近似して、 ( φ i ) i ∈ I {\displaystyle (\varphi _{i})_{i\in I}} ( ψ j ) j ∈ J {\displaystyle (\psi _{j})_{j\in J}} κ {\displaystyle \kappa }

κ ~ ( x , y ) = ∑ ν = 1 k κ ( x , ξ ν ) ℓ ν ( y ) , {\displaystyle {\tilde {\kappa }}(x,y)=\sum _{\nu =1}^{k}\kappa (x,\xi _{\nu })\ell _{\nu }(y),}

ここでは補間点の族であり、は対応するラグランジュ多項式 の族である。を で置き換えると近似値が得られる。 ( ξ ν ) ν = 1 k {\displaystyle (\xi _{\nu })_{\nu =1}^{k}} ( ℓ ν ) ν = 1 k {\displaystyle (\ell _{\nu })_{\nu =1}^{k}} κ {\displaystyle \kappa } κ ~ {\displaystyle {\tilde {\kappa }}}

g ~ i j = ∫ Ω ∫ Ω κ ~ ( x , y ) φ i ( x ) ψ j ( y ) d y d x = ∑ ν = 1 k ∫ Ω κ ( x , ξ ν ) φ i ( x ) d x ∫ Ω ℓ ν ( y ) ψ j ( y ) d y = ∑ ν = 1 k a i ν b j ν {\displaystyle {\tilde {g}}_{ij}=\int _{\Omega }\int _{\Omega }{\tilde {\kappa }}(x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx=\sum _{\nu =1}^{k}\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx\int _{\Omega }\ell _{\nu }(y)\psi _{j}(y)\,dy=\sum _{\nu =1}^{k}a_{i\nu }b_{j\nu }}

係数

a i ν = ∫ Ω κ ( x , ξ ν ) φ i ( x ) d x , {\displaystyle a_{i\nu }=\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx,}
b j ν = ∫ Ω ℓ ν ( y ) ψ j ( y ) d y . {\displaystyle b_{j\nu }=\int _{\Omega }\ell _{\nu }(y)\psi _{j}(y)\,dy.}

すべての に対して同じ補間点を選択して使用すると、 が得られます 。 t ⊆ I , s ⊆ J {\displaystyle t\subseteq I,s\subseteq J} i ∈ t , j ∈ s {\displaystyle i\in t,j\in s} G | t × s ≈ A B ∗ {\displaystyle G|_{t\times s}\approx AB^{*}}

明らかに、変数とを分離する他の近似、たとえば多重極展開によっても、二重積分を 2 つの単一積分に分割することができ、同様に因数分解された低階数行列を得ることができます。 x {\displaystyle x} y {\displaystyle y}

特に興味深いのは、 元の行列の要素のみを使用して低ランク近似を構築する交差近似手法[6] [7] [15]である。 G {\displaystyle G}

楕円型偏微分方程式への応用

楕円偏微分方程式の解演算子はグリーン関数を含む積分演算子として表現できるため 、有限要素法 とスペクトル法から生じる剛性行列の逆行列が階層行列で近似できることは驚くべきことではありません。

グリーン関数は計算領域の形状に依存するため、通常は既知ではありません。しかし、近似演算を用いることで、関数を明示的に知らなくても近似逆関数を計算することができます。

驚くべきことに、微分演算子が滑らかでない係数を含み、グリーン関数が滑らかでなくても、逆関数を近似できること が証明できる[11] [12] [13] [14] 。

算術演算

階層的行列法の最も重要な革新は、非スパース行列に対して（近似）行列算術演算を実行するための効率的なアルゴリズムの開発です。たとえば、近似逆行列、LU 分解、行列方程式の解を計算します。

中心的なアルゴリズムは、効率的な行列-行列乗算、すなわち階層行列とスカラー因子に対するの計算です。このアルゴリズムでは、階層行列の部分行列がブロックツリー構造に構成されている必要があり、因数分解された低ランク行列の特性を利用して、演算における 更新された を計算します。 Z = Z + α X Y {\displaystyle Z=Z+\alpha XY} X , Y , Z {\displaystyle X,Y,Z} α {\displaystyle \alpha } Z {\displaystyle Z} O ( n k 2 log ⁡ ( n ) 2 ) {\displaystyle O(nk^{2}\,\log(n)^{2})}

ブロック構造を利用することで、対角ブロックの逆元とシュアー補集合を再帰的に計算し、それらを行列-行列乗算で組み合わせることで、逆元を計算できます。同様に、LU分解[16] [17]は 再帰と乗算のみで構築できます。どちらの演算も演算を必要とします。 O ( n k 2 log ⁡ ( n ) 2 ) {\displaystyle O(nk^{2}\,\log(n)^{2})}

H2-行列

非常に大きな問題を扱うために、階層的行列の構造を改良することができる。H2行列[18] [ 19] は、ブロックの一般的な低ランク構造を、高速多重極法に密接に関連した階層的表現に置き換え、記憶の複雑さを軽減する。 O ( n k ) {\displaystyle O(nk)}

境界積分演算子の文脈では、固定ランクをブロック依存ランクに置き換えると、基礎となる境界要素法の収束速度を[20] [21]の複雑さで維持する近似が得られる。 k {\displaystyle k} O ( n ) . {\displaystyle O(n).}

H 2行列の乗算、逆行列、コレスキー分解またはLR分解といった算術演算は、2つの基本的な演算、すなわち部分行列との行列ベクトル乗算と部分行列の低ランク更新に基づいて実装できます。行列ベクトル乗算は単純ですが、適応的に最適化されたクラスター基底を用いた効率的な低ランク更新の実装は大きな課題となります。[22]

文学

  1. ^ Hackbusch, Wolfgang (1999). 「H行列に基づくスパース行列演算．パートI：H行列入門」. Computing . 62 (2): 89– 108. doi :10.1007/s006070050015. S2CID  24294140.
  2. ^ ab Grasedyck, Lars; Hackbusch, Wolfgang (2003). 「H行列の構築と算術」. Computing . 70 (4): 295– 334. doi :10.1007/s00607-003-0019-1.
  3. ^ Hackbusch, Wolfgang (2015).階層的行列：アルゴリズムと解析. Springer Series in Computational Mathematics. Vol. 49. Springer. doi :10.1007/978-3-662-47324-5. ISBN 978-3-662-47323-8。
  4. ^ Bebendorf, Mario (2008).階層的行列：楕円境界値問題を効率的に解く手段. Springer.
  5. ^ Hackbusch, Wolfgang; Khoromskij, Boris N. (2000). 「スパースH行列演算。パートII：多次元問題への応用」. Computing . 64 : 21–47 . doi :10.1007/PL00021408.
  6. ^ ab Bebendorf, Mario (2000). 「境界要素行列の近似」. Numer. Math . 86 (4): 565– 589. doi :10.1007/pl00005410. S2CID  206858339.
  7. ^ ab Bebendorf, Mario; Rjasanow, Sergej (2003). 「コロケーション行列の適応型低ランク近似」. Computing . 70 : 1– 24. CiteSeerX 10.1.1.133.182 . doi :10.1007/s00607-002-1469-6. S2CID  16501661. 
  8. ^ Börm, Steffen; Grasedyck, Lars (2005). 「積分演算子のハイブリッド交差近似」. Numer. Math . 101 (2): 221– 249. CiteSeerX 10.1.1.330.8950 . doi :10.1007/s00211-005-0618-1. S2CID  263882011. 
  9. ^ Börm, Steffen; Christophersen, Sven (2016). 「グリーン求積法とネスト交差近似による積分演算子の近似」. Numer. Math . 133 (3): 409– 442. arXiv : 1404.2234 . doi :10.1007/s00211-015-0757-y. S2CID  253745725.
  10. ^ Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2016). 「BEM行列の逆行列に対するH行列近似の存在：単純層演算子」. Math. Comp . 85 (297): 119– 152. arXiv : 1311.5028 . doi :10.1090/mcom/2990. S2CID  10706786.
  11. ^ ab Bebendorf, Mario; Hackbusch, Wolfgang (2003). 「-係数を持つ楕円型作用素の逆FE行列に対するH行列近似の存在」. Numer. Math . 95 : 1– 28. doi :10.1007/s00211-002-0445-6. S2CID  263876883. L ∞ {\displaystyle L^{\infty }}
  12. ^ ab Börm, Steffen (2010). 「楕円型偏微分方程式の解演算子のH行列およびH 2行列による近似」. Numer. Math . 115 (2): 165– 193. doi :10.1007/s00211-009-0278-7. S2CID  7737211.
  13. ^ ab Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2015). 「FEM行列の逆行列のH行列近似可能性」. Numer. Math . 131 (4): 615– 642. arXiv : 1308.0499 . doi :10.1007/s00211-015-0706-9. S2CID  2619823.
  14. ^ ab Shen, Jie; Wang, Yingwei; Xia, Jianlin (2016). 「変数係数を持つ微分方程式に対する高速構造化直接スペクトル法」SIAM Journal on Scientific Computing . 38 (1): A28 – A54 . doi :10.1137/140986815.
  15. ^ Tyrtyshnikov, Eugene (2000). 「モザイクスケルトン法における不完全交差近似」. Computing . 64 (4): 367– 380. CiteSeerX 10.1.1.100.6153 . doi :10.1007/s006070070031. S2CID  15850058. 
  16. ^ Bebendorf, Mario (2007). 「有限要素法の離散化を三角階層行列で因数分解できる理由」SIAM J. Numer. Anal . 45 (4): 1472– 1494. doi :10.1137/060669747.
  17. ^ Grasedyck, Lars; Kriemann, Ronald; Le Borne, Sabine (2009). 「領域分割に基づくH-LU前処理」. Numer. Math . 112 (4): 565– 600. doi : 10.1007/s00211-009-0218-6 .
  18. ^ Hackbusch, Wolfgang; Khoromskij, Boris N.; Sauter, Stefan (2002). 「H 2-行列について」.応用数学講義. pp.  9– 29. doi :10.1007/978-3-642-59709-1_2. ISBN 978-3-642-64094-0。
  19. ^ Börm, Steffen (2010). 非局所演算子のための効率的な数値解析法：H2行列の圧縮、アルゴリズム、解析. EMS Tracts in Mathematics. ISBN 9783037190913。
  20. ^ Sauter, Stefan (2000). 「可変順序パネルクラスタリング」. Computing . 64 (3): 223– 261. doi :10.1007/s006070050045. S2CID  36813444.
  21. ^ Börm, Steffen; Sauter, Stefan (2005). 「古典境界積分演算子に対する線形複雑度を持つBEM」. Math. Comp . 74 (251): 1139– 1177. doi : 10.1090/s0025-5718-04-01733-8 .
  22. ^ Börm, Steffen; Reimer, Knut (2015). 「階層的低ランク更新に基づくランク構造行列の効率的な算術演算」. Computing and Visualization in Science . 16 (6): 247– 258. arXiv : 1402.5056 . doi :10.1007/s00791-015-0233-3. S2CID  36931036.

ソフトウェア

HLib は、階層型および階層型行列の最も重要なアルゴリズムを実装する C ソフトウェア ライブラリです。 H 2 {\displaystyle {\mathcal {H}}^{2}}

AHMED は、教育目的でダウンロードできる C++ ソフトウェア ライブラリです。

HLIBpro は、商用アプリケーション向けのコア階層型マトリックス アルゴリズムの実装です。

H2Lib は、研究と教育を目的とした階層型マトリックス アルゴリズムのオープン ソース実装です。

awesome-hierarchical-matrices は、他の H 行列の実装のリストを含むリポジトリです。

HierarchicalMatrices.jl は、階層型行列を実装する Julia パッケージです。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hierarchical_matrix&oldid=1285634482"