IJPAM: Volume 2, No. 3 (2002)

A PARALLEL ELIMINATION ALGORITHM
FOR BANDED LINEAR SYSTEMS

M.M. Chawla, R.R. Khazal
Dept. of Mathematics and Computer Science
Kuwait University
P.O. Box 5969, Safat 13060, KUWAIT

Abstract.We present a parallel algorithm for the solution of $% \beta$ -semiband linear systems of size $N\times N$ by partitioning the system into $p^{2}$ blocks each of size (). In order to uncouple the partitioned blocks, in each diagonal block $B^{\left( r\right) }$ we apply two sets of simultaneous eliminations; the first set consists of $\beta$ usual forward eliminations within the block and the second set consists of $\beta$ eliminations in the block $C^{\left( r-1\right) }$ on top of $B^{\left( r\right) }$ . While the vertical fill-ins in the last $% \beta$ columns of the block on the left of $B^{\left( r\right) }$ pose no difficulty, the purpose of the second set of eliminations is to move fill-ins in the last $\beta$ rows of $C^{\left( r-1\right) }$ successively to the right till they reach their destination in the last $\beta$ columns. At the end of the elimination stage, we reach a core block tridiagonal system with each block of size $\beta \times \beta .$ Once the core system is solved, the partitioned blocks of equations uncouple and the uncoupled subsystems can be solved in parallel by back substitution. We include arithmetic complexity for both serial and parallel implementations of the presented algorithm and illustrate the main idea of the presented parallel algorithm by an example.