GPA: 基于多面体网格几何并行性的矩阵特征多项式异步因式分解器

孙家昶教授最新发表在 《中国科学：数学》2023年第6期的论文研究空间三维多面体网格中相应本性的异步并行算法，提出通过几何(G)网格(G)作预变换(P)，将大型偏微分方程(P)的代数特征值问题(A)化为若干块对角子问题的异步(A)并行算法（简称GPA算法）。GPA算法将在国产并行机上使用，结合应用进一步优化程序及算法。

随着我国E-级高性能计算系统与应用的发展，求解超大规模数学物理离散方程性能效率低下的瓶颈已日益突出。解线性方程组预条件子算法已经在求解偏微分方程 (PDE) 的离散代数系统高性能计算中取得巨大成功。特征值高性能算法的研究相对迟缓，远不能满足 E-级高性能计算应用的需求。特征值问题在物理上反映谱分布，在特定条件下，计算时可用到多变量 Fourier变换。大型PDE特征值高效并行计算在数学上要用到分析、代数及几何等多学科的知识。在经典计算数学学科中，特征值计算属于代数高次方程求根的范畴，如何准确估计高阶特征值的重数及分离度历来是计算数学中的一个本质困难。然而，基于椭圆偏微分方程特征值问题的数学原理，构造有特色的高效并行算法来满足高性能计算应用的需求是有可能的，这也是作者多年的愿望（参见文献[1-2]）。

结合椭圆偏微分方程离散预条件子及区域分解等高效求解器的研究经验，我们对Jordan 标准型所依据的代数基本定理进行了再思考。我们发现并证明了以Laplace为代表的PDE扩散算子能保持两个具有不同几何对称性质子空间之间的正交关系（参见文献[1]）。

本文[3]提出 GPA 算法的主要思想是通过几何(G)网格(G)将偏微分方程(P)的大型代数离散矩阵(A)通过酉变换实现内在的并行算法:不直接调用“n次实多项式分解为一次多项式乘积的常规数学库函数”, 而从计算问题的源头出发，先把大块矩阵的特征值问题通过几何图形的因式分解得到低阶矩阵特征值问题，再异步调用相应的低阶数学库函数，从而大幅度减少计算量与通信开销, 实现整体高效的内在并行计算。

基于对常用的平面多边形网格（三角形、四边形、六边形及一般的m-正多边形网格） 及空间三维多面体网格的几何不变性的研究， 我们提出了相应本性的异步并行算法: 通过几何(G)网格(G)作预变换(P)，将大型偏微分方程(P)的离散代数特征值问题(A)化为若干块对角子问题的异步(A)并行算法（简称GPA算法）。

对于平面及空间网格，我们直接关心的不只是网格尺度h，更关注离散网格的整体几何信息，特别是各种对称性在坐标变换下的几何不变性，并力图利用这些内在的几何不变量构造该离散系统的几何预处理子框架，形成适用于某些大型稳态数学物理方程求解的内在异步并行算法。特别地，对于大型离散网格特征值问题，我们通过因式分解（实数域或复数域），尽量把离散的高阶广义特征值问题直接解耦分解为一批低阶问题异步并行计算求解。

对于一个给定的网格剖分，把自由度的两个不同排序之间的置换矩阵（每行、每列有一个元素为1 其余元素均为0 的方阵）称为“几何网格矩阵”。GPA 算法的基本思想是：通过几何对称性构造“几何网格矩阵”、实现与原矩阵几何对称规模相应的特征多项式异步并行因式分解算法。

以中国科学院数学与系统科学研究院院徽（Logo）为例：赵爽弦图是中国古代数学家证明勾股定理的历史明证，被定为2002年国际数学家大会的会标。在传统意义下该图可视为是简单的一组二维非传统的规则网格，至少有两种不同排序，如图1所示。12个节点按几何位置可分为三组：节点组I：(1,3,12,10)；节点组 II：(2,9,11,4)；节点组 III：(5,6,8,7)。

排序1 与排序2 之间可直接写出节点置换矩阵：

满足四阶幂等公式 。

该置换矩阵在实数域有三项因式分解

在复数域则有四项因式分解

找到置换矩阵的本征展开后，应用到相关矩阵的本征多项式计算。

首先考虑满足互易关系的一组带三参数的质量矩阵

为分别通过四个三阶特征向量的计算得到的的十二阶特征向量酉矩阵。相应的刚度矩阵与质量矩阵均与网格矩阵乘法可易，特征向量矩阵在刚度矩阵与质量矩阵意义下均为块正交：

于是十二阶广义特征多项式可分解为四个三次特征多项式的乘积

其中及分别为及前三个对角块矩阵。

GPA算法将在国产并行机上使用，结合应用进一步优化程序及算法。如条件具备即可通过与国内著名高性能计算软件平台合作研制相应的数学库函数，并将与几何多重网格算法结合，研制新一代的多重网格(M)并行因式分解算法MGPA。

【参考文献】

[1] Sun J C. Orthogonal piece-wise polynomials basis on an arbitrarytriangular domain and its applications. J Comput Math, 2001, 19: 55-66

[2] 孙家昶. 有关PDE本征问题数学模型与新型计算模式的设想. 国家973“新型计算模式”项目组第一次全体会议大会特邀报告, 2011.8.20

[3] 孙家昶. GPA: 基于多面体网格几何并行性的矩阵特征多项式异步因式分解器. 中国科学：数学, 2023, 53: 859-894

作者简介

孙家昶

中国科学院软件研究所研究员。孙家昶1970年代发明圆弧样条，应用于国产大飞机“运10”的外形设计，学术上曾参与苏步青教授开创的我国计算几何学；1980年代访美三年（耶鲁大学计算机系、加州大学洛杉矶分校数学系、Minnesota超级计算机研究所（MSI）等），研究特征值问题、奇性差分方法及区域分解并行算法；回国后先后组建中科院计算中心与软件所的并行计算学科，研制具有自主知识产权的数学库与油藏数值模拟等并行软件。2001年领衔获国家科技进步二等奖，2018年荣获第七届CSIAM苏步青应用数学奖。

他的研究方向包括计算机辅助几何设计、多元B样条、计算方法、区域分解、并行计算等。