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

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

Grouping and Order Reducing Algorithm for Solving Toeplitz Type Circular Tri-diagonal Liner Algebraic Equation Systems

Based on the idea of the divide and conquer method, as is commonly adopted in parallel algorithms, a grouping and order reducing sequence algorithm is proposed for solving the Toeplitz type circular tri-diagonal linear algebraic equation systems in this paper. Compared with the traditional algorithm for the same problem, the advantage of this grouping and order reducing algorithm is that the computation cost and the computer memory requirement can be reduced. The whole algorithm includes three steps. The first step is grouping and order reducing of the original system. To put it better, the coefficient matrix and the right hand side of a Toeplitz type circular tri-diagonal system of order n=μm is divided into μ subgroups. Consequently, the order of each subgroup is . The second step is the formation of the parameter equations. That is to say, according the characteristics of the tri-diagonal coefficient matrix, the relations between subgroups are obtained, and the solution components, which do not belong to the subgroups, are taken as parameters. Then, a parameter equation is formed based on the equation that includes the parameters. The third step is to solve the parameter equation. And then, the original system is solved by substituting the parameters into the corresponding subgroups. As for the tri-diagonal system, the grouping and order reducing algorithm can also reduce the requirement for the computer memory and increase the order of the system, but at the same time , increase the computation cost. Numerical experiments show that, on one hand, there is an optimal number for grouping in saving the computation cost if the order of the system is fixed. On the other hand, the optimal number for groupings increases with the increase of the order of the system.