Efficient parallel algorithm for quasi pentadiagonal systems on a hypercube

摘要

We present an efficient algorithm for the parallel solution of pentadiagonal linear systems written in the matrix form as Ax = d, where A is a N × N quasi pentadiagonal matrix having non-zero elements at the top right and bottom left corners. The algorithm is implemented on a p-processor hypercube in three phases. In phase one, a generalization of the algorithm due to J.S. Kowalik [High Speed Computation, Springer Verlag, NY, 1984] is developed which decomposes the above matrix system into smaller quasi block tridiagonal (p + 1) × (p + 1) subsystem, which is then solved in phase two using odd even reduction method generalized for block tridiagonal systems with non-zero blocks at the top right and bottom left corners. The values of all the variables are then evaluated in phase three by backward substitution.