A direct incomplete factorization method for parallel solution of tridiagonal linear systems

Abstract

For the direct solution of tridiagonal linear systems Ax = d, the best known serial algorithm is based on LU-factorization of the coefficient matrix A. In the present paper we consider extending the idea to partitioned tridiagonal matrices. Let A be partitioned: A = (A _{(i, j)}) so that the diagonal blocks A( _i,i )are tridiagonal. We seek a factorization of A into L = (L _{(i j)} and U = (U _{(i j)} ), partitioned conformally. For the diagonal blocks of A we require the classical factorization: A( _ii ) = L _(i,i) U _(i,i) , L _(i,i) unit lower bidiagonal and U _(i,i) upper bidiagonal. But, because of the presence of a non-zero element in each of the off-diagonal blocks of A, it is necessary to have Lupper block bidiagonal and U lower block bidiagonal, with only last row of L_(i,i+1) and last column of U_(i,i-1) filled. To avoid any interlocking/updating during/after the factorization stage, each of these last row and column in each block are required to have their last elements as zeros. On completion of the determination of Land U,A-LU leaves a tridiagonal matrix B leading directly to the “core system”. Once the core system is solved, the solution of the given system is obtained in parallel across the blocks. For a system of size N = np, the arithmetical operations count for the parallel algorithm, employing p processors, is 17(N/p) + 8p - 24.

Keywords:

• Tridiagonal linear system
• classical factorization
• Thomas algorithm
• partitioning
• incomplete factorization
• core system
• parallel algorithm

Keywords:

• C.R. Categories:
• G.1.3
• G.1.0.