一类Toeplitz循环三对角方程组的一种分布式并行算法

提出一类Toeplitz循环三对方程组的一种分布式并行算法,在求解由一阶线性双曲型方程（如迁移方程）在一定边界条件下导出的隐式差分方程组时,要重复地求解此类Toeplitz循环三对角方程组。算法基于对系数矩阵的分解,贯彻并行算法设计中“分而治之”的原则,充分利用了系数矩阵结构的特殊性。算法实现中通过秦九韶公式的运用,避免了不必要的冗余计算;理论分析和数值试验表明,算法是数值稳定的,且当方程组规模充分大时,该算法加速比趋近线性加速比的理想情况。给出了算法在某分布存储多计算机系统上的数值试验结果。     

近似三对角Toeplitz方程组的快速分布式并行算法

利用近似三对角Toeplitz矩阵的特殊结构，提出了一种新的求解近似三对角Toeplitz方程组的快速算法．在三对角Toeplitz矩阵的近似LU分解的基础上，利用“分而治之”的思想，并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算，提出了求解近似Toeplitz三对角方程组的快速分布式并行算法，并在理论上证明了算法具有近似于线性的加速比．最后通过数值实验证明，新的并行算法具有较高的并行效率，并且当矩阵阶数n足够大时，算法的加速比趋近于线性加速比．     

一类求解非线性方程组算法的并行性能分析

讨论了一类求解非线性方程组算法的并行性能,与传统的算法不同之处是用一个块对角矩阵作为迭找矩阵,且该矩阵可由一个仅包含向量内积的矩阵与向量乘积的递推关系简便计算得到,在对算法进行描述之后,分析了算法的并行执行过程,给出了算法的并行加速比和对存储的需求分析,数值计算表明理论分析与数值结果相符合,算法具有较好的并行度和较低的存储要求,可适用于一般和大规模科学与工程的高性能计算。     

基于曙光并行机的超大规模非线性方程组并行算法研究

该文讨论了一类求解大规模非线性方程组算法的并行性能及其在曙光并行机上的实现过程，与传统的算法不同之处是用一个块对角矩阵作为迭代矩阵，且该矩阵可由一个仅包含向量内积和矩阵与向量乘积的递推关系简便计算得到，在对算法进行描述之后，分析了算法的并行加速比和存储需求，讨论了算法在基于消息传递的MPI并行环境下的实现流程，数值计算表明理论分析与数值结果相比，算法在分布式并行环境下具有有较好的并行主攻较低的存储要求，可适用于大规模科学与工程的高性能计算。     

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

提出了求解系数矩阵为块三对角的线性方程组的一种适合于MIMD分布式存储的并行算法，该算法以系数矩阵分解为基础，充分利用了系数矩阵结构的特殊性，进行了近似处理，使整个计算过程只在相邻处理机间通信两次，具有很高的并行效率，并在理论上给出了该算法成立的充分条件。最后，在HPrx2600集群上进行数值试验，结果表明，加速比呈线性增加，并行效率达到90％以上。     

三角形方程组的一种分布式并行算法

提出了分布式环境下求解三角形方程组的一种新的并行算法,该算法基于将系数矩阵和右端顶分,并将其以块行卷帘方式存储在各处理器的局部存储器,利用通信与计算重叠的技术,取得了比块列扫描算法好的效果,当方程组具有多重右端项时,效果尤为突出。文中给出了在YH3M计算机上该算法的数值试验结果及其与块列扫描算法的数值比较结果。     

大规模结构化二次规划并行算法

在内点算法(IPM)框架基础上,分析具有分块带边结构系数矩阵与箭形结构二次项的二次规划(QP)问题,导出其既约与最简既约修正方程.对既约修正方程系数矩阵进行置换,使其具有箭形分块结构,并结合该结构与解耦技术给出修正方程的并行求解算法,设计QP问题的并行IPM结构.在集群环境下的数值实验结果表明,该算法具有较好的加速比和...     

多处理机上高次代数方程的并行求解

本文讨论在多处理机上求解n次代数方程f_n(x)=0的并行计算方法。文中给出了代数方程同时求根算法的同步并行格式和异步并行格式,还给出了两个具体的算法,它们分别是二阶收敛和三阶收敛的。在YH-2模拟器上对两个算法进行了一些数值测试,表明这两个算法对高次代数方程求根问题有较高的并行加速比。     

基于直径为2的摩尔图网络的并行矩阵乘算法

提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.     

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

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

一类Toeplitz三对角方程组的有效分布式并行算法

针对大型方程组的特点,本文提出了一种求解一类Toeplitz三对角方程组的分布式并行算法.该算法首先并行求出原Toeplitz三对角方程组的近似解,然后在给定的误差范围内对近似解进行修正,该算法的通信机制简单、冗余计算量少.数值试验表明该算法具有较高的并行效率.     

