On increasing the parallelism in numerical algorithms

Parallel algorithms have been designed for the past 20 years initially by parallelising existing sequential algorithms for many different parallel architectures. More recently parallel strategies have been identified and utilised resulting in many new parallel algorithms. However the analysis of such algorithms reveals that further strategies can be applied to increase the parallelism. One of these, i.e., increasing the computational capacity in each processing node can reduce the congestion/communication for shared memory/distributed memory multiprocessor systems and dramatically improve the performance of the algorithm. Two algorithms are identified and studied, i.e., the cyclic reduction method for solving large tridiagonal linear systems in which the odd/even sequence is increased to a ‘stride of 3’ or more resulting in an improved algorithm. Similarly the Gaussian Elimination method for solving linear systems in which one element is eliminated at a time can be adapted to parallel form in which two elements are simultaneously eliminated resulting in the Parallel Implicit Elimination (P.I.E.) method. Numerical results are presented to support the analyses.