大型复线性方程组预处理双共轭梯度法

当复线性方程组的规模较大或系数矩阵的条件数很大时,系数矩阵易呈现病态特性,双共轭梯度法存在不收敛和收敛速度慢的潜在问题,采用适当的预处理技术,可以改善矩阵病态特性,加快收敛速度。从实型不完全Cholesky分解预处理方法出发,构造了一种针对复线性方程组的预处理方法,结合双共轭梯度法,给出了一种预处理双共轭梯度法。数值算例表明该算法求解速度快,可靠高效,能够应用于大型复线性方程组的求解。     

大型稀疏线性方程组的一种压缩求解算法

求解线性代数方程组是工程上经常遇到的问题,而它们的系数矩阵又往往是大型稀疏矩阵。文章介绍了一种简单易行,并且已经用C语言实现了的求解这类方程组的压缩算法。最后,还对压缩和非压缩算法进行了比较。     

块三对角线性方程组的一种并行迭代算法

系统工程计算在科学计算中,单台处理机不能满足需要,为提高计算效率和精度,采用并行处理是一个非常好的块三对角线性方程组的办法,提出了分布式环境下求解块三对角线性方程组的一种并行计算,算法是充分利用系数矩阵结构的特殊性,通过对系数矩阵进行适当地分解构造的迭代算法,使得算法需要在相邻处理机之间进行并行通信三次.并从理论上给出了算法收敛的一个充分条件.最后,在HP rx2600集群上进行了数值仿真,结果表明,实算与理论是一致的,提高了并行效率和精度.     

新预处理ILUCG法求解稀疏病态线性方程组

大型稀疏病态线性方程组的高效求解在科学计算和工程应用中起着十分重要的作用.对于一般非对称正定的非奇异线性代数方程组,首先介绍常用的不完全LU分解预处理矩阵构造技术;然后给出SSOR预处理分解及其改进分解,并基于ILUCG思想提出新预处理ILUCG法同时给出收敛性分析;最后进行数值模拟仿真试验,数值结果表明该算法是有效可行的,且较之一般的预处理ILUCG方法该法在求解稀疏病态方程组方面具有优越性.     

GPU加速不完全Cholesky分解预条件共轭梯度法

不完全Cholesky分解预条件共轭梯度(incomplete Cholesky factorization preconditioned conjugate gradient, ICCG)法是求解大规模稀疏对称正定线性方程组的有效方法.然而ICCG法要求在每次迭代中求解2个稀疏三角方程组,稀疏三角方程组求解固有的串行性成为了ICCG法在GPU上并行求解的瓶颈.针对稀疏三角方程组求解,给出了一种利用GPU加速的有效方法.为了增加稀疏三角方程组求解在GPU上的多线程并行性,提出了对不完全Cholesky分解产生的稀疏三角矩阵进行分层调度(level scheduling)的方法.为了进一步提高稀疏三角方程组求解的并行性能,提出了在分层调度前通过近似最小度(approximate minimum degree, AMD)算法对系数矩阵进行重排序、在分层调度后对稀疏三角矩阵进行层排序的方法,降低了分层调度过程中产生的层数,优化了稀疏三角方程组求解的GPU内存访问模式.数值实验表明,与利用NVIDIA CUSPARSE实现的ICCG法相比,采用上述方法性能可以获得平均1倍以上的提升.     

并行PCG算法在电法勘探中的应用研究

采用有限元法进行电法勘探时，会产生大型稀疏线性方程组，如何提高方程组的求解效率成为物探研究的关键。针对传统直接法难以实现并行求解的缺点，提出了在Beowulf集群环境下，采用并行PCG算法求解物探系统线性方程组。在集群环境下，该算法具有机器间相互通讯少、时间复杂度低等优点，并且易于并行实现。实验结果表明，采用PCG算法获得了良好的并行效果。     

基于工作站机群并行求解有限元线性方程组

随着计算机高速网络技术的发展,工作站机群正在成为并行计算的主要平台.有限元线性方程组在土木工程结构分析中是最常见的问题.预处理共轭梯度法(PCGM)是求解线性方程组的迭代方法.对预处理共轭梯度法进行并行化并在两个不同的机群上实现,对存储方式进行详细分析,编程中采用了稀疏矩阵向量相乘的优化技术.数值结果表明,设计的并行算法具有良好的加速比和并行效率,说明并行计算能更快地求解大规模问题.     

基于OpenMP的共轭梯度法并行加速

共轭梯度法是为求解线性方程组而独立提出的一种常用的数值计算方法,被广泛地应用于天气动力、物理海洋等数值计算中,其复杂的矩阵计算产生巨大工作量,成为业务化应用过程中的计算瓶颈。利用OpenMP共享并行技术,将大量计算并行化,实现基于OpenMP的共轭梯度法并行加速,为共轭梯度法的广泛应用提供了新的计算解决方案。     

一般稀疏线性方程组的因子组合型并行预条件研究

基于因子组合给出一般稀疏线性方程组的一种新并行预条件。在该方案中,应用基于邻接图的重叠区域分解,形成一串相互重叠的子区域。对每个子区域,可以采用任何不完全LU分解。之后,利用全局三角因子与全局下三角因子的乘积作为全局的并行预条件,其中全局三角因子利用限制加性Schwarz思想对每个局部上三角因子的逆进行组合得到。分析表明,提出的预条件优于经典加性Schwarz和限制加性Schwarz,且能保持对称正定性。对混凝土细观数值模拟中线性方程组的实验再次表明,新方案优于经典加性Schwarz。     

