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

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

基本信息

批准号：
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年度は，実対称帯行列を（分割統治法が適用可能な）半帯幅の小さい実対称帯行列に変換するアルゴリズムに関する研究を実施した．本研究では既存の変換アルゴリズムの計算量を決定するパラメータの厳密最適化が低いコストで実行可能であることを陽に示した．またそのようなパラメータの厳密最適化を行ったときの変換アルゴリズムの計算量および実行時間を最新の計算機で評価し，その有効性を明らかにした．

在这个研究项目中，我们正在研究改进矩阵的特征值计算方法，称为分而治之法。分而治之法是寻找实对称三对角矩阵和小半带宽实对称带状矩阵等矩阵的标准特征值和标准特征向量的强大特征值求解方法之一。三对角矩阵最经典的分治法在事实上的标准矩阵计算库LAPACK中作为特征值求解器实现，并广泛应用于各种科学和工程计算软件中。尽管分治法很重要，但它也存在许多问题，例如其算法中称为紧缩的过程的行为、带状矩阵分治法中项的处理顺序以及如何利用生成划分树时划分点的自由度还有很多问题没有完全阐明。为此，有必要明确分治法的本质，重点关注这几点。此外，由于分治法的原理，适用的矩阵不限于实对称三对角矩阵或小半带宽的实对称带状矩阵，而是可以适用于更广泛的矩阵。因此，通过开发可应用分治法的新矩阵类，以及研究分治法可应用的矩阵类的变换方法，扩大分治法的应用范围非常重要。可以采用并攻法。 2022年，我们研究了将实对称带状矩阵转换为小半带宽实对称带状矩阵（可以采用分治法）的算法。在这项研究中，我们明确证明了可以以低成本对确定现有转换算法的计算复杂性的参数进行严格优化。我们还评估了使用最新计算机对这些参数进行严格优化时转换算法的计算复杂度和执行时间，并阐明了其有效性。