求解循环三对角方程组的追赶法

利用LU分解的思想,首先将循环三对角方程组的系数矩阵A分解成3个矩阵的乘积LUD,其中L是下三角矩阵,U是单位上三角矩阵,D是拟对角矩阵(每行只有两个非零元素,前n-1行非零元位于主对角线和最后一列上,第n行非零位于第1列和最后一列上);然后,运用追赶法的思想依次用前代法("追")解出Lu=d的解,回代法("赶")解出Uv=u的解;再利用Dx=v的第一行和最后一行求出未知量xn,进而回代求解出所有未知量。该方法虽然将系数矩阵分解成3个矩阵的乘积,但计算过程并不复杂,总的算数运算量只有O(14n),小于传统算法的计算量(O(17n))。文章对数值计算的稳定性进行了分析,当矩阵A对角占优且2ai≤bi时,算法是数值稳定的。数值试验结果与理论分析相吻合。

追赶法并行求解循环三对角方程组

给出了求解循环三对角线性方程组的一种并行算法。在系数矩阵满足对角占优的条件下,利用该方法能够快速、稳定地求解循环三对角线性方程组,在单个进程上的计算量仅为O(17n),与传统算法求解循环三对角线性方程组的计算量相同。而且,本算法可以方便地实施分布式并行计算,各进程仅需向主进程传递8个实数,而主进程向各子进程传递2个实数,通讯量较小。数值实验结果表明:对于大规模的循环三对角线性方程组,利用16个进程计算的并行效率均在0.75以上。求解三对角线性方程组的传统追赶法实则是本文算法的一种特例,因此,该算法也可用于求解三对角线性方程组。

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

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

解循环三对角线性方程组的追赶法

循环三对角、循环 Toeplitz三对角线性方程组的求解在科学与工程计算中有着广泛的应用 .运用矩阵分解给出此类方程组的直接解法 ;通过分析其特性 ,给出了达到机器精度的截断算法 ,其计算复杂度几乎等同于求解一个三对角线性方程组的计算复杂度 .数值实验的结果与理论分析的结果十分吻合 .该算法还推广到求解拟三对角线性方程组 .

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

提出一种分布存储环境下求解循环块三对角方程组的并行算法 ,该算法以矩阵子块运算为基础 ,算法实现调用BLAS3子程序 ;文中分析了算法的复杂性 ,给出了一个保证算法不会在执行过程中中断的充分条件 .

改进的求解线性方程组的并行Arnoldi方法

以Galerkin原理为基础,提出了求解循环块三对角线性方程组的并行算法。根据系数矩阵的稀疏性,选取适当的子空间的基,使算法不但不会发生中断,并从理论上证明了当系数矩阵对称正定时,该并行算法收敛。最后,在HPrx2600集群上进行的数值实验结果表明,该算法的并行效率很高,理论和实际计算相一致。

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

A parallel solver for cyclic tridiagonal systems on distributed-memory multi- computers is presented. The complexity of the algorithm is analyzed. We prove that the processes will not break down if the cyclic tridiagonal systems’ coefficient matrix is strictly diagonally dominant. The results of numerical experiments on a distributed-memory multicomputer YH3E show that the algorithm has a high parallel efficiency.

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

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

循环三对角Toeplitz线性方程组的分组降阶算法

运用并行算法中分而治之的思想,给出了一种求解循环三对角Toeplitz线性方程组的分组降阶串行算法。与求解同类问题的传统算法相比,分组降阶算法的优点在于它不仅大幅度减少了内存占用量,而且还大幅度减少了算术运算量。分组降阶算法可以通过3个步骤来实现。第一步是分组降阶,其基本思路是将一个n=μm阶的方程组按行分成μ组,每组m个方程;n维解向量也对应地分成μ组。第二步是构造参数方程组,也就是依据三对角系数矩阵的特点,给出各组解之间的关系式,把不属于该组的解分量看作参数。第三步是求解参数方程组和原方程组,在这一步中,首先求解参数方程组,然后再代入相应分组的关系式便可求出所有的解分量。对于三对角Toeplitz线性方程组,同样能减少内存占用量,从而在计算机性能不变的情况下,提高求解问题的规模,但与求解三对角Toeplitz线性方程组的传统算法相比运算量有所增加。数值实验结果表明,对于特定规模的方程组来说,总存在一个最佳的分组个数使得计算时间最少;随着方程组阶数的提高,最佳分组的个数也增大。

Sherman-Morrison公式及其应用

Sherman-Morrison公式是求矩阵之和的逆矩阵的一种特殊方法,在最优化BFGS算法和循环三对角线性方程组的求解等方面有着重要的应用。