A Parallel Elimination Method for "Periodic" Tridiagonal Systems

We extend the elimination method of Chawla and Khazal [1] to uncouple partitioned blocks of "periodic" tridiagonal linear systems. At each step of the elimination stage, we now need three simultaneous eliminations: within each block, one usual forward elimination and one backward elimination from across the succeeding block, and one elimination in the last row of the last block. An interesting feature of the present elimination procedure is that at the end of it, the property of periodicity of the original system is now passed on to the core system . Once the core system is solved, the blocks uncouple and the solution is obtained in parallel from each block by back substitution. For a system of size N , the classical elimination has an arithmetical operations count of 17N . A best serial algorithm, based on the Sherman-Morrison formula, has an operations count of 0 14N . The present parallel elimination algorithm, employing p partition blocks, has an operations count of O 17N p and, in comparison with the Sherman-Morrison algorithm, it can achieve an efficiency of nearly 82% on a p -processor machine.

Keywords:

• Periodic Tridiagonal Systems
• Classical Elimination
• Partitioning
• Parallel Elimination
• Sherman-Morrison Formula
• Efficiency