CUDA架构下大规模稠密线性方程组的并行求解

在Gauss-Jordan消去法的基础上,给出了一种适应于CUDA架构的改进Gauss-Jordan消去并行算法。通过分析该方法的处理过程以及CUDA架构的相应限制,在CUDA的grid-block-thread三层组织结构的基础上,从算法构造的角度提出了grid-strip-group-block-thread五层结构,给出了基础行以及全局基础行等概念,并构建了适应于CUDA架构的Gauss-Jordan消去法的并行版本,在最高维数为4000维的大规模稠密线性方程组的算例求解上与串行Gauss-Jordan消去法进行了比较,实验结果表明,该算法能够充分利用GPU的硬件特性,有效地降低了大规模稠密线性方程组的求解时间。

大规模稠密线性方程组求解的并行计算方法

大规模工程计算对并行计算的需求是推动并行计算快速发展的主要动力。而大规模稠密线性方程组的求解问题在工程计算中非常重要。笔者构造了新的稠密线性算法,并用三种不同的并行计算技术,分别是基于OpenMP、MPI与PPL的多核并行算法,比较得出了适合科学计算与工程上的并行计算技术,得到了PPL并行计算的优势。

大规模带状线性方程组的分层混合并行求解算法

并行计算过程中,全局通信往往会成为影响算法可扩展性的关键因素。因此,针对大规模带状线性方程组,提出基于MPI/OpenMP多粒度混合编程模型的分层并行算法,将全局通信转化为多次局部通信,解决了全局通信所带来的瓶颈问题,提高了大规模带状线性方程组并行求解算法的可扩展性。

解大规模线性方程组的Mann迭代并行算法

利用实函数不动点的Mann迭代算法,提出了一种求解大规模线性方程组新的并行算法,分析了算法的并行加速比,讨论了算法在基于消息传递机制的MPI并行环境下的实现流程,给出了并行环境上的实验。该算法适用范围广,数值计算结果表明理论分析与实际计算相符合,算法在并行环境下具有较好的并行度,可适合大规模科学与工程的高性能计算。

基于PVM的稠密线性方程组网上并行求解

将求解线性方程组的Gauss-Jordan消去法与Gauss列主元消去法结合起来,提出了利用并行计算支撑软件PVM在局域网上高效并行求解稠密线性方程组的算法.该算法处理机间的通信开销较少,实现了负载平衡和各处理机间的全并行工作.用1～24台桌面PC机按两种网络布局方式连接成的局域网,在PVM3.4 on Windows2000、VC 6.0并行计算平台上编程对该算法进行了数值试验,得到了正确的结果.

稠密线性方程组的多线程同步算法及其实现

构造线性方程组的若干多线程同步算法 ,给出它们在Delphi中的实现并用典型计算实例在多CPU计算机上进行测试 .

计算电磁学中稠密线性方程组的迭代求解

针对计算电磁学中产生的大型稠密复对称非共轭线性方程组,总结和讨论了这几年发展和流行的Krylov子空间迭代算法和预条件技术.数据计算表明采用带双阈值的不完全LU分解(ILUT)预条件处理的BiCGSTAB和GMRES迭代方法比较适合求解计算电磁学中产生的大型稠密复对称非共轭线性方程组,它们不但可以获得较快的收敛,而且整个构建和存储代价也很小.

求解稠密线性方程组的并行算法研究

基于对稠密线性方程组系数矩阵的一种新的分解方法，给出了分解与求解过程的并行算法。

分布式并行机上稠密线性方程组的直接解法

本文综合介绍稠密线性方程组的几种直接解法，介绍常用的处理机与矩阵元素间的映射方案并详细给出环绕映射的分配方案。最后从理论和实验两方面介绍各种分配方案间的性能比较。从比较发现：环绕映射性能最优且可扩展性最好。

求解电路仿真中超大规模稀疏线性方程组的改进分块对角加边方法

针对电路仿真中瞬态分析产生的超大规模稀疏线性方程组,分块对角加边(Bordered Block Diagonal,BBD)方法是一类经典的求解方法.本文提出了一种改进的BBD方法,通过使用基础列分解和流水线分解结合的方式,改善了传统BBD方法中负载不均衡的问题.在矩阵边界分解时,本文通过引入流水线分解克服了传统方法边界难以并行的缺陷.通过求解16个真实电路上产生的超大规模稀疏线性方程组,我们验证了改进BBD方法的有效性.相较于传统的BBD方法,改进方法在不同线程下的求解速度均有一定提升.

求解大规模矩阵问题的Krylov子空间方法

求解大规模矩阵问题包括线性方程组和特征值问题等是计算数学和科学工程计算中的重大课题。最近几年 ,其研究工作取得了许多重大进展。文中给出大型线性方程组和特征值问题 Krylov子空间方法若干进展的一个概述 ,其中包括作者对这些问题的研究成果。涉及的专题包括求解大型线性方程组的共轭梯度法、SYMMLQ算法、MINRES算法、GMRES算法、Lanczos双正交化算法、QMR算法以及这些算法的块格式 ;求解大型对称特征值问题的 Lanczos算法和块 Lanczos算法 ;求解大型非对称特征值问题的 Lanczos算法、Arnoldi算法以及这些算法的块推广。讨论求解大规模矩阵问题的加速技术和预处理技术。

