最小次数アルゴリズム

数値解析において、最小次数アルゴリズムとは、コレスキー分解を適用する前に対称疎行列の行と列を並べ替え、コレスキー因子における非ゼロ値の個数を減らすアルゴリズムである。これにより必要な記憶容量が削減され、より少ない算術演算でコレスキー因子を適用できる。（場合によっては、前処理として用いられる不完全コレスキー因子にも適用される。例えば、前処理付き共役勾配アルゴリズムなど）。

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

線形システムを考えると

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

ここで、Aは実対称疎正方行列である。コレスキー因子Lは典型的には「穴埋め」、つまりAの上三角よりも多くの非零要素を持つ。我々は、同じく対称行列である行列Pがコレスキー因子の穴埋めを可能な限り少なくするような 置換行列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 \varepsilon >0}$

参考文献

• Cummings, Robert; Fahrbach, Matthew; Fatehpuria, Animesh (2021). 「高速最小次数アルゴリズムとマッチング下限値」. Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms : 724– 734. arXiv : 1907.12119 . doi :10.1137/1.9781611976465.45. ISBN 978-1-61197-646-5. S2CID  198968052。
• ジョージ, アラン; リュー, ジョセフ (1989). 「最小次数順序アルゴリズムの進化」. SIAM Review . 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). 「疎な正定値線形方程式の数値解に関するグラフ理論的研究」.グラフ理論とコンピューティング. アカデミック・プレス. 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.