A DIRECT INCOMPLETE FACTORIZATION METHOD FOR PARALLEL SOLUTION OF TRIDIAGONAL LINEAR-SYSTEMS

For the direct solution of tridiagonal linear systems Ax = d, the best known serial algorithm is based on LU-factorization of the coefficien t matrix A. In the present paper we consider extending the idea to par titioned tridiagonal matrices. Let A be partitioned: A = (A((i,j))) so that the diagonal blocks A((i,j)) are tridiagonal. We seek a factoriz ation of A into L = (L((i,j))) and U = (U-(i,U-j)), partitioned confor mally. For the diagonal blocks of A we require the classical factoriza tion: A((i,i)) = L((i,i)) U-(i,U-i), L((i,i)) unit lower bidiagonal an d U-(i,U-i) upper bidiagonal. But, because of the presence of a non-ze ro element in each of the off-diagonal blocks of A, it is necessary to have L upper block bidiagonal and U lower block bidiagonal, with only last row of L((i,i+1)) and last column of U-(i,U-i-1) filled. To avoi d 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 L and U , A-LU leaves a tridiagonal matrix B leading directly to the ''core sy stem''. Once the core system is solved, the solution of the given syst em is obtained in parallel across the blocks. For a system of size N = np, the arithmetical operations count for the parallel algorithm, emp loying p processors, is 17(N/p)+8p-24.