IJPAM: Volume 1, No. 1 (2002)

A PARALLEL ELIMINATION ALGORITHM
FOR PENTADIAGONAL LINEAR SYSTEMS

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


Abstract.Classical elimination procedure is extended to uncouple partitioned pentadiagonal linear systems for parallel processing of their solution. In each block of equations, we need two sets of simultaneous eliminations; each set consists of two usual forward eliminations and two backward from across the succeeding block. While vertical fill-ins in the last two columns of the block on the left pose no difficulty, the purpose of the indicated eliminations is to move fill-ins in the last two rows successively two columns to the right till they reach their destination in the last two columns of each block. At the end of the elimination stage, we reach a relatively small size $2\times 2$ block tridiagonal core system. Once the core system is solved, the blocks of equations uncouple and the uncoupled subsystems are solved in parallel by back substitution. We include arithmetical operations counts for both serial and parallel implementations of the presented algorithm and illustrate the working of the algorithm by an example.

Received: January 20, 2002

AMS Subject Classification: 65F30, 15A06

Key Words and Phrases: linear systems, pentadiagonal, partitioning, elimination, parallel algorithm.

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2002
Volume: 1
Issue: 1