MiniBranRAP:极小化分支判断数的AMG粗网格矩阵计算并行算法

代数多重网格(AMG)是科学工程计算与工业仿真领域求解大规模稀疏线性代数方程组最常用的算法之一。在启动(Setup)阶段的每个网格层,AMG需要基于限制算子R、当前细网格层矩阵A和插值算子P的稀疏矩阵乘积来计算粗网格矩阵A c=RAP,该过程是AMG并行性能的主要瓶颈。首先发现了主流AMG解法器中RAP并行算法由于分支判断的平方复杂度导致的性能瓶颈,并结合稀疏矩阵CSR的行主序特点,提出了具有线性复杂度分支判断数的RAP并行算法MiniBranRAP。该算法集成到JXPAMG解法器中,并通过实际应用算例验证了算法的有效性。测试结果表明,对于6个来自实际应用的典型算例,相对于Hypre最新版本的BoomerAMG解法器,基于MiniBranRAP的JXPAMG解法器在28个进程上将Setup阶段的计算效率平均加速3.3倍、最高加速9.3倍。

直流电阻率法三维正演的聚集代数多重网格算法研究（英文）

为加快直流电阻率法三维正演模拟的计算速度,本文引入一种新型的代数多重网格算法一聚集代数多重网格算法(AGMG)。首先从直流电阻率法满足的电位二次场微分方程出发,采用七点有限差分格式进行离散,结合混合边界条件形成大型稀疏求解线性方程组;然后详细给出AGMG法聚集粗化的成对聚集算法及技术流程,并采用V循环AGMG预处理共轭梯度(CG)算法(AGMG-CG)求解线性方程组,最终实现直流电阻率三维正演模拟。通过典型地电模型数值模拟研究,并与成熟的直流电阻率三维正演模拟程序(3DDCXH)结果及解析结果对比验证了本文给出算法可行性和准确性。另外通过对不同剖分网格和不同模型的数值模拟,并与传统迭代算法(ILU-BCGSTAB、ILU-GCR、SSOR-CG)对比表明,AGMG-CG算法不论从迭代次数还是迭代时间上都有显著优势,同时具有近乎线性快速下降、迭代次数随网格大小增加而缓慢增加等优点。因此,本文算法具有收敛精度高、收敛快、迭代稳定等优点,为提高直流电阻率法三维正演模拟的计算效率提供了可能。

并行代数多重网格算法可扩展性能分析

对当今求解大型稀疏线性代数方程组最有效的迭代方法之一——代数多重网格(AMG)算法的并行计算进行可扩展性能分析.给出一套并行计算可扩展性能分析方法,用于分析和指导并行迭代算法及实现技术的设计与优化并应用于并行AMG算法.分析表明,网格算子的平均模式大小和迭代过程的算法效率分别制约了AMG算法启动阶段和迭代求解阶段并行性能的发挥,成为该类算法急需解决的两个关键问题.

使用代数多重网格进行多聚焦图像融合

针对将代数多重网格对图像结构信息的提取能力应用到图像的融合方面进行了研究,提出了一种基于代数多重网格的自适应多聚焦图像融合算法。首先提取图像的粗网格数据,然后进行分块重建,根据分块重建结果与原始图像的均方差选择合适的源图像分块进入融合图像。为了避免分块之间的不连续性,采用了自适应的策略。实验结果表明,自适应图像融合的结果没有丢失有效信息,能够最大程度地将清晰物体保留在融合图像之中。

大型稀疏法方程组的代数多重网格解法

测量平差中经常会遇到大型稀疏法方程组的求解。传统的线性方程组迭代解法能够很快平滑误差分量中的高频分量;但对于低频分量衰减很慢。代数多重网格算法通过建立多重网格,并在不同的网格层上分别处理高低频误差分量,将所有层相互协调起来求解同一问题。这对于大规模稀疏线性方程组的求解,具有高效性。这里介绍了代数多重网格算法,并进行了改进,得到了AMG-CG算法。数值算例表明,代数多重网格算法(AMG)以及改进的AMG-CG算法对求解大型稀疏法方程组具有高效性和数值稳定性,改进后的AMG-CG算法在计算效率上进一步提高,对于大型稀疏法方程组的求解是可行有效的算法。

一种新的代数多重网格法及其在CFD中的应用

