分散メモリ型並列機における並列固有値ソルバ
対称密行列を対象とし、二分法＋逆反復法や直交化処理を含む並列実装を研究。修士論文では大規模固有値問題ソルバの分散メモリ並列機上での実装を体系化しました。
片桐孝洋・金田康正「並列固有値ソルバーの実現とその性能」(1997)、「並列固有値ソルバーの実現とその並列性の改良」(JSPP'98)。
Overview
固有値計算は「アルゴリズム選択」と「実装選択」が性能を決める
実対称・Hermitian密行列の直接法では、一般に三重対角化、三重対角固有値問題、固有ベクトルの逆変換という複数段階を通ります。各段階には複数のアルゴリズム、データ分散、通信方式、CPU/GPUカーネル、精度、並列度の選択肢があり、固有値計算は自動チューニングとAIエージェントの非常に自然な対象です。
1. ReductionHouseholder三重対角化
1-stage / 2-stage
1-stage / 2-stage
2. Tridiagonal EVPQR / Divide & Conquer
Bisection / MRRR
Bisection / MRRR
3. Back TransformationHouseholder vectors
通信・メモリ・再利用
通信・メモリ・再利用
4. Verification残差・直交性
精度・再現性
精度・再現性
研究上のポイント： 行列サイズ、固有値だけか固有ベクトルも必要か、必要固有対数、固有値分布、計算機アーキテクチャ、MPIプロセス数、GPU数などによって最適な方式は変わります。したがって「一つの最高速実装」よりも、状況に応じて方式を選択・変形する仕組みが重要になります。
Research Evolution
片桐孝洋の固有値計算研究：並列化からAgentic HPCへ
研究の中心課題は一貫して「その時代の計算機で、数値的信頼性を保ちながら固有値計算を速くするには何を自動化すべきか」です。
Householder三重対角化の超並列化
HITACHI SR2201の1024 PEを用い、密実対称固有値問題に対するHouseholder三重対角化を通信量の観点から再設計。(Cyclic, Cyclic)分散と通信複雑度を抑える方式により、1024 PEでScaLAPACKに対して約2～5倍の高速化を報告しました。
ABCLib：固有値ソルバそのものを自動チューニング
ABCLib（Automatically Blocking-and-Communication adjustment Library）を提案し、密実対称固有値ソルバABCLib_DRSSEDへ発展。ブロック長、ループ展開、通信実装、データ分散などを性能パラメータとして扱い、FIBERの最適化タイミングと連携しました。
三重対角固有値問題のアルゴリズム自体をRuntime Auto-Tuning
Multi-section with Multiple Eigenvalues（MME）法を提案し、実行時に実装パラメータを選択。アルゴリズムの中に自動チューニングを組み込む方向へ研究を拡張しました。
ペタ・エクサスケールを意識した通信削減
Householderベクトルの保持と逆変換を見直し、process-grid-free方式やcommunication splitting multicasting、非ブロッキングMPI、ハイブリッドMPIを利用して超並列環境での通信コストを削減しました。
T. Katagiri and S. Itoh, “A Massively Parallel Dense Symmetric Eigensolver with Communication Splitting Multicasting Algorithm,” VECPAR 2010. / Communication Avoiding and Reducing Algorithm for Symmetric Eigenproblem for Very Small Matrices.
高性能だけでなく「精度保証」もチューニング対象へ
JHPCN共同研究 “Developing Accuracy Assured High Performance Numerical Libraries for Eigenproblems” で、高精度・精度保証アルゴリズム、高性能実装、自動チューニングを統合する研究を推進しました。
機械学習で固有値ライブラリのテストを最適化
LAPACK固有値計算ルーチンのテスト系列を対象に、故障を早期に検出できるテストを機械学習で予測し、テスト実行順序を最適化する研究へ展開。性能だけでなく、検証・品質保証工程もAIの対象になっています。
Agentic Eigensolver Engineering
生成AI・AIエージェントと自動チューニングを統合し、問題分析、アルゴリズム選択、コード生成、実機ベンチマーク、数値検証、再最適化、知識蓄積を閉ループ化する研究テーマへ接続します。
Householder Parallelization
Householder法の並列化：研究の原点
密実対称固有値問題では、Householder変換による三重対角化が大きな計算コストを占めます。演算量だけでなく、ベクトル・行列データの通信、Householderベクトルの保持、逆変換時の通信がスケーラビリティを左右します。
通信量を中心にアルゴリズムを再設計
2001年のParallel Computing論文では、従来の対称性利用方式だけに拘らず、MPP環境で通信複雑度を抑えるHouseholder三重対角化方式を採用しました。
(Cyclic, Cyclic) 分散
多数PE環境でロードバランスと通信を両立するデータ分散を利用。1024 PE SR2201上でScaLAPACKとの比較評価を行いました。
逆変換とHouseholderベクトル
2010年前後には、Householderベクトルの重複保持によるメモリ増加と通信削減のトレードオフを明示的に扱い、communication splitting multicastingへ展開しました。
1024 PEHITACHI SR2201で評価
約2–5×ScaLAPACK比の高速化（2001論文）
Communication演算量だけでなく通信複雑度を重視
Memory Trade-offHouseholder vector保持と速度の両立
ABCLib & Auto-Tuning
ABCLib：固有値計算を「自動で適応するソフトウェア」へ
ABCLibは Automatically Blocking-and-Communication adjustment Library の略で、並列数値計算ライブラリ自身がブロッキング、通信、実装方式を計算機環境に合わせて調整する構想です。固有値計算パッケージABCLib_DRSSEDは、この考え方を実際の並列固有値ソルバに組み込みました。
ABCLib_DRSSED
実対称密行列固有値問題を対象とする並列ソルバ。Before Execute-time Optimization（BEO）、データ分散のロードバランシング、通信・計算パラメータの適応を組み込みました。
Parallel Computing論文 →ABCLibScript
ブロック長、loop unrolling、アルゴリズム選択などの自動チューニング知識をディレクティブとして記述する言語。数値計算専門家の知識をソフトウェアへ埋め込む仕組みでした。
Parallel Computing論文 →FIBER
Install-time / Before Execute-time / Run-time の複数タイミングで最適化を実行する枠組み。現在のAIエージェントで言えば、事前学習・起動時適応・実行中適応を役割分担する設計に近い発想です。
自動チューニングソフトウェア工学 →ABCLibからAIエージェントへの連続性： ABCLibScriptでは「専門家がチューニング知識を記述」しました。AIエージェント時代には、その知識をLLM/RAG/Knowledge Graphから取得し、実機評価結果を見ながら自動的に仮説生成・実装・検証・更新する方向へ拡張できます。
Modern Eigensolver Landscape
2026年の並列固有値計算：CPUだけでなくGPU・異種計算・自動チューニングへ
1999年版で中心だったScaLAPACKは現在も基準となるライブラリですが、現代のHPCではGPU、2-stage reduction、タイルアルゴリズム、異種計算、組込みautotuningが重要になっています。疎行列側ではKrylov法を中心に、大規模分散・GPU対応が進んでいます。
| ライブラリ | 主対象 | 現在の特徴 | 自動化との接点 |
|---|---|---|---|
| ScaLAPACK | 分散メモリ密行列 | 対称/Hermitian・非対称固有値問題、D&C、MRRR等 | 基準実装・vendor最適化・process grid選択 |
| ELPA | 大規模対称/Hermitian密行列 | 1-stage/2-stage、NVIDIA/AMD/Intel GPU、MPI/OpenMP | ライブラリ自身がautotuning機構を備える |
| SLATE | Exascale向け分散密行列 | MPI/OpenMP + CUDA/HIPによるGPU加速、ScaLAPACK機能を現代化 | タイル・デバイス配置・通信/計算重畳の探索 |
| SLEPc | 大規模疎行列・構造化固有値問題 | PETSc上のMPI並列、CUDA/HIP GPU、標準/一般化/非線形固有値問題等 | 反復法・前処理・spectral transformationの選択 |
重要な変化： 現代の固有値ソルバでは「アルゴリズム名」だけで最適解を決められません。1-stage/2-stage、GPU有無、MPI task/GPU mapping、process grid、block size、kernel、固有ベクトル要否など、実行時構成を含む大きな設計空間が存在します。ELPAが組込みautotuningを備えること自体が、この問題の重要性を示しています。
Agentic Eigensolver Engineering
自動チューニング × AIエージェントで、固有値ソルバの設計そのものを自律化する
次の研究段階では、単一の性能パラメータを探索するだけでなく、「問題の性質を理解し、アルゴリズムを選び、コードを生成し、実機で試し、数値的正しさまで検証し、知識として残す」一連の工程をAIエージェントで閉ループ化します。
Problem Agent行列種・サイズ・スペクトル・精度要求を分析
Solver AgentQR/D&C/MRRR/Krylov等から候補選択
Code AgentMPI/OpenMP/CUDA・library APIを生成
Performance Agent実機測定・Profiler・Auto-Tuning
Verification Agent残差・直交性・精度・再現性を検証
Knowledge Agent結果をMemory/RAG/Knowledge Graphへ蓄積
Analyze → Select → Generate → Run → Verify → Learn → Re-design
- 1. Solver Portfolio Agent： 密/疎、対称/非対称、全固有対/部分固有対、固有ベクトル要否に応じてdirect/iterative solverを選ぶ。
- 2. Spectrum-Aware Agent： 固有値分布、gap、cluster、条件数等を低コストに推定し、アルゴリズムと停止条件を変える。
- 3. Architecture-Aware Agent： CPU/GPU/複数GPU/分散メモリに応じてELPA・SLATE・ScaLAPACK・SLEPc等を使い分ける。
- 4. Auto-Tuning Agent： block size、process grid、MPI/OpenMP比、GPU mapping、1-stage/2-stage、kernelを実機探索する。
- 5. Numerical Verification Agent： 残差、直交性、backward error、精度、混合精度の妥当性を評価し、性能だけの誤最適化を防ぐ。
- 6. Test Engineering Agent： LAPACK等のテスト系列をMLで優先順位付けし、故障検出までの時間を短縮する。
- 7. Communication Agent： Householder変換、逆変換、collective/nonblocking通信、overlap、データ複製のトレードオフを探索する。
- 8. Algorithm Discovery Agent： 既存solverのパラメータ調整に留まらず、通信回避・混合精度・新しい分割方式などの候補を生成して実験する。
研究テーマとしての新規性： ABCLibが「人間が記述したチューニング知識を自動適用する」枠組みだったのに対し、Agentic Eigensolver Engineeringでは、AIエージェントが知識を獲得・統合し、実機ベンチマークと数値検証を根拠にソルバ構成を更新します。これはHPC-GENIE / ACRUで進めているAgentic HPCの数値線形代数への具体化です。
Selected Publications
固有値計算・ABCLib・自動チューニングに関する主な成果
- 1997並列固有値ソルバーの実現とその性能 — 片桐孝洋，金田康正，情報処理学会研究報告 97-HPC-69, pp.49–54.
- 1998並列固有値ソルバーの実現とその並列性の改良 — 片桐孝洋，金田康正，JSPP'98論文集, pp.223–230.
- 2001An Efficient Implementation of Parallel Eigenvalue Computation for Massively Parallel Processing — T. Katagiri, Y. Kanada, Parallel Computing 27(14), 1831–1845.
- 2006ABCLibScript: a directive to support specification of an auto-tuning facility for numerical software — T. Katagiri, K. Kise, H. Honda, T. Yuba, Parallel Computing 32(1), 92–112.
- 2006ABCLib_DRSSED: A parallel eigensolver with an auto-tuning facility — T. Katagiri, K. Kise, H. Honda, T. Yuba, Parallel Computing 32(3), 231–250.
- 2007Automatic Performance Tuning for the Multi-section with Multiple Eigenvalues Method for Symmetric Tridiagonal Eigenproblems — T. Katagiri, C. Vömel, J. W. Demmel, PARA 2006 selected papers.
- 2010ペタフロップス環境における小規模行列用対称密行列固有値ソルバに向けて―逆変換の改良 — 片桐孝洋，情報処理学会論文誌 ACS 3(2), 1–8.
- 2011A Massively Parallel Dense Symmetric Eigensolver with Communication Splitting Multicasting Algorithm — T. Katagiri, S. Itoh, LNCS 6449, 139–150.
- 2014/24A Communication Avoiding and Reducing Algorithm for Symmetric Eigenproblem for Very Small Matrices — T. Katagiri, J. Iwata, K. Uchida. ABCLib Working Notes (2014); arXiv re-submission (2024).
- 2019–21Developing Accuracy Assured High Performance Numerical Libraries for Eigenproblems — JHPCN共同研究.
- 2024LAPACKを用いた固有値計算におけるテストシーケンスの最適化 — 樫村寛大，森崎修司，片桐孝洋，河合直聡，永井亨，星野哲也.
- 2026A Trial on Optimizing Test Sequences for LAPACK Eigenvalue Computation Routines using Machine Learning — H. Kashimura, T. Katagiri, S. Morisaki, D. Mukunoki, T. Hoshino, SCA/HPCAsia 2026.
Historical Archive
1999年版「並列固有値ソルバのページ」の内容
以下は元ページの技術内容を、表現とHTMLだけ整理して保存したものです。当時のリンクには現在利用できないものもあります。
密行列・疎行列の当時のアルゴリズム整理を表示
密行列
対称行列（標準固有値問題）
- 並列QR法
- Chinchalkarらは、処理対象の密行列を三重対角行列に変換後、三重対角行列に対するQR法で全固有値・固有ベクトルを求めた。分散方式は列方向に分散させる (*, Cyclic) 分割方式を用いる。
- 並列分割統治法（Divide-and-Conquer Method）
- 三重対角固有値問題に対する代表的な直接法の一つ。現在もLAPACK/ScaLAPACK系ライブラリで重要な選択肢である。
- 二分法 + 逆反復法
- 相似変換により密行列を三重対角行列に変換し、二分法で固有値を求め、逆反復法で固有ベクトルを収束させ、最後に元の行列の固有ベクトルへ変換する。並列化では固有ベクトルの直交性を保証する再直交化処理が重要になる。1999年版ではLoら、DemmelらのScaLAPACK、Hendrickson/Jessup/Smith solver、および片桐らの並列ソルバを比較していた。ダウンロード可能な実装としてScaLAPACKのPDSYEVXを挙げていた。
- 二分法 + マルチカラー逆反復法
- 直野健、猪貝光祥、山本有作らによって開発された並列版逆反復法。固有ベクトルの直交処理から並列性を抽出する。
- 並列 Hessenberg QR法
- 密非対称行列をHessenberg形へ変換し、その後ダブルシフトQR法で固有値を求める。1999年版ではHenryとvan de GeijnによるマルチシフトQRとデータ分割、須田らによるデータ分割方式の改良を紹介していた。
疎行列
非対称行列
Arnoldi法：大規模疎非対称固有値問題に対する代表的Krylov部分空間法。現在はSLEPc等の並列ライブラリで、shift-and-invertや各種spectral transformationと組み合わせて利用される。
1999年版で挙げていた主な参考文献
- S. Chinchalkar and T. F. Coleman, “Computing Eigenvalues and Eigenvectors of A Dense Real Symmetric Matrix on the NCUBE 6400,” Cornell Theory Center Technical Report 91-074 (1991).
- S. Lo, B. Philippe, and A. Sameh, “A Multiprocessor Algorithm for the Symmetric Eigenvalue Problem,” SIAM J. Sci. Stat. Comput., 8(2), s155–s165 (1987).
- J. Demmel and K. Stanley, “The Performance of Finding Eigenvalues and Eigenvectors of Dense Symmetric Matrices on Distributed Memory Computers,” UT-CS-94-254.
- B. Hendrickson, E. Jessup, and C. Smith, “A Parallel Eigensolver for Dense Symmetric Matrices.”
- 片桐孝洋，金田康正「並列固有値ソルバーの実現とその性能」情報処理学会研究報告 97-HPC-69, pp.49–54 (1997).
- 片桐孝洋，金田康正「並列固有値ソルバーの実現とその並列性の改良」JSPP'98, pp.223–230 (1998).
- T. Katagiri, “A Study on Parallel Implementation of Large Scale Eigenproblem Solver for Distributed Memory Architecture Parallel Machines,” Master thesis, The University of Tokyo (1998).
- 直野健，猪貝光祥，山本有作「マルチカラー逆反復法による並列固有ベクトル計算」日本応用数理学会平成7年度会講演予稿集, pp.18–19 (1995).
- 直野健，猪貝光祥，山本有作「並列固有値ソルバーの開発と性能評価」JSPP'96, pp.9–16 (1996).
- G. Henry and R. van de Geijn, “Parallelizing the QR algorithm for the unsymmetric algebraic eigenvalue problem: myths and reality,” SIAM J. Sci. Comput., 17(4), 870–883 (1996).
- R. A. van de Geijn, “Storage schemes for Parallel Eigenvalue Algorithms,” NATO ASI Series F70, 639–647 (1991).
- 須田礼二，西田晃，小柳義夫「並列Hessenberg QR法のための新しいデータ分割方式とAP1000+への効率的実装」JSPP'97, pp.377–384 (1997).
Related Pages
関連する研究ページ
自動チューニング工学（ATE）
固有値計算を含む数値ソフトウェアを、性能可搬性の観点から体系化する研究概念。
PAE.html →自動チューニングソフトウェア工学
仕様設計、プログラミング、最適化、知識探索という開発サイクルからAuto-Tuningを捉える。
AutoSE.html →生成AI・AIエージェント × HPC
LLM、マルチエージェント、実機性能フィードバック、自律研究を含む現在の研究テーマ。
genai-hpc.html →