大規模分散並列環境におけるコレスキー45 型アルゴリズムによる縦長行列の列ピボット付き 45 分解の性能評価（続）深谷猛
北海道大学情報基盤センター

１．はじめに
行列分解は科学技術計算の基盤技術の一つであり、高性能な数値計算技術が求められている。
著者らは、基本的な行列分解の一種である 45 分解について、これまでに様々な研究開発を行ってきた。前回の記事>@では、縦長行列に対する列ピボット付き 45 分解（通称：45&3：45
IDFWRUL]DWLRQZLWKFROXPQSLYRWLQJ）>@に対して、著者らが現在開発している &KROHVN\45 型アルゴリズムを、 年  月実施の大規模 +3& チャレンジで評価した結果の速報を報告した。
その後、再度、 年  月に「:LVWHULD%'(& 2G\VVH\ 」および「2DNEULGJH&;」の両シス
テムにおける大規模 +3& チャレンジの機会を頂き、初回の性能評価の後に改良を加えたアルゴリズムについて、より詳細な性能評価を実施することができた。そこで、本稿では、 回目の大規模 +3& チャレンジにおける性能評価を通して得られた最新の結果のハイライトを紹介する。


２．前回の記事の概要
本節では、前回の記事>@の概要を述べる。詳細については、前回の記事を参照されたい。
２．１．問題設定および代表的なアルゴリズム
与えられた行列𝐴𝐴 ∈ ℝ𝑚𝑚×𝑛𝑛 (𝑚𝑚 ≥ 𝑛𝑛)に対して

𝐴𝐴𝐴𝐴 = 𝑄𝑄𝑄𝑄の形で行列を分解する計算を 45&3 と呼ぶ>@。ここで、𝑃𝑃 ∈ ℝ𝑛𝑛×𝑛𝑛 は置換行列、𝑄𝑄 ∈ ℝ𝑚𝑚×𝑛𝑛 は列直交行列、𝑅𝑅 ∈ ℝ𝑛𝑛×𝑛𝑛 は上三角行列である。45&3 は 5DQN 5HYHDOLQJ 45 分解の一種であり、行列の低ランク近似等の応用を持つ>@。なお、本研究では行列𝐴𝐴が縦長（WDOOVNLQQ\）の場合、つまり、𝑚𝑚 ≫ 𝑛𝑛の場合を想定する。

45&3 に対して、列ピボット付きハウスホルダー45 分解（+45&3：+RXVHKROGHU45ZLWK&ROXPQ3LYRWLQJ）が代表的な数値計算アルゴリズムとして知られている>@。+45&3 では、各ステップで貪欲法的にピボット列を選択（𝑃𝑃の構成と本質的に等価）しながら、ハウスホルダー変換による行列の上三角化を行う。これらの詳細は、例えば、文献>@等を参照されたい。


２．２．45&3 に対するコレスキー45 型アルゴリズムの開発
縦長行列に対する通常（列ピボットなし）の 45 分解において、コレスキー45 型アルゴリズムが有効である>@。この事実を踏まえて、コレスキー45 型アルゴリズムを 45&3に拡張し、その有効性を示すことが我々の研究目的である。数学的には、通常のコレスキー45 ア
ルゴリズムに対して、コレスキー分解を完全ピボット（&RPSOHWH 3LYRWLQJ）付きコレスキー分
解：𝑃𝑃⊤ 𝑊𝑊𝑊𝑊 → 𝑅𝑅 ⊤ 𝑅𝑅>@に置き換えることで、45&3 への拡張が可能となる。しかし、数値計算の

スーパーコンピューティングニュース
- 52-

Vol. 26, No.22024