并行PCG算法在电法勘探中的应用研究

采用有限元法进行电法勘探时,会产生大型稀疏线性方程组,如何提高方程组的求解效率成为物探研究的关键。针对传统直接法难以实现并行求解的缺点,提出了在Beowulf集群环境下,采用并行PCG算法求解物探系统线性方程组。在集群环境下,该算法具有机器间相互通讯少、时间复杂度低等优点,并且易于并行实现。实验结果表明,采用PCG算法获得了良好的并行效果。     

求解线性与非线性方程组的单调异步迭代并行算法

针对偏序情形，构造一类适用于多处理机系统的求解线性与非线性方程组的异步迭代并行算法，并对其单调收敛性条件进行了严格的理论分析。此外，还用数值试验证实了这些结果。     

Krylov子空间方法解线性方程组的并行性能分析及应用

许多并行计算问题,在结合并行机的特有体系结构时,要对算法的并行性能及其可扩展性进行分析。它决定了该算法解决有关问题是否有效,并进一步判断所用的并行计算系统是否符合求解问题的要求。文章通过对Ｋｒｙｌｏｖ子空间中两种有效算法－ＰＣＧ算法和ＧＭＲＥＳ（ｍ）算法在一类并行系统中形成的并行算法的性能进行了分析,给出了其求解问题规模与处理机数与加速比的关系结果表明。ＧＭＲＥＳ（ｍ）算法比ＰＣＧ算法更适合于并行。     

求解大规模矩阵特征问题的并行算法研究

基于数据并行的重启动Arnoldi并行算法,基于使用数据并行模型的重启动Arnoldi并行算法,提出一个精化重启动Arnoldi并行算法。为了降低弱扩展性对并行性能的负面影响,该算法使用任务图模型并行计算精化向量,减少处理器进程之间的通信次数,有效地实现并行计算。在KD-50-I万亿次机上的测试结果表明,该算法具有较好的可扩展性和并行 效率。     

一种求解输运方程的并行调度算法

高效并行扫描问题是调度问题的子集,调度问题是NP完全问题.针对输运问题的特点,如何按特定的计算次序调度本地网格单元,以保证最佳的计算与通信性能是一个难度很大的问题.文中设计了一种基于局部深度优先的优先级(PDFDS)算法,该算法具有局部性、通信量小、优先级队列好等特点.将PDFDS算法应用到求解二维粒子输运方程的程序中,与现有的调度算法相比,新算法具有更好的并行计算效果,对于大规模计算问题,可以扩展到1024个处理器,相对于64个处理器的并行效率达到了96%.     

基于BSP模型的大规模线性规划并行算法研究

在许多实际工程问题中经常遇到一些大型线形规划问题，通常的计算过程需要占用大量的计算时间，效率低下。文中提出了一种基于BSP模型的大规模线性规划并行算法——修正单纯形并行算法，分析了其代价函数和加速比，在所研制的集群计算机上进行了实现和测试。结果表明：当问题规模比较大时，此并行算法能获得较好的加速比。     

Performance Prediction for Parallel Iterative Solvers

In this paper, an exhaustive parallel library of sparse iterative methods and preconditioners in HPF and MPI was developed, and a model for predicting the performance of these codes is presented. This model can be used both by users and by library developers to optimize the efficiency of the codes, as well as to simplify their use. The information offered by this model combines theoretical features of the methods and preconditioners in addition to certain practical considerations and predictions about aspects of the performance of their execution in distributed memory multiprocessors.     

A Decentralized Computational Infrastructure for Grid-Based Parallel Asynchronous Iterative Applications

Parallel asynchronous iterative algorithms relax synchronization and communication requirements, and can potentially extend Desktop Grids beyond embarrassingly parallel applications to support a broader class of parallel iterative applications. This paper presents the design and implementation of CometG, a decentralized (peer-to-peer) computational infrastructure that extends Desktop Grid environments to support these applications. CometG provides a decentralized and scalable tuple space, efficient communication and coordination support, and application-level abstractions that can be used to implement Desktop Grid applications based on parallel asynchronous iterative algorithms using the master-worker/BOT paradigm. The deployment and evaluations of CometG and a CometG-based application in a wide-area environment using the PlanetLab [7] test bed, as well as a campus network are presented.     

求解带状线性方程组的一种并行算法

提出了一种在MIMD分布式存储环境下求解带状线性方程组的交替方向迭代并行算法。利用系数矩阵的结构特点分裂矩阵,使整个计算过程只在相邻处理机间通信两次。给出了系数矩阵分别为Hermite正定矩阵和M-矩阵时算法收敛的充分条件。最后,在HP rx2600集群系统上进行的数值计算表明,该算法与多分裂方法相比具有较高的加速比和并行效率。     

基于曲线投影模型的电子断层三维重构并行算法

大尺度高精度的电子断层三维重构可以获得在更大视角下的生物大分子三维结构的细节信息。但研究尺度的增大给获取高精度重构结果和缩短数据处理时间带来了巨大的挑战。TxBR提出的曲线模型显著提高了重构的精度,但其计算比直线模型更复杂耗时,且在曲线模型下,之前的并行策略不再可行。针对这一问题,提出了一种在GPU平台上实现的针对曲线模型的分块迭代并行算法。通过对曲线模型的研究发现,曲线模型具有一定的空间局域性,利用这种性质提出了一种纵向的分块方式。在算法的实现阶段,提出一个基于页的数据传输策略,从而能够去除冗余的数据传输,减少数据传输带来的时间消耗。实验结果显示,本算法可接近40倍的加速比。