Among several types of parallel computers the MIMD machines are most general. They are capable of executing multiple streams of instructions upon multiple streams of data simultaneously, unlike array processors that handle multiple data streams but can only execute the same instruction on all the data streams. One such computer is the Heterogeneous Element Processor (HEP). The machine consists of a number of process execution modules, each with its own data memory connected to the HEP switch. Each module can access its own data memory bank directly, but access to most of the memory is through the switch. The HEP machine in its maximal configuration can execute up to 160 million instructions per second. The machine has served as a learning tool for many researchers investigating parallel algorithms, coding methods and systems software. One of the earliest applications of HEP was solving linear algebraic equations and manipulating matrices. The Givens method of annihilating the nonzero subdiagonal element of a matrix is an obvious candidate for parallelizations since many elements can be eliminated simultaneously. The specific method under consideration is the fast Givens transformation due to Gentleman. The method is used to solve the nXn system of linear equations \(Ax=b\) in two steps:
(1) factorize the augmented matrix (A,b), i.e. compute D, R and b such that \(Q(A,b)=D^{\frac{1}{2}}(R,\hat b)\), where R is upper-triangular, Q is the product of all orthogonal transformations required to triangularize A, and D in diagonal,
(2) solve \(Rx=\hat b.\)
Two algorithms are considered - one using \(0(n^ 2)\) processors and the second using 0(n) processors. In the first case it is possible to solve \(Ax=b\) in time proportional to \(T_ p=11n-15\) using \(p=3/4 n^ 2+3/2n\) processors. In the second case only \(p=\lceil(n-1)/2\rceil\) processors are used but the solution time is \(T_ p=6n^ 2+0(n)\). These theoretical results have been verified using the HEP computer.