C. H. Walshaw
The topic of distributed parallel solution of tridiagonal linear systems using partition methods is discussed with particular reference to diagonally dominant matrices. We introduce a two-way matrix factorization and use it to develop a new algorithm for P processors which results in a global reduced matrix of order P/2. We present a proof that diagonal dominance in the full matrix is retained by the reduced matrix.
Sparse systems of differential equations provide a rich field to utilise such algorithms and we apply distributed parallel methods to several problems. We provide some new numerical results for two systems of ordinary differential equations - the Becker-Döring equations and the KP lattice. Some sample timing results are included both for these problems, the alternating direction method, a diagonal leap-frog grid and some communications routines used extensively in all the parallel computations reported here. The results indicate good speed-up can be achieved even whilst employing implicit integration and in particular in two or greater dimensions a high processor effciency can be attained.