Parallel householder method for linear systems

Abstract

We introduce a generalised Householder transformation which, operating on two vectors, concurrently eliminates all their elements except the first and the last. For a system of size N × N,Ax = b, the kth generalised Householder transformation W _k concurrently eliminates all the elements a _{k+1→N−k;k} in col. k and all the elements a _{k+1→N−k+1} in col. N− k+1. The product transformation W=W _n-l….W _l,n = [(N +1)/2], reduces A to Z-form. For solution of the reduced system, starting from the middle two unknowns are determined simultaneously at each step. The arithmetical operations count for the bi-directional WZ-factorisation method is 0(2N ³/3). If implemented on a 2-processor machine, the present parallel Householder method could achieve an efficiency (of processor utilization) close to 50%in comparison with the LU-factorisation method, with the additional advantage of numerical stability without the need for pivoting.

Keywords:

• Linear system
• generalised Householder transformation
• bi-directional reduction
• WZ-factorisation
• parallel Householder method

C.R. Categories:

• 5.2

^†Supported by Kuwait University Research Grant SM 118.

^†Supported by Kuwait University Research Grant SM 118.

Notes

^†Supported by Kuwait University Research Grant SM 118.