三对角系统并行算法的研究概况
【摘 要】在科学和工程计算中，许多问题往往归结为三对角线性方程组的求解，其并行算法的研究具有重要意义。文章全面总结了当前求解三对角线性方程组的两类并行算法：直接解法和迭代解法，并介绍了其特点。
【关键词】三对角线性方程组；分治策略；并行算法；算法可扩展性
一、概述
三对角线性方程组的求解是许多科学和工程计算中最重要也是最基本的问题之一。在核物理、流体力学、油藏工程、石油地震数据处理及数值天气预报等许多领域的大规模科学工程和数值处理中都会遇到三对角系统的求解问题。很多三对角线性方程组的算法可以直接推广到求解块三对角及带状线性方程组。由于在理论和实际应用上的重要性，近20年来三对角方程组的并行算法研究十分活跃。
大规模科学计算需要高性能的并行计算机。随着软硬件技术的发展，高性能的并行计算机日新月异。现今，SMP可构成每秒几十亿次运算的系统，PVP和COW可构成每秒几百亿次运算的系统，而MPP和DSM可构成每秒万亿次运算或更高的系统。
高性能并行计算机只是给大型科学计算提供了计算工具。如何发挥并行计算机的潜在性能和对三对角系统进行有效求解，其关键在于抓住并行计算的特点进行并行算法的研究和程序的设计与实现。另外，对处理机个数较多的并行计算系统，在设计并行算法时必须解决算法的可扩展性，并对可扩展性进行研究和分析。
二、问题的提出
设三对角线性方程组为
AX=Y （1）
式中：A∈Rn×n非奇异，αij=0， 。X=(x1，x2，…xn)T Y=(y1，y2，…yn）T。
此系统在许多算法中被提出，因此研究其高性能并行算法是很有理论和实际意义的。
三、并行求解三对角系统的直接解法
关于三对角线性方程组的直接求解已经有大量并行算法，其中Wang的分裂法是最早针对实际硬件环境，基于分治策略提出的并行算法。它不仅通信结构简单，容易推广到一般带状线性方程组的并行求解，而且为相继出现的许多其它并行算法提供了可行的局部分解策略。
近20年来求解三对角方程组的并行算法都是基于分治策略，即通过将三对角方程组分解成P个小规模问题，求解这P个小规模问题，再将这些解结合起来得到原三对角方程组的解。一般求解三对角方程组的分治方法的计算过程可分为3个阶段：一是消去，每台处理机对子系统消元；二是求解缩减系统（需要通信）；三是回代，将缩减系统的解回代到每个子系统，求出最终结果。具体可分为以下几类：
（一）递推耦合算法（Recursive Doubling）
由Stone于1975年提出，算法巧妙地把LU分解方法的时序性很强的递推计算转化为递推倍增并行计算。D.J.Evans对此方法做了大量研究。P.Dubois和G.Rodrigue的研究表明Stone算法是不稳定的。
（二）循环约化方法（Cyclic Reduction）
循环约化方法由Hockey和G.Golub在1965年提出，其基本思想是每次迭代将偶数编号方程中的奇变量消去，只剩下偶变量，问题转变成求解仅由偶变量组成的规模减半的新三对角方程组。求解该新方程组，得到所有的偶变量后，再回代求解所有的奇变量。即约化和回代过程。由于其基本的算术操作可以向量化，适合于向量机。此方法有大量学者进行研究，提出了许多改进的方法。例如，Heller针对最后几步的短向量操作提出了不完全循环约化方法；R.Reulter结合IBM3090VF向量机的特点提出了局部循环约化法；P.Amodio针对分布式系统的特点改进了循环约化方法；最近针对此方法又提出对三对角方程组进行更大约化步的交替迭代策略。
（三）基于矩阵乘分解算法
将系数矩阵A分解成A=FT，方程Ax=b化为Fy=b和Tx=y两个方程组的并行求解。这种算法又可以分为两类：
1.重叠分解。如Wang的分裂法及其改进算法就属于这一类。P.Amodio在1993年对这类算法进行了很好的总结，用本地LU、本地LUD和本地循环约化法求解，并在1995年提出基于矩阵乘分解的并行QR算法。H.Michielse和A.Van der Vorst改变Wang算法的消元次序，提出了通信量减少的算法。李晓梅等将H.Michielse和A.Van der Vorst算法中的通信模式从单向串行改为双向并行，提出DPP算法，是目前最好的三对角方程组分布式算法之一。2000年骆志刚等中依据DPP算法，利用计算与通信重叠技术，减少处理机空闲时间取得了更好的并行效果。此类算法要求解P-1阶缩减系统。
2.不重叠分解。例如Lawrie & Sameh算法、Johsoon算法、Baron算法、Chawla在1991年提出的WZ分解算法以及Mattor在1995年提出的算法都属于这一类。此类算法要求解2P-2阶缩减系统。
（四）基于矩阵和分解算法