三对角线性方程组的循环规约对角占优算法

Cyclic reduction parallel diagonal dominant algorithm for tridiagonal systems

针对并行求解三对角线性方程组的对角占优(PDD)算法在系数矩阵为弱对角占优时,近似处理引入误差较大,即使是采用迭代PDD算法,收敛速度仍然很慢的问题,提出了一种PDD算法的循环归约方案。该方案采用新的分解方法,生成修正值计算方程组仍为三对角线性方程组,且保持对角占优特性。在修正值计算中采用循环归约方法,随着归约算法展开,系统的对角占优迅速增强,适时忽略非对角元素,取得解的修正值。算法的计算复杂性与迭代PDD算法基本相当,通信复杂性略高于迭代PDD算法,但解的收敛速度显著高于迭代PDD算法。不仅如此,该算法还可直接应用于非对角占优三对角线性方程组的求解。

Aiming at the problem that the error introduced by approximate processing is large when parallelly solving weak diagonal dominant tridiagonal linear equations, the convergence rate is still very slow even if the iterative Parallel Diagonal Dominant （PDD） algorithm is employed. A eyelie reduction scheme based on PDD algorithm was proposed and the scheme adopted a new decomposition method to generate the revised calculation equations which remain tridiagonal linear equations and keep diagonally dominant. The correction value was ealcalated by eyelie reduction method, while the reduction algorithm diagonally dominant of the system enhanced quickly and the correction value was obtained by using approximate treatment timely. The computational complexity is roughly equivalent to the iterative PDD algorithm and the communication complexity is slightly higher than that, but the convergence rate is signifieantly higher than that of the iterative PDD algorithm. Besides, the scheme can also be direedy applied to non-diagonally dominant tridiagonal linear equations.