最小次数アルゴリズム

数値解析において、最小次数アルゴリズムは、コレスキー分解を適用する前に対称スパース行列の行と列を並べ替え、コレスキー因子の非ゼロの数を減らすために使用されるアルゴリズムです。これにより、必要なストレージが削減され、より少ない算術演算でコレスキー因子を適用できるようになります。(場合によっては、前処理として使用される不完全コレスキー因子にも関係することがあります。たとえば、前処理付き共役勾配アルゴリズムなどです。)

最小次数アルゴリズムは有限要素法でよく使用され、偏微分方程式の係数ではなくメッシュのトポロジーのみに応じてノードの並べ替えを実行できるため、さまざまな係数値に同じメッシュを使用する場合に効率が向上します。

線形システムを考えると

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

ここで、A は実対称疎正方行列である。コレスキー因子L は典型的には「埋め」の影響を受ける。つまり、Aの上三角よりも非ゼロ要素が多くなる。我々は、対称行列 のコレスキー因子の埋めが可能な限り少なくなるような置換行列Pを求める。我々は、並べ替えられたシステムを解く。 ${\displaystyle n\times n}$ ${\displaystyle \mathbf {P} ^{T}\mathbf {A} \mathbf {P} }$

${\displaystyle \left(\mathbf {P} ^{T}\mathbf {A} \mathbf {P} \right)\left(\mathbf {P} ^{T}\mathbf {x} \right)=\mathbf {P} ^{T}\mathbf {b} .}$

最適な順序付けを見つける問題はNP 完全問題であるため扱いにくいため、代わりにヒューリスティックな方法が使用されます。最小次数アルゴリズムは、非対称線形計画問題に対して 1959 年にMarkowitzによって最初に提案された方法から派生したもので、大まかに次のように説明されます。ガウス消去法の各ステップで、行と列の置換が実行され、ピボット行と列の非対角の非ゼロの数を最小限に抑えます。Markowitz 法の対称バージョンは 1967 年に Tinney と Walker によって説明され、Rose は後に因数分解のみがシミュレートされるアルゴリズムのグラフ理論的バージョンを導き、これを最小次数アルゴリズムと名付けました。ここで参照されるグラフは、 のときに頂点iとj が辺で接続されたn個の頂点を持つグラフであり、次数は頂点の次数です。このようなアルゴリズムの重要な側面は、同じ次数になる番号の付け直しを選択できる場合の同点決着戦略です。 ${\displaystyle a_{ij}\neq 0}$

最小次数アルゴリズムのバージョンは、MATLAB関数symmmd (MMD は多重最小次数を表す) に実装されていましたが、現在はより高速な対称近似多重最小次数関数symamdに置き換えられています。これは理論的な分析によって確認されており、 n頂点とm辺を持つグラフの場合、MMD の実行時間にはという厳しい上限があるのに対し、AMD の場合は という厳しい上限が成り立つことが示されています。Cummings、Fahrbach、および Fatehpuria は、実行時間 の正確な最小次数アルゴリズムを設計し、強い指数時間仮説を仮定すると、任意の に対して の時間で実行されるアルゴリズムは存在しないことを示しました。 ${\displaystyle O(n^{2}m)}$${\displaystyle O(nm)}$${\displaystyle O(nm)}$${\displaystyle O(nm^{1-\varepsilon })}$${\displaystyle \epsilon >0}$

• Cummings, Robert; Fahrbach, Matthew; Fatehpuria, Animesh ( 2021). 「高速最小次数アルゴリズムとマッチング下限」。第32回ACM-SIAM離散アルゴリズムシンポジウム議事録: 724–734。arXiv : 1907.12119。doi : 10.1137 / 1.9781611976465.45。ISBN 978-1-61197-646-5. S2CID  198968052。
• ジョージ、アラン ;リュー、ジョセフ (1989)。「最小次数順序アルゴリズムの進化」。SIAM レビュー。31 (1): 1–19。doi : 10.1137/1031001。JSTOR 2030845。OSTI  5686483。
• Heggernes, P. ; Eisenstat, SC; Kumfert, G.; Pothen, A. (2001)、最小次数アルゴリズムの計算複雑性(PDF) (技術レポート)、科学技術におけるコンピュータ応用研究所
• Markowitz, HM (1957). 「逆行列の消去形式と線形計画法への応用」. Management Science . 3 (3): 255–269. doi :10.1287/mnsc.3.3.255. JSTOR  2627454. 2017年9月24日時点のオリジナルよりアーカイブ。
• Rose, DJ (1972)。「疎な正定値線形方程式の数値解のグラフ理論的研究」。グラフ理論とコンピューティング。Academic Press。pp. 183–217。ISBN 0-12-583850-6。
• Tinney, WF; Walker, JW (1967). 「最適順序付けされた三角因数分解によるスパースネットワーク方程式の直接解」Proc. IEEE . 55 (11): 1801–1809. doi :10.1109/PROC.1967.6011.