提出了一种面向对象的代数多重网格(algebraic multi-grid,AMG)算法,以每一层网格作为研究单元.网格粗化过程中,形成各单元,同时记录其前后单元,形成双向链表.粗化过程采用Ruge和Stüben算法,光滑算子用Gauss-Seidel迭代.由于AMG算法与网格信息无关,可以作为"即插即用"型的线性方程组求解器.对CFD计算过程耗时最多的压力修正方程作了研究,分别对二维后台阶流动模型在不同网格划分情况进行了计算,代数多重网格方法与单重网格的不完全分解共轭梯度法对比发现,前者具有明显的优势,随着网格数目增加,优势表现更为明显.最后与AMG1r5相比,开发的程序内存占用较少,最高只有AMG1r5的36%.

代数多重网格法在排队理论中的应用

提出一种校正ＡＭＧ方法来求解排队模型。该方法对一般ＡＭＧ方法的限制算子进行了改进，从而在求解过程中保留了问题的奇异性。计算结果表明改进后的方法加快了收敛速度，提高了解的精度。

多重网格技术在SIMPLE算法中的应用及结果的不确定性分析

将多重网格技术应用于SIMPLE算法 ,对方腔顶盖驱动流问题进行求解 ,并运用Richardson外推法进行了计算结果的不确定度分析 .与单重网格计算的对比表明 ,多重网格技术的应用不仅大大减少了计算的迭代次数、CPU占用时间 ,加速收敛的效果明显 ,而且使计算结果的不确定度分析工作量减小 。

代数多重网格法与多水平不完全LU分解法

介绍代数多重网格(AlgebraicMulti-Grid,AMG)法和多水平不完全LU分解(Multi-eliminationIncompleteLUPreconditioner,ILUM)法的基本算法,分析二者的关系.给出了用ILUM方法思想建立的代数多重网格方法的理论特征,证明了此类AMG算法的两网格收敛性,说明了此类算法和基本算法一样也不一定具有与层数无关的收敛性.

几类典型应用的代数多重网格算法并行可扩展瓶颈分析

对于大规模稀疏线性代数方程组,代数多重网格(AMG)是具有最优计算复杂度的求解算法,但由于其算法流程复杂,导致难以取得理想的并行可扩展性能,难以定位和分析其并行可扩展瓶颈。通过分析AMG算法的性能骨架和通信模式,归纳了三类可扩展性能瓶颈,并引入稀疏矩阵通信域的概念来刻画稀疏模式对并行通信性能的影响。针对辐射流体力学、结构力学、航空发动机三类实际应用的6个具有不同稀疏模式特征的典型算例,实现了多粒度并行可扩展性能瓶颈的定位与分析,总结了未来AMG并行性能优化方向。

标准Criss-Cross剖分下线性有限元方程的快速AMG算法

首先对标准Criss -Cross剖分下的线性有限元空间进行能量正交分解 ,通过对正交子空间的双尺度分析 ,获得了一种合适的限制算子 ,进而构造相应的AMG算法 .数值实验结果表明 ,该方法对求解椭圆方程是非常有效和健壮的 ,且与通常的代数多重网格法相比较 。

求解二维三温辐射扩散方程组的一种代数两层迭代方法

在二维三温辐射扩散方程离散代数方程组的求解中,由于光子、电子和离子温度之间存在耦合关系,而且三个温度在同种介质中有不同的扩散性质,使得经典的代数多重网格(AMG)方法难以直接应用.基于特殊粗化策略,在粗网格层解除了这种耦合关系,得到一种代数两层网格方法,而粗网格方程由经典AMG方法求解.将这一算法具体应用于JFNK(Jacobian自由的Newton-Krylov)框架中预处理方程的求解,并基于该框架求解二维三温辐射扩散方程组.数值结果显示了算法的可扩展性和健壮性.

一种新的并行代数多重网格粗化算法

近年来,受实际应用领域中大规模科学计算问题的驱动,在大规模并行机上实现代数多重网格(AMG)算法成为数值计算领域的研究热点。本文针对经典AMG方法,提出一种新的并行网格粗化算法——多阶段并行RS算法(MPRS)。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示,新算法适合更广泛的问题,相对其他并行粗化算法,明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程,在64个处理机上并行AMG求解,含8百万个未知量,新算法比RS3算法减少了近60的三维Poisson方程,近32万个未知量,在16个处理机上并行AMG-GMRES求解,新算法所需的迭代步数大约为其他粗化算法的一半,显示了很好的算法可扩展性。

