分割統治法の高度化による中間形行列に対する高性能固有値ソルバの実現

改进分治法实现中间矩阵高性能特征值求解器

基本信息

批准号：
22K12047
负责人：
廣田悠輔
金额：
$ 2.16万
依托单位：
University of Fukui
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K12047/
关键词：
高性能計算固有値問題分割統治法帯行列

项目摘要

本研究課題では，分割統治法と呼ばれる行列の固有値計算手法の高度化に関する研究を行っている．分割統治法は実対称三重対角行列や半帯幅の小さい実対称帯行列などの行列の標準固有値および標準固有ベクトルを求める強力な固有値解法の一つである．最も古典的な三重対角行列向け分割統治法はデファクトスタンダード行列計算ライブラリLAPACK の固有値ソルバとして実装され，様々な科学技術計算ソフトウェアで広く使用されている．分割統治法はその重要性にもかかわらず，そのアルゴリズム中のデフレーションと呼ばれる処理の振る舞い，帯行列向け分割統治法における項の処理順序，分割ツリー生成における分割点の自由度の活用法など，十分明らかにされていない点が多数存在する．このため，これらの点を中心に分割統治法の性質を明らかにする必要がある．また，分割統治法の原理上，適用可能な行列は実対称三重対角行列や半帯幅の小さい実対称帯行列に限定されず，より広いクラスの行列に適用できる可能性がある．したがって，分割統治法の適用可能な新たな行列クラスの開発や，分割統治法の適用可能な行列クラスへの変形手法の研究により，分割統治法の応用範囲を拡大することも重要である．2022年度は，実対称帯行列を（分割統治法が適用可能な）半帯幅の小さい実対称帯行列に変換するアルゴリズムに関する研究を実施した．本研究では既存の変換アルゴリズムの計算量を決定するパラメータの厳密最適化が低いコストで実行可能であることを陽に示した．またそのようなパラメータの厳密最適化を行ったときの変換アルゴリズムの計算量および実行時間を最新の計算機で評価し，その有効性を明らかにした．

该研究主题正在进行有关称为分裂和征服方法的矩阵特征值计算方法的进步的研究。该分区征服方法是在矩阵中找到标准特征值和标准特征向量的强大特征值解决方案之一，例如真实的对称三角形矩阵和带有半波段宽度的真实对称带矩阵。在事实上，最古典的Tridiagonal分区征服方法是在事实上标准矩阵计算库Lapack中作为特征值求解器实施的，并广泛用于各种科学和技术计算软件中。尽管它的重要性，但仍未完全澄清很多点，例如算法中称为通缩的过程的行为，频段矩阵征服方法中的术语处理顺序以及使用分区树产生的分区自由度。因此，有必要阐明分裂和征服方法的性质，重点关注这些要点。此外，在划分和征服的原理中，适用的矩阵不仅限于具有小的半波段宽度的真实对称的三角形矩阵或真实的对称带矩阵，但可能适用于更宽的矩阵。因此，通过开发可以应用于分区和征服方法的新矩阵类别以及研究将除法和征服方法转换为适用矩阵类的方法，以及研究方法，扩大分裂和征服方法的应用范围也很重要。在2022年，我们对将真实的对称带矩阵转换为小型，半波段宽度（可以应用分裂和征服方法）的算法进行了研究。这项研究明确表明，可以以低成本执行确定现有转换算法的计算复杂性的参数的严格优化。此外，当精确优化此类参数时，使用最新计算机评估了转换算法的计算量和执行时间，并阐明了其有效性。