PARALLEL HOUSEHOLDER METHOD FOR LINEAR-SYSTEMS

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 x N, <A(x)under bar>=(b) u nder bar, the kth generalised Householder transformation W-k concurren tly eliminates all the elements a(k+1-->N-k;k) in col. k and all the e lements a(k+1-->N-k;N-k+1) in col. N-k+1. The product transformation W =W-n-1...W-1, n=[(N+1)/2], reduces A to Z-form. For solution of the re duced system, starting from the middle two unknowns are determined sim ultaneously at each step. The arithmetical operations count for the bi directional WZ-factorisation method is O(2N(3)/3). If implemented on a 2-processor machine, the present parallel Householder method could ac hieve an efficiency (of processor utilization) dose to 50% in comparis on with the LU-factorisation method, with the additional advantage of numerical stability without the need for pivoting.