場合、丸め誤差の影響を受けるため、一般的に、正しい（+45&3 と等しい）ピボットの選択に失敗する。
そこで、我々は、完全ピボット付きコレスキー分解の計算過程で現れる値をチェックして、ある条件を満たした場合に計算を打ち切り（それ以降の結果の信頼性が低いと判断）、それまでに得られた部分的なピボット選択の情報のみを採用するアプローチを考案した。そして、反復的に（部分的な）完全ピボット付きコレスキー分解を繰り返す形のアルゴリズムを構築し、,WH
&KRO45&3（,WHUDWLYH&KROHVN\45ZLWK&ROXPQ3LYRWLQJ）と名付けた。,WH&KRO45&3 の基本的な構造は、従来のコレスキー45 型アルゴリズムと同じであり、計算の大部分が行列積（*(00）に代表される /HYHO%/$6 で実行可能であり、分散並列計算における集団通信の回数が𝑂𝑂(1)である（&$&RPPXQLFDWLRQ$YRLGLQJ）、といった高性能計算に適した特徴を維持している。なお、,WH&KRO45&3 の詳細については、本研究の成果をまとめた論文>@が国際会議に採択されたので、そちらに委ねる形としたい。


２．３．性能評価結果の概要：+45&3 との比較
:LVWHULD%'(& 2G\VVH\ （以下、%'(&2）と 2DNEULGJH&;（以下、2%&;）の両システム上で、03,（と  次元データ分散）を用いて分散並列実装した ,WH&KRO45&3 を、代表的な既存手法である +45&3（の簡略版）と比較した。%'(&2（ ノード）では、𝑛𝑛が比較的小さい（𝑛𝑛 =16, 32, 64）の場合に、,WH&KRO45&3 は +45&3 よりも高速（最大で  倍弱）であった。一方、
2%&;（ ノード）の場合に、テストした全ての𝑛𝑛（最大で𝑛𝑛 = 1024）で +45&3 よりも高速（最大で  倍強）であった。これらの結果より、我々が開発した ,WH&KRO45&3 は %'(&2 や 2%&;のような一般的な大規模分散並列環境（所謂、スパコン）において、代表的既存手法である +45
&3 よりも有効な手法となり得る可能性が高いことが示された。なお、共有メモリ環境（マルチコア &38 環境）における性能評価結果も上記の国際会議論文>@で提示しているので、興味がある場合は参照されたい。


３．今回の性能評価の概要と主結果
本節では、今回の大規模 +3& チャレンジの実施内容の概要と主な結果を報告する。


３．１．実施内容の概要
前回の性能評価では、代表的な既存手法の一つである +45&3 を比較対象とした。一方、計算対象の行列が縦長の場合、以下の計算手法も有力となる。まず、行列𝐴𝐴に対して、通常の 45 分解
𝐴𝐴 = 𝑄𝑄1 𝑅𝑅1 を行い、次に、得られた上三角行列𝑅𝑅1 に対して、+45&3（あるいは他の手法）によりと 45&3 を行う。これにより

𝑅𝑅1 𝑃𝑃 = 𝑄𝑄2 𝑅𝑅

𝐴𝐴𝐴𝐴 = 𝑄𝑄1 𝑄𝑄2 𝑅𝑅 = 𝑄𝑄𝑄𝑄, 𝑄𝑄 = 𝑄𝑄1 𝑄𝑄2と行列𝐴𝐴の 45&3 が得られる>@。前半の𝐴𝐴に対する通常の 45 分解の計算量は𝑂𝑂(𝑚𝑚𝑛𝑛2 )であり、一方、後半の𝑅𝑅1 に対する 45&3 の計算量は𝑂𝑂(𝑛𝑛3 )であるため、行列𝐴𝐴が縦長（𝑚𝑚 ≫ 𝑛𝑛）の場合には、前半の計算が支配的となる。したがって、（列ピボットなしの）コレスキー45 型アルゴリズムなど、縦長行列に対する高性能な 45 分解の計算手法を活用することで、高速に 45&3 を計算するこスーパーコンピューティングニュース
- 53 -

Vol. 26, No.22024

とが可能となる。今回、我々が開発した ,WH&KRO45&3 の有効性を議論する上で、この計算手法との比較は不可欠であり、今回の性能評価では、これを主眼に置く。
また、,WH&KRO45&3 の実装方法に関して、いくつか改良できる可能性があることが分かった。
具体的な実装の内容については、現在論文を執筆中であり、それに委ねる形としたい。方針としては、アルゴリズムに対する数学的な考察に基づいた、一部の演算（例：数学的にゼロになることが分かっている部分の演算）の省略や、ループの順番を入れ替えることによる、反復を途中で打ち切る場合に無駄になる可能性の高い演算の削減、という改良の導入を試みた。今回の実装方法の改変により、理論的な演算量の削減は期待できるが、一方で、各処理の演算効率（)/236）
も変わるため、計算時間の意味での有効性は断言できない。そこで、今回の性能評価では、,WH
&KRO45&3 の新旧の実装方法の比較も行う。
最後に、問題設定として、前回の大規模 +3& チャレンジの際の設定（𝑄𝑄, 𝑅𝑅, 𝑃𝑃を全て求める）に加えて、事前に指定された一部の結果（例えば、必要なランクが指定されていて、それに対応する結果）のみを求める場合も考える。このような問題設定に対して、,WH&KRO45&3 は途中で計算を打ち切ることが可能であるが、一方で、上述した縦長行列に対する通常の 45 分解に基づく手法は、前半の 45 分解は完全に行うことが求められる（ランクの情報は後半で得られる）。そのため、,WH&KRO45&3 が有効となる可能の高い問題設定であり、検証する価値があると考える。

性能評価における設定や条件は前回と同様であり、前回の記事>@を参照されたい。今回、新たに比較対象とした、通常の 45 分解に基づく手法に関しては、コレスキー45 型アルゴリズムと7645 アルゴリズムをそれぞれ用いた手法を実装した。前者については、シフト付きコレスキー45（6KLIWHG&KROHVN\45）アルゴリズムを前処理に用いた手法であり、前処理の回数を動的に決定する形を採用した。これらのアルゴリズムの詳細については、文献>@などを参照されたい。なお、上三角行列の 45&3 は +45&3（/$3$&. の関数）を用いた。


３．２．評価結果
図  に、%'(&2（ ノード）および 2%&;（ ノード）における、各手法（の各実装）の+45&3 に対する速度向上を示す。なお、「,WH&KRO45&3」に関して、 が以前の実装、 が新しい実装である。また、「&KRO4545&3」は通常のコレスキー45 型アルゴリズムに基づいた手法、「764545&3」は 7645 アルゴリズムに基づいた手法であり、それぞれ複数の実装を試した（%'(&2 では一部の /$3$&. 関数が利用できないため、評価した 764545&3 の実装が 2%&; よりも少ない）。なお、𝑚𝑚を固定（𝑚𝑚 = 16777216）して、𝑛𝑛 = 16, … , 512と変えて性能を測定した。

図  のグラフから、縦長行列に対する通常の 45 分解を用いた手法も十分に有効であり、条件によっては ,WH&KRO45&3 よりも高性能となっていることが確認できる。また、通常の 45 分解に対するコレスキー45 型アルゴリズムや 7645 アルゴリズムの性能は文献>@などでも報告されており、𝑛𝑛が大きくなった場合に 7645 の性能が低下する点や %'(&2 と 2%&; で性能の挙動が異なる点など、これまでの報告と整合性が確認できる結果であることも分かる。
また、図  より、,WH&KRO45&3 について、今回の実装方法の変更（グラフ中の ）が計算時間の意味でも概ね有効であったことも確認できる。特に、2%&; において𝑛𝑛が大きい場合に効果が高くなっていることが観察できる。
図  の結果から、,WH&KRO45&3 と通常の 45 分解に基づく手法は、どちらも縦長行列の 45&3を計算する際に有望であることが確認できる。また、,WH&KRO45&3 および通常のコレスキー45



スーパーコンピューティングニュース- 54-

Vol. 26, No.22024

型アルゴリズムに基づく手法は、どちらも反復型の計算手法であり、計算対象の行列の条件（や手法内部のパラメータの設定）に応じて反復回数が変化する。そのため、限られた実験結果のみから、両者の優劣を断言すべきではないことにも注意が必要である。以上の内容を踏まえると、我々が開発した ,WH&KRO45&3 について、現時点では、縦長行列の 45&3 の計算において、既存の有力な手法と同程度の性能を持った（有効な選択肢の一つになり得る）手法、と評価するのが妥当であると考える。
次に、部分的な 45 分解を計算する場合を考える。具体的には、𝑄𝑄の一部（前半部分）と対応する𝑅𝑅の部分行列のみを必要とする場合を想定する。このような設定において、,WH&KRO45&3
では反復の途中で計算をストップすることが可能であるが、最初に通常の 45 分解を行う手法では、45 分解全体を計算する必要がある。そのため、,WH&KRO45&3 の有効性が期待できる問題設定である。図  に、%'(&2（ ノード）および 2%&;（ ノード）において、𝑄𝑄の最初の の列ベクトル（𝑛𝑛/4本の列ベクトル）のみを計算する場合の、各手法（の各実装）の +45&3を基準にした速度向上を示す。
 図  より、部分的な 45&3 を計算する設定では、,WH&KRO45&3 が、通常の 45 分解を用いる手法よりも有効となるケースが多く、また、両者の差も図  の結果より大きいことが確認できる。特に、𝑛𝑛が大きくなるほど、両者の差が拡大する傾向にあることが読み取れる。ただし、+45&3 も途中で計算をストップすることができるため、+45&3 に対する速度向上は𝑛𝑛に応じて大きくなるわけではなく、注意が必要である。
４．おわりに
本稿では、前回の記事に引き続き、我々が開発しているコレスキー45 型の 45&3 アルゴリズム（,WH&KRO45&3）に関する性能評価の結果を中心に報告した。特に、縦長行列の 45&3 を、通常の 45 分解を利用して計算する手法を比較対象とした性能評価の結果を示した。これまでに得られた性能評価の結果より、,WH&KRO45&3 は、通常の 45 分解を利用する手法と同程度の性能が期待され、状況に応じて両者の優劣は変化することが確認できた。乱択アルゴリズム>@などのその他の最新のアルゴリズムを含めて、より詳細な性能評価を行うことが今後の課題である。また、部分的な 45&3 を計算する設定では、,WH&KRO45&3 の有効性が十分に期待できることが分かった。各アプリケーションでのニーズに応じて、適切な計算手法を使い分けることが重要であり、そのための判断材料になる性能データの収集や分析を今後行うことが必要である。
謝 辞
 大規模 +3& チャレンジの実施に関してお世話になりました、東京大学情報基盤センターの関係者の皆様に深く感謝いたします。本稿は、山本有作教授（電気通信大学）および中務佑治准教授（8QLYHUVLW\RI2[IRUG）との共同研究に基づいた内容であり、両氏に感謝いたします。本研究の一部は、-67 さきがけ（課題番号：-30-350）、-636 科研費（課題番号：-3.、-3+）、学際大規模情報基盤共同利用・共同研究拠点（-+3&1）、および、革新的ハイパフォーマンス・コンピューティング・インフラ（+3&,）（課題番号：MK）の支援を受けています。スーパーコンピューティングニュース
- 55 -

Vol. 26, No.22024

D %'(&2（ ノード）



E 2%&;（ ノード）


図 ：+45&3 に対する速度向上（𝑚𝑚 = 16777216）。

スーパーコンピューティングニュース
- 56-

Vol. 26, No.22024

D %'(&2（ ノード）



E 2%&;（ ノード）

図 ：部分的な 45&3（𝑄𝑄の先頭から  の列のみを計算する場合）における

+45&3 に対する速度向上（𝑚𝑚 = 16777216）。スーパーコンピューティングニュース
- 57 -

Vol. 26, No.22024

参 考 文 献
>@深谷猛 大規模分散並列環境におけるコレスキー45 型アルゴリズムによる縦長行列の列ピボット付き 45 分解の性能評価東京大学情報基盤センタースーパーコンピューティン
グニュース9RO1R  SS>@7)&KDQ5DQNUHYHDOLQJ45IDFWRUL]DWLRQV/LQHDU$OJHEUD$SSO9RO
 SS

>@* *ROXE 1XPHULFDO PHWKRGV IRU VROYLQJ OLQHDU OHDVW VTXDUHV SUREOHPV 1XPHU
0DWK9RO  SS–>@6&KDQGUDVHNDUDQDQG,&),SVHQ2Q5DQN5HYHDOLQJ)DFWRUL]DWLRQV6,$0-
0DWUL[$QDO$SSO9RO  SS–>@6&KDQGUDVHNDUDQDQG,&),SVHQ2Q5DQN5HYHDOLQJ)DFWRUL]DWLRQV6,$0-
0DWUL[$QDO$SSO9RO  SS–>@3 %XVLQJHU DQG * + *ROXE /LQHDU OHDVW VTXDUHV VROXWLRQV E\ +RXVHKROGHUWUDQVIRUPDWLRQV1XPHU0DWK9RO  SS–>@0 *X DQG 6 & (LVHQVWDW (IILFLHQW $OJRULWKPV IRU &RPSXWLQJ D 6WURQJ 5DQN
5HYHDOLQJ45)DFWRUL]DWLRQ6,$0-6FL&RPSXW9RO  SS–>@7)XND\D<1DNDWVXNDVD<<DQDJLVDZDDQG<<DPDPRWR&KROHVN\45$6LPSOH
DQG&RPPXQLFDWLRQ$YRLGLQJ$OJRULWKPIRU&RPSXWLQJD7DOO6NLQQ\45)DFWRUL]DWLRQ
RQD/DUJHScale Parallel System, ScalA’14, pp. 31–>@<<DPDPRWR<1DNDWVXNDVD<<DQDJLVDZDDQG7)XND\D5RXQGRII(UURU$QDO\VLVRIWKH&KROHVN\45$OJRULWKP(71$9RO  SS–>@ 7 )XND\D 5 .DQQDQ < 1DNDWVXNDVD < <DPDPRWR DQG < <DQDJLVDZD6KLIWHG
&KROHVN\45IRU&RPSXWLQJWKH45)DFWRUL]DWLRQRI,OO&RQGLWLRQHG0DWULFHV6,$0
-6FL&RPSXW9RO  SS$–$>@ 深谷猛縦長行列の 45 分解に対する各種アルゴリズムの比較：2DNIRUHVW3$&6 上での性能評価東京大学情報基盤センタースーパーコンピューティングニュース9RO1R
  SS
