Development of a hierarchical parallel numerical algorithm for saddle point problems

鞍点问题的分层并行数值算法的开发

基本信息

批准号：
20K11840
负责人：
多田野寛人
金额：
$ 2.66万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

鞍点型と呼ばれる連立一次方程式は，2行2列のブロック行列を係数行列にもつ連立一次方程式であり，同方程式は様々な分野において現れる．係数行列の左上ブロックの行列が良条件であったとしても，右上，左下ブロックの行列の列数，行数が多くなると，クリロフ部分空間反復法の収束性が悪化し，求解が困難となる．この状況を打破するために，我々は同方程式のブロック構造を用いた数値解法（以下，提案法）を構築した．提案法では同方程式を直接解くのではなく，左上ブロック行列を係数行列とする複数右辺連立一次方程式の求解を介し，その解行列を用いて鞍点型連立一次方程式の解ベクトルを求める．この複数右辺連立一次方程式は，解くべき鞍点型連立一次方程式よりも求解が容易であり，ブロッククリロフ部分空間反復法を適用することで計算時間，反復回数の両面で効率的に求解が可能である．さらに，各右辺ベクトルは互いに依存関係がないことから分割が可能であるため，この性質を利用することで同時求解可能な複数の方程式に分割でき，分割された各方程式も並列に求解できる．よって，提案法は階層型の並列性をもつ．2022年度は特に，提案法の高速化を行うために，GPUクラスタにおける提案法の並列コード実装，及び性能評価を行った．複数右辺連立一次方程式の右辺ベクトルはMPIを用いて分割され，分割された各方程式は各MPIプロセスで解かれる．本研究では各MPIプロセスにGPUを1台割り当て，GPUで複数右辺連立一次方程式の求解を行った．また，鞍点型連立一次方程式の解ベクトルの計算には小規模連立一次方程式を解く必要があるが，この部分もGPUで計算することで高速化を図った．性能評価は筑波大学計算科学研究センターのスーパーコンピュータ「Cygnus」の計算ノードを最大56ノード利用して行い，GPU版コードはCPU版コードよりも十分高速であることを確認した．

称为鞍点型的线性方程组是系数矩阵为2×2分块矩阵的线性方程组，这些方程出现在各个领域中。即使系数矩阵左上块中的矩阵条件良好，随着右上和左下块中矩阵的列数和行数增加，Krylov子空间迭代法的收敛性变差，解变为难的。为了克服这种情况，我们使用同一方程的块结构构造了一种数值求解方法（以下简称所提出的方法）。该方法不是直接求解同一个方程，而是以左上分块矩阵为系数矩阵求解多个右侧联立线性方程组，并利用解矩阵求线性方程组鞍点系统的解向量方程。这种多重右侧线性方程组比要求解的鞍点线性方程组更容易求解，并且通过应用分块Krylov子空间迭代方法，无论在计算时间还是求解次数上都可以高效地求解。迭代．．此外，由于每个右侧向量彼此之间没有依赖关系，因此可以被划分，因此利用这个性质，可以将其划分为多个可以同时求解的方程，并且每个划分的方程也可以并行求解。因此，所提出的方法具有层次并行性。特别是在 2022 财年，我们在 GPU 集群上实现了所提出方法的并行代码，并评估了其性能，以加快所提出方法的速度。使用 MPI 对多个右侧联立线性方程的右侧向量进行除法，并在每个 MPI 过程中求解每个除法方程。在本研究中，我们为每个 MPI 进程分配一个 GPU，并使用 GPU 求解多个右侧联立线性方程。另外，计算鞍点线性方程组的解向量需要求解一个小的线性方程组，但这部分也是使用GPU计算的，以加快计算速度。使用筑波大学计算科学中心的超级计算机“Cygnus”的多达 56 个计算节点进行性能评估，并确认 GPU 版本的代码比 CPU 版本的代码足够快。