On recursive decoupling method for solving tridiagonal linear systems

Abstract

A recursive decoupling method was introduced by Evans [2] to form the basis of a parallel tridiagonal linear system solver. Recently, Evans [3] has described another version of the recursive decoupling strategy making it into an efficient parallel algorithm by using a series of rank one updating stages performed in parallel to combine the solutions of the 2 ×2 subsystems. However, in his version of the decoupling method the diagonal elements of the coefficient matrix of the system are modified. In the present paper we present an alternative implementation of the recursive decoupling method which is in the same vein with the essential difference that our implementation obviates the need to modify the diagonal elements of the coefficient matrix. The total arithmetical operations count for the present version of recursive decoupling method is , while that for the parallel variant of cyclic reduction, termed PARACR, is (Hockney and Jesshope [4]).

Keywords:

• Tridiagonal linear systems
• recursive decoupling
• 2×2 submatrices
• parallel processing

C.R. Categories:

• G.1.3
• F.1.2
• C.1.2