(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211352681.9 (22)申请日 2022.11.01 (71)申请人 泰山学院 地址 271000 山东省泰安市岱岳区东 岳大 街525号 (72)发明人 孟静　冯昌利　牛立强　吴垚坤　 张智敏　李勃晔　 (74)专利代理 机构 济南圣达知识产权代理有限 公司 372 21 专利代理师 于凤洋 (51)Int.Cl. G06F 17/12(2006.01) G06F 17/16(2006.01) (54)发明名称 一种IDRstab算法高可扩展并行处理方法及 系统 (57)摘要 本发明提出了一种IDRstab算法高可扩展并 行处理方法及系统， 属于高性能计算技术领域， 步骤为环境初始、 数据划分、 块状正交对偶残差 向量生成、 初始块状向量生成和循环求解； 本发 明引入TSQR分解优化正交化过程， 通过循环移位 将并行TSQR分解与内积计算移位到同个同步点 上， 在同一个同步点上同时执行并行TSQR分解与 内积计算， 大大减少IDRstab算法的全局通信次 数， 克服现有IDRstab算法的全局通信耗时太长 的局限性， 提高算法的可扩展能力， 加快算法求 解速度， 使得用户能够快速使用算法求解实际应 用问题。 权利要求书2页 说明书10页 附图6页 CN 115408653 A 2022.11.29 CN 115408653 A 1.一种IDRstab算法高可扩展并行处理方法， 用于高置信度数值模拟中大型稀疏线性 方程组Ax=b的求 解， 包括以下步骤： 设置并行计算 参数值， 创建并行 执行环境； 将大型稀疏线性方程组Ax=b的系数矩阵A与右端向量b划分到每 个处理器上； 计算矩阵A与初始向量x0的矩阵乘积Ax0， 计算每个处理器的局部残差， 将所有处理器划 分成s个虚拟区域， 计算每 个虚拟区域的局部块状正交对偶残差向量； 生成初始块状向量； 循环迭代更新近似解、 残差、 块状正交向量与块状向量， 直到残差向量范数值小于拟定 的阈值， 停止循环， 输出解向量； 在块状正交向量的生成和更新中， 引入TSQR分解优化正交化过程， 对原算法IDRstab （s,l） 中的步骤进 行循环移位， 将并行TSQR分解与内积 计算调整在同一个同步点上， 在同一 个同步点上同时执 行并行TSQR分解与内积计算。 2.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述并 行计算参数值,包括处理器总数P、 双正交投影的次数s  、 GMRES多项式算子的个数l、 算法停 止阈值to l。 3.如权利 要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 将矩阵A 与右端向量b按 m行划分， 包括将矩阵的非零局部矩阵块 Cp、 Tp、 Dp与bp按上标分布到标识相 同的第p个处理器上。 4.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述将 所有处理器划分成s个虚拟区域， 每块区域中的处理器总数小于 等于 ， 前s‑1块区域中处 理器的个数 是 ， 第s块区域中的处 理器个数是 ， 其中 表示向上整数。 5.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述计 算每个虚拟区域的局部块状正交对偶残差向量， 具体为： 划分到第i块区域的所有处理器 ， 将各自的局部残差向量范数值发送到i 区域中的处理器 上， 处理器 将i区域内的所有处理器发送的局部残差向量范数 值进行求和并将结果返回到该区域的各进程中， 最后该区域中各进程计算局部残差向量乘 以求和值的倒数， 将所 得结果作为局部块状正交对偶残差向量的第i列的非零部分。 6.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述引 入TSQR分解优化 正交化过程， 包括舍去原算法中的MGS正交过程， 更 换为并行TSQR分解。 7.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述对 原算法IDRstab （s,l） 中的步骤进 行循环移位， 包括将算法步骤中的某些块状向量之间或向 量之间的内积计算， 通过向量替换， 移动到并行TSQ R分解步骤， 与并行TSQR分解一同进行归 约操作。 8.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述在权　利　要　求　书 1/2 页 2 CN 115408653 A 2同一个同步点上同时执行并行TSQR分解与内积计算， 具体为： 各个进程创建一个OUT数组， 用于存放对块状向量执行简约QR分解后所得的一个 上三角形与局部块状向量之间或 局部向量之间的内积值； 定义新的函数， 将来自不同处理器的两个数组做简约QR分解与求 和计算； 基于新的函数， 定义归约操作， 将最后结果存储到OUT数组， 并将OUT数组返回到根 进程中； 在根进程计算 参数， 并将所 得参数传输 到其他处理器内存中。 9.如权利要求1所述的一种IDRstab算法高可扩展并行处理方法， 其特征在于， 所述循 环迭代更新近似解、 残差、 块状正交向量与块状向量， 具体步骤为： 步骤 （1） 、 基于块状向量 U0与U1， 更新近似解与残差向量， 执行矩阵向量乘计算， 生成1个 GMRES多项式算子 ； 步骤 （2） 、 执 行IDR步骤， 生成1个块状正交向量Vk； 步骤 （3） 、 循环迭代步骤 （1） 与步骤 （2） 共l次， 生成l个GMRES多项式算子rk与l个块状正 交向量Vk； 步骤 （4） 、 基于l个GMRES多项式算子， 更新近似解与平滑修正残差， 判断是否收敛， 满足 输出解向量， 停止迭代， 否则继续； 步骤 （5） 、 更新 块状向量 U0与U1， 返回步骤 （1） 。 10.一种IDRstab算法高可扩展并行处理系统， 用于高置信度数值模拟中大型稀疏线性 方程组Ax=b的求解， 其特征在于， 包括环境初始模块、 数据划分模块、 块状正交对偶残差向 量生成模块、 块状向量初始模块、 循环求 解模块： 环境初始模块， 被 配置为： 设置并行计算 参数值， 创建并行 执行环境； 数据划分模块， 被配置为： 将大型稀疏线性方程组Ax=b的系数矩阵A与右端向量b划分 到每个处理器上； 块状正交对偶残差向量生成模块， 被配置为： 计算矩阵A与初始向量x0的矩阵乘积Ax0， 计算每个处理器的局部残差， 将所有处理器划分成s个虚拟区域， 计算每个虚拟区域的局部 块状正交对偶残差向量； 块状向量初始模块， 被 配置为： 生成块状向量 U0与块状向量 U1； 循环求解模块， 被配置为： 循环更新近似解、 残差、 块状正交向量与块状向量， 直到残差 向量范数值小于拟定的阈值， 停止循环， 输出解向量； 在块状正交向量的生成和更新中， 引入TSQR分解优化正交化过程， 对原算法IDRstab （s,l） 中的步骤进 行循环移位， 将并行TSQR分解与内积 计算调整在同一个同步点上， 在同一 个同步点上同时执 行并行TSQR分解与内积计算。权　利　要　求　书 2/2 页 3 CN 115408653 A 3