JSIAM Online Magazine


2022年6月以降、JSIAM Online Magazine の新規の記事は https://jsiam.org/online_magazine で公開されます。本ページは今後更新されなくなります。

書評

『計算力学レクチャーコース 固有値計算と特異値計算』一般社団法人 日本計算工学会 編

山本 有作



固有値・特異値の計算は,構造解析,電子状態計算,信号処理など,様々な科学技術計算の中核をなす計算である.近年重要性を増しているデータ科学においても,主成分分析や線形判別分析をはじめ,スペクトラルクラスタリングやグラフ分割など,固有値・特異値計算はその応用範囲を大きく広げている.これらの応用では,大規模な固有値・特異値問題を高速・高精度に解くことが求められており,そのニーズに応じて,近年,様々な新しいアルゴリズムが登場している.しかし,固有値・特異値計算の定評あるテキストの多くは出版から20年以上が経過しており( [1],[2],[3]など),一般のユーザが最新の研究成果を概観できる新しいテキストが待望されていた.本書は,その期待に応えるべく,長谷川秀彦教授をはじめとする我が国の代表的な固有値・特異値計算分野の研究者によって共同執筆された教科書である.

 

本書は,第1章「あらまし」,第2章「密行列の固有値計算」,第3章「疎行列の固有値計算」,第4章「櫻井-杉浦法」,第5章「反復改良法」,第6章「特異値問題」,第7章「高精度特異値分解」の7章からなる.

 

第2章,第3章はそれぞれ密行列,疎行列の固有値計算法の基礎であり,標準的な内容ながらも,最近の進展を取り込んだ解説となっている.第2章では,実対称固有値問題の解法を重点的に扱っている.実対称固有値問題では,行列を直交変換により3重対角行列に変換した後,3重対角行列の固有値・固有ベクトルを反復法により求めるのが標準的な手法である.しかし,3重対角化の計算はキャッシュメモリの利用効率が低く,かつ並列化した場合に通信が頻発する計算パターンとなっており,大規模計算での性能ボトルネックとなっていた.本章では,この問題を解決する高性能計算向けの3重対角化手法を詳しく解説するとともに,3重対角行列の固有値・固有ベクトル計算についても,従来法の計算量をオーダーの意味で改善できる可能性を持つMRRR(Multiple Relatively Robust Representations)アルゴリズムを紹介している.第3章では,大規模疎行列の固有値計算の標準的な手法であるランチョス法,アーノルディ法,ヤコビ-ダビッドソン法に加えて,物性物理などの分野で評価が高いLOBPCG(Locally Optimal Block Preconditioned Conjugate Gradient)法についても解説している点が類書にない特色である.特に,LOBPCG法のプログラムが出版社のウェブサイトからダウンロード可能となっているのは貴重である.なお,ランチョス法/アーノルディ法については,本章で解説されているのは原型に近い形であるが,標準的なライブラリARPACKに実装されて現在広く使われているのは,陰的リスタート型ランチョス法/アーノルディ法と呼ばれる,メモリ量と計算量を削減した改良型のアルゴリズムである.これについては[4]に解説がある.

 

第4章は,我が国発の並列型固有値解法である櫻井-杉浦法の解説である.櫻井-杉浦法は,レゾルベント(A - zI)-1の複素周回積分を用いたフィルタにより,求めたい固有ベクトル成分を抽出する手法である.数値計算では,この複素周回積分を数値積分により近似するが,各標本点におけるレゾルベントの計算は独立に行えるため,本手法は大粒度並列性(独立に計算できる単位が大きいこと)を持ち,超並列環境に極めて適した手法となる.櫻井-杉浦法はz-Paresというソフトウェアに実装され,様々な分野での超大規模固有値解析に成果を上げている.櫻井-杉浦法の特筆すべき点として,非線形固有値問題にも適用でき,複素平面上の指定された領域内にある固有値を原理的にはすべて求められるという点が挙げられる.このような特長を持つ非線形固有値問題の解法は,他にないのではないかと思われる.なお,櫻井-杉浦法の最近の進展については,耐故障型アルゴリズムへの発展や非線形固有値問題への拡張を含め,[5]にいくつかの論文が収録されている.

 

第5章は,固有値問題に対する反復改良法を扱っている.反復改良とは,近似的な固有値・固有ベクトルを入力として,何らかの反復計算により,より精度の高い固有値・固有ベクトルを求めることである.この問題について,最近,実対称固有値問題向けの効率的なアルゴリズムが荻田と相島によって提案された(日本応用数理学会2020年度論文賞(JJIAM部門)受賞).本章では,この手法を中心に,連立1次方程式に対する反復改良にも触れつつ解説を行っている.反復改良法は,固有値・固有ベクトルの精度を高めるためだけでなく,時間に依存する行列A(t)の固有値・固有ベクトルを追跡する問題にも応用可能であり,今後の発展が期待される.

 

第6章,第7章では,特異値の計算を扱う.まず第6章で特異値の性質と標準的な計算法を述べた後に,第7章では,高精度特異値分解法を紹介している.特異値計算の標準的なアルゴリズムでは,まず入力行列を両側直交変換により2重対角行列に変換した後,2重対角行列の特異値と特異ベクトルを反復法により求める.第7章ではこの後半の部分を扱っており,その中心となるのはqd(quotient difference)法と呼ばれるアルゴリズムである.qd法は,固有値計算手法であるLR法と数学的には等価であるが,式変形の工夫により減算なしで計算を実行でき,その結果,2重対角行列の任意の特異値を高い相対精度で計算できる.この性質は,QR法など,他の2重対角行列用の特異値計算手法には見られないものである.また,qd法に原点シフトを導入して収束を加速した手法としてdqds法とoqds法があり,qd法の高精度性はこれらの手法にも受け継がれている.本章の著者らのグループは,特異値・特異ベクトルの高精度計算法に関して長年研究を行っており,本章にはその知見が凝縮されている.また,著者らが公開しているコードLAPROGNCについても紹介されている.

 

以上,本書の内容について,類書に見られない特色あるトピックを中心に概観してきた.これからわかるように,本書は固有値・特異値計算の様々な側面について,最新の研究成果を踏まえつつバランスよく記述しており,研究者や科学技術計算分野のユーザに広く勧められる本となっている.固有値・特異値計算の分野は,最近でも進展が著しく,特異値分解に対する確率的近似アルゴリズム,特異値分解の高次元版としての各種のテンソル分解,無限次元行列の固有値問題に対する数値解法,量子計算/量子アニーリングを援用した固有値計算法など,数多くの興味深い研究テーマが目白押しである.これらのテーマについても,近い将来,まとまった書物の形で手軽に読めるようになることを期待したい.

 

参考文献

[1] B. N. Parlett: The Symmetric Eigenvalue Problem, SIAM, 1998.

[2] Z. Bai et al.: Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, 1987.

[3] J. K. Cullum and R. A. Willoughby: Lanczos Algorithms for Large Symmetric Eigenvalue Computations : Vol. I: Theory, SIAM, 2002.

[4] 金田行雄, 笹井理生 (監修), 張紹良 (編): 20世紀のトップ10アルゴリズム, 共立出版, 2022.

[5] T. Sakurai et al.: Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing, Springer, 2017.



やまもと ゆうさく
電気通信大学
[Article: J2112A]
(Published Date: 2022/02/10)