并行代数多重网格算法:大规模计算应用现状与挑战

代数多重网格(AMG)是求解偏微分方程离散线性代数方程组最有效的算法之一,广泛应用于科学与工程计算领域实际问题的大规模数值模拟.随着超级计算机性能不断提升,实际数值模拟的计算规模和并行规模越来越大,同时.实际问题应用特征和计算机体系结构特征越来越复杂,AMG面临并行可扩展、算法可扩展和浮点性能优化的严峻挑战.本文结合大规模计算的发展趋势,特别是面向即将到来的百亿亿次(E级)计算,分析AMG算法在这三个方面的挑战,总结研究现状与进展,展望未来研究重点.

求解二维三温能量方程的基于AMG预条件子的Krylov子空间迭代法

本文对一类二维三温能量方程的实际应用问题 ,建立了一种半粗化的代数多重网格法 (SAMG) ,进而得到了以该 SAMG方法为预条件子的 Krylov子空间迭代法 .数值实验结果表明 。

CPU/GPU集群上求解偏微分方程的可扩展混合算法

当前世界上排前几位的超级计算机都基于大量CPU和GPU组合的混合架构,它们对某些特殊问题,譬如基于FFT的图像处理或N体颗粒计算等领域可获得很高的性能。但是对由有限差分(或基于网格的有限元)离散的偏微分方程问题,于CPU/GPU集群上获得较好的性能仍然是一种挑战。本文提出并测试一种基于这类集群架构的混合算法。算法的可扩展性通过区域分解算法实现,而GPU的性能由基于光滑聚集的代数多重网格法获得,避免了在GPU上表现不理想的不完全分解算法。本文的数值实验采用32CPU/GPU求解用差分离散后达三千万未知数的偏微分方程。

并行代数多重网格粗化算法的优化

近年来,随着日常生活等实际应用领域中大规模稀疏矩阵求解问题的推动,代数多重网格(AMG)算法及其并行化的研究成为了数值计算领域的热点。本文在原始AMG算法和MPRS算法的基础上,对现有的并行AMG算法提出了一种优化的动态阈值算法(DVRS)。在Visual Studio 2008环境下,数值计算实验结果表明,新算法适用于更广泛的领域,与原有的并行AMG算法相比,改善了AMG并行计算的可扩展性。

基于局部松弛和粗化策略的代数多重网格方法

受强振荡、间断系数和非均匀网格步长的影响,由偏微分方程离散所得的稀疏线性代数方程组的系数矩阵呈现多尺度性质,即同一行的非对角元素可相差几个数量级,使得经典代数多重网格(AMG)算法难以适应.本文提出一种新的AMG方法(LRC-AMG),基于强弱相邻关系分离某些具有特殊性质的点结成网格子块,仅在局部块内进行光滑和粗化,可有效地消除多尺度性对收敛速度的影响.数值实验在文中给出.

求解静电场偏微分方程的新代数多重网格法

多重网格法是求解偏微分方程大规模离散化方程最有效的方法,针对静电场偏微分方程,讨论一致线性有限元剖分下的拉格朗日有限元方程的代数多重网格法,给出了一种新的粗化算法和构造插值算子的途径。数值实验表明,新的代数多重网格法的有效性。

求解多尺度稀疏矩阵的代数界面优先AMG光滑子

光滑子是影响代数多重网格算法(AMG)求解效率的重要组件之一.本文考虑实际应用中普遍出现的一类多尺度稀疏矩阵,由于多尺度性质的影响,现有AMG光滑子的光滑效果不理想,从而影响AMG算法求解该类方程的效率.借助代数界面的概念,本文分析了代数界面对松弛型光滑子的影响,并通过扩展代数界面的内涵,设计了一种代数界面优先的光滑子(AI-Smoother).以Gauss-Seidel(GS)光滑子为例,通过三维模型问题和实际问题测试了该光滑子(AI-GS)的有效性.测试表明,与自然序GS光滑子相比,AI-GS有效改善了AMG算法的收敛速度.对于三维随机系数扩散方程百万自由度算例,AI-GS可获得28.2%的加速,对于激光聚变应用中的三温方程百万自由度算例,AI-GS可获得28.8%的加速.