关于广义边界元方程组迭代解的一个新预处理方法(英文)

引入一个用于解偏微分方程广义边界无法代法的新预处理算法。文中首先考虑标准边界元法使用的稀疏预处理子。然后阐述广义边界元法及其推广。使用离散小波变换来加速基于分离的预处理子。广义边界元法能有效迭代的关键在于压缩轴基函数形成的矩阵，用有紧支撑集的轴基函数得到了预处理迭代的新结果。也给出一些数值试验结果。

高温稠密等离子体交换能量的快速精确计算

高温情况下，自由电子所能达到的分波数很大，因而应用标准的交换能计算公式大规模计算高温等离子体的原子能量基本是不可行的。为了满足在一定计算精度下的工程计算要求，必须找到一种快速计算高分波自由电子间相互作用能的方法。

一种基于敏捷集群计算系统的并行GMRES方法

随着通信系统和人工智能的飞速发展,以智慧城市、智慧工厂和智能制造等为代表的多种新型应用场景不断涌现,使得通信、感知和计算等系统的一体化成为技术发展的新趋势。人工智能新型应用场景对大规模高效敏捷计算提出了新的要求,基于敏捷集群计算系统,提出了一种并行广义最小残差(Generalized Minimal Residual, GMRES)方法,主要通过并行矩阵向量乘法和并行高瘦矩阵QR(Tall and Skinny QR,TSQR)分解实现Krylov子空间的高效并行构造,充分利用集群计算系统的计算和通信性能,实现大规模线性方程组Ax=b的快速求解,其中A为一个n×n的矩阵,在工程实践中,n可达数十万甚至百万规模。通过求解二维泊松方程的有限元离散得到的刚度方程,验证了算法的有效性。

关于Kaczmarz的一类加速免伪逆贪婪块方法

块贪婪Kaczmarz方法在解决大规模一致线性系统方面取得了成功应用。然而在每次迭代步骤中,GBK方法都涉及伪逆计算,这不仅复杂化了计算并减慢了收敛速度,且不适合分布式实现。在本文中基于Sketching技术提出了两种免伪逆计算的GBK方法,分别是杠杆得分抽样免伪逆GBK方法和稀疏随机投影免伪逆GBK方法,其算法效率更加高效,收敛速度可以达到指数收敛。为了进一步加快收敛速度,我们还提出了CountSketch免伪逆重力球GBK方法、杠杆得分抽样免伪逆重力球GBK方法和稀疏随机投影免伪逆重力球GBK方法。为了验证新方法的有效性,我们进行了一些数值示例。结果表明,这些新方法在解决大规模一致线性系统方面具有很高的效率和准确性。

变预处理子SOR-双共轭残量法

研究了大规模稀疏线性方程组的预条件迭代求解算法。结合Krylov子空间方法和SOR迭代,给出了一个新的求解算法,即变预处理子SOR-双共轭残量法,同时给出了算法的收敛性分析。数值实验显示了算法的快速收敛性。

三维多介质电容计算的有效方程组织方法

随着 VL SI电路集成密度急剧增长及特征尺寸不断缩小 ,快速准确地计算三维互连寄生电容已成为集成电路辅助设计中一个研究热点。提出一种有效的多介质直接边界元方程组织方法。该方法排列直接边界元方程组中的源点和变量 ,使系数矩阵非零元分布极有规律 ,通过最少的数组存储非零矩阵块 ,以达到加快方程迭代求解的目的。该方法可应用于任意复杂结构的三维寄生电容计算 ,对介质数目较多的虚拟多介质计算 。

基于GaBP的迭代加速优化算法

求解对称对角占优线性方程组的GaBP(Gaussian Belief Propagation)迭代算法具有低计算复杂性和高并行性的特点。利用GaBP算法的这两个特点,便于处理大规模稀疏线性方程组的求解。为了进一步提高求解的迭代效率,使用经典迭代算法中的加速优化方法,给出了对应的多种GaBP迭代加速优化算法。从动态松驰因子的GaBP算法和MannGaBP迭代加速优化算法的实验结果表明,在相同精度下,所提出的加速优化算法比经典迭代算法和GaBP算法具有更高的并行执行效率。

并行J-变量块Cholesky分解算法的仿真研究

该文提出一个针对大型实对称正定稠密方程组或复对称非Herm itian稠密方程组线性求解器的并行分布式算法。它使用了不同于ScaLAPACK的J-变量块Cholesky分解算法和一维块循环列数据分配。该算法以MPI作为消息传递库,在最多可达16个处理器的集群上针对实对称正定稠密方程组可提供与ScaLAPACK近似的浮点操作性能,并可解决一些涉及复对称非Herm itian稠密方程组的电磁场散射问题。该算法的优点是执行Cholesky分解所需的存储量只是标准并行库ScaLAPACK的一半。仿真的数值结果表明该算法是正确、有效的。

GaBP算法优化与实现

通过研究经典GaBP算法,实现了同步和异步GaBP算法程序设计和计算实验,并对结果进行了系统的分析。实验表明GaBP优化算法——异步GaBP算法比经典GaBP算法有更好的计算效率。