階層マトリックス

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

階層的行列は、ローカルな低ランク近似に依存します。 をインデックス セットとし、 を近似する行列とします。多くのアプリケーション (上記を参照) では、 を ランク行列で近似できるサブセットを見つけることができます。 この近似は、因子 を持つ因数 分解形式で表すことができます。 行列の標準表現には単位のストレージが必要ですが、因数分解表現には単位のみが必要です。が大きすぎない場合、必要なストレージは大幅に削減されます。 ${\displaystyle I,J}$${\displaystyle G\in {\mathbb {R} }^{I\times J}}$${\displaystyle t\subseteq I,s\subseteq J}$${\displaystyle G|_{t\times}}$${\displaystyle k}$${\displaystyle G|_{t\times}\approx AB^{*}}$${\displaystyle A\in {\mathbb {R} }^{t\times k},B\in {\mathbb {R} }^{s\times k}}$${\displaystyle G|_{t\times}}$${\displaystyle O((\#t)(\#s))}$${\displaystyle O(k(\#t+\#s))}$${\displaystyle k}$

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

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

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

${\displaystyle {\mathcal {G}}[u](x)=\int _{\Omega }\kappa (x,y)u(y)\,dy.}$

ガラーキン法では、次のような行列要素が得られる。

${\displaystyle g_{ij}=\int _{\Omega }\int _{\Omega }\kappa (x,y)\varphi _{i}(x)\psi _{j}(y)\,dy \,dx,}$

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

${\displaystyle {\tilde {\kappa }}(x,y)=\sum _{\nu =1}^{k}\kappa (x,\xi _{\nu })\ell _{\nu } (y),}$

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

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

係数

${\displaystyle a_{i\nu }=\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx,}$

${\displaystyle b_{j\nu }=\int _{\Omega }\ell _{\nu }(y)\psi _{j}(y)\,dy.}$

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

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

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

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

グリーン関数は計算領域の形状に依存するため、通常は不明です。ただし、近似演算を使用すると、関数を明示的に知らなくても近似逆関数を計算できます。

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

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

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

ブロック構造を利用すると、再帰を使用して対角ブロックの逆行列とシュアー補数を計算し、行列-行列乗算を使用して両方を組み合わせることで、逆行列を計算できます。同様に、LU分解^{[16] [17]}は 再帰と乗算のみを使用して構築できます。両方の操作にも操作が必要です。 ${\displaystyle O(nk^{2}\,\log(n)^{2})}$

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

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

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

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

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

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

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

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

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