关于三对角线性方程组的高效并行计算

摘要

求解三对角线性方程组已有很多并行算法。我们知道,倍增法需18log2N步,奇偶消去法需12log2N步,循环奇偶约化法需10log2N步。文[5]给出一种仅需5logN步的并行算法,但算法较复杂,而且在稳定性方面有一定的局限性。本文重新分析了奇偶消去法的计算复杂性。结果表明,其并行步数可达4log2N步,而所需处理机台数不超过6N台。从而,奇偶消去法不失为一种稳定有效的并行算法。特别地,对T型三对角方程组,提供了一个复杂性与[3]相当的新算法。