7.6 PARALLEL NUMERICAL ALGORITHMS 205■ 7.6.3 Solving Systems of Linear Equations with an
SIMD Algorithm
In Section 4.3, we looked at a sequential algorithm to solve a system of N lin-
ear equations with N unknowns using the Gauss-Jordan method. For that
algorithm, we represented the linear equations as a matrix with N rows and N
- 1 columns and got our solution by doing operations on rows and between
rows until we were left with an identity matrix in the first N rows and col-
umns. The values of the unknowns then appeared in the last column of this
matrix. We now present an SIMD algorithm for the CREW PRAM model to
accomplish the same thing. Our discussion below will use the notation of Mij
to represent the memory location for the coefficient of the jth unknown
(columN) in the ith equation (row).
Before presenting the parallel algorithm, let’s review the sequential algo-
rithm presented in Section 4.3. We said that the process would begin by divid-
ing the first row by the value in the first column of that row. So, if the first
value in the first row was 5, each value in that row would be divided by 5.
Next, the sequential algorithm would subtract from every other row the first
row multiplied by the first value of that other row. For example, if the second
row had a value of 12 in the first column, the second row would have the first
row times 12 subtracted from it.
The following CREW PRAM model algorithm requires N* (N + 1) pro-
cessors, each handling the update of just one element in our matrix. As with
our sequential algorithm for the Gauss-Jordan method, this parallel algorithm
does not handle problems with round-off error or matrix singularity.
for x = 1 to N do
Parallel Start
for y = x to N+1 do
Pxy reads Mxx into factor and Mxy into value
Pxy calculates value/factor and writes it to Mxy
end for y
Parallel End
Parallel Start
for y = x to N+1 do
for z = 1 to N do
if x ≠ z
Pzy reads Mzy into current, Mzx into factor,
and Mxy into value
Pzy calculates current - factor * value and
writes it to Mzy