Analysis of Algorithms : An Active Learning Approach

206 PARALLEL ALGORITHMS

end if

end for z

end for y

Parallel End

end for x

In this algorithm, the outer loop steps through each of the unknowns. The

first parallel block will divide the current row by the appropriate element.

The second parallel block then subtracts the proper multiple of this row from

every other. In this second block, the outer loop handles the remaining col-

umns that still need adjustment and the inner loop does this for all of the

equations.

7.6.4

1. Trace the mesh network matrix multiplication as in Fig. 7.6 for the multi-
   plication of the matrices


2. Trace the mesh network matrix multiplication as in Fig. 7.6 for the multi-
   plication of the matrices


3. Trace the mesh network matrix multiplication as in Fig. 7.6 for the multi-
   plication of the matrices


4. Do an analysis of the run time and cost of the parallel Gauss-Jordan method
   for solving a system of linear equations. Your analysis should determine the
   number of multiplication or division operations and the number of addition
   or subtraction operations. How does this compare to the sequential algo-
   rithm for the Gauss-Jordan method?

■7.6.4 EXERCISES

23

74

and^51

29

82

35

and^32

74

15

46

72

and^823

519