快速求解一类Toeplitz循环三对角线性方程组的分布式并行算法

在分布式存储环境下,提出了一种在给定误差范围内快速求解一类Toeplitz循环三对角线性方程组的分布式并行算法,该算法是在仔细研究了方程组结构特点的基础上,通过求解满足给定误差范围的方程组的近似解,从而使得通信开销小,冗余计算量少,数值试验表明：该算法具有较高的加速比和并行效率。     

三对角线性方程组的一种有效并行算法

本文提出一种求解严格对角占优的三对角线性方程组的并行算法（简称ＰＰＤ算法）,新算法计算复杂性约为８ｎ,与最优串行算法追赶法的计算复杂性相同,通信复杂性为常数．目前求解此类方程组的最优并行算法的计算复杂性约为１７ｎ,通信复杂性约为ｌｏｇＰ,相对而言ＰＰＤ算法的计算性能和通信性能都有大幅度提高．试算结果表明,加速比呈线性增加,并行效率达到９０％以上．     

A multilevel parallel solver for block tridiagonal and banded linear systems

This paper describes an efficient algorithm for the parallel solution of systems of linear equations with a block tridiagonal coefficient matrix. The algorithm comprises a multilevel LU-factorization based on block cyclic reduction and a corresponding solution algorithm.

The paper includes a general presentation of the parallel multilevel LU-factorization and solution algorithms, but the main emphasis is on implementation principles for a message passing computer with hypercube topology. Problem partitioning, processor allocation and communication requirement are discussed for the general block tridiagonal algorithm.

Band matrices can be cast into block tridiagonal form, and this special but important problem is dealt with in detail. It is demonstrated how the efficiency of the general block tridiagonal multilevel algorithm can be improved by introducing the equivalent of two-way Gaussian elimination for the first and the last partitioning and by carefully balancing the load of the processors. The presentation of the multilevel band solver is accompanied by detailed complexity analyses.

The properties of the parallel band solver were evaluated by implementing the algorithm on an Intel iPSC hypercube parallel computer and solving a larger number of banded linear equations using 2 to 32 processors. The results of the evaluation include speed-up over a sequential processor, and the measure values are in good agreement with the theoretical values resulting from complexity analysis. It is found that the maximum asymptotic speed-up of the multilevel LU-factorization using p processors and load balancing is approximated well by the expression (p +6)/4.

Finally, the multilevel parallel solver is compared with solvers based on row and column interleaved organization.     

Fast solution of implicit methods for linear hyperbolic equations

A factorisation method is described for the fast numerical solution of constant tridiagonal Toeplitz linear systems which occur repeatedly in the solution of the implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the Transport equation, under a variety of boundary conditions. In this paper, we show that such special linear systems can be solved efficiently by the factorisation of the coefficient matrix into two easily inverted matrices.     

块三对角线性方程组的一种分布式并行算法

提出了分布环境下求解三对角线性方程组的一种并行算法,该算法基于对计算量的仔细估算,合理地将方程组求解工作分配到各处理机,达到负载平衡,同时,充分地将计算与通信重叠,减少处理机空闲时间;当块三以角线性方程组的系数矩阵为对角占优时,算法在执行过程中不会中断;文中分析了算法的复杂性,给出了在分析布存储多计算机系统上的数值试验结果,数值结果表明,文中算法的效率较Ｃｈｕｎｇ等的算法有较大的提高。     

A fast stationary iterative method for a partial integro-differential equation in pricing options

A jump-diffusion model for the pricing of options leads to a partial integro-differential equation (PIDE). Discretizing the PIDE by certain method, we get a sequence of systems of linear equations, where the coefficient matrices are Toeplitz matrices. In this paper, we decompose the coefficient matrix as the sum of a tridiagonal matrix and a near low-rank matrix, and approximate the near low-rank matrix by low-rank matrices. Then we introduce a stationary iterative method for the approximate systems of linear equations. Comparison of the performance of our algorithm to that proposed in Pang et al. (Linear Algebra Appl. 434:2325–2342, 2011) is presented.     

A fast algorithm for solving special tridiagonal systems

In this paper, a fast algorithm for solving the special tridiagonal system is presented. This special tridiagonal system is a symmetric diagonally dominant and Toeplitz system of linear equations. The error analysis is also given. Our algorithm is quite competitive with the Gaussian elimination, cyclic reduction, specialLU factorization, reversed triangular factorization, and Toeplitz factorization methods. In addition, our result can be applied to solve the near-Toeplitz tridiagonal system. Some examples demonstrate the good efficiency and stability of our algorithm.