>@ 7 )XND\D 'LVWULEXWHG 3DUDOOHO 7DOO6NLQQ\ 45 )DFWRUL]DWLRQ 3HUIRUPDQFH(YDOXDWLRQRI9DULRXV$OJRULWKPVRQ9DULRXV6\VWHPV3'&$7 /1&69RO SS>@ 1-+LJKDP$FFXUDF\DQG6WDELOLW\RI1XPHULFDO$OJRULWKPVQGHG6,$0
>@ 7 )XND\D < 1DNDWVXNDVD DQG < <DPDPRWR $ &KROHVN\ 45 W\SH DOJRULWKP IRUFRPSXWLQJ WDOOVNLQQ\45 IDFWRUL]DWLRQ ZLWKFROXPQSLYRWLQJ ,3'36  DFFHSWHG >@ 5 &XQKD ' %HFNHU DQG - 3DWWHUVRQ 1HZ 3DUDOOHO 5DQN5HYHDOLQJ  45)DFWRUL]DWLRQ$OJRULWKPV(XUR3DUSS–>@ - $ 'XHUVFK DQG 0 *X 5DQGRPL]HG 3URMHFWLRQ IRU 5DQN5HYHDOLQJ 0DWUL[)DFWRUL]DWLRQVDQG/RZ5DQN$SSUR[LPDWLRQV6,$05HY9RO  SS–

スーパーコンピューティングニュース- 58-Vol. 26, No.22024