A recursive doubling algorithm for inverting tridiagonal matrices

Abstract

Evans [2, 3] introduced the method of recursive point partitioning algorithm for the solution of sparse banded matrix systems and investigated the “one-line at a time” strategy for the solution of tridiagonal linear systems. Recursive block partitioning schemes resulting from variation in the size of the block structure using “two-lines at a time” have been investigated for both the tridiagonal and the quindiagonal matrix systems in Okolie [6]. The case of partitioning strategy for an nth order system has been considered by Evans and Okolie [4] resulting in a recursive decoupling algorithm for tridiagonal linear systems. Following the recursive point partitioning algorithm of Evans [2, 3], Chawla et al [1] developed a recursive partitioning algorithm for inverting tridiagonal matrices. In the present paper we present a method for inverting tridiagonal matrices by adopting the strategy resulting in a recursive doubling algorithm; the present algorithm has a highly parallel structure.

Keywords:

• Tridiagonal matrices
• inversion
• recursive doubling
• recursive partitioning
• degree of parallelism

C.R. Categories:

• G.1.3
• G.1.0