programs.dvi
1. procedure MAT VECT (A, x , y)
2. begin
3. for i := 0 to n − 1 do
4. begin
5. y[i] := 0;
6. for j := 0 to n − 1 do
7. y[i] := y[i] + A[i, j] × x[ j];
8. endfor;
9. end MAT VECT
Algorithm 8.1 A serial algorithm for multiplying an n × n matrix A with an n × 1 vector x to yield
an n × 1 product vector y.
1. procedure MAT MULT (A, B, C)
2. begin
3. for i := 0 to n − 1 do
4. for j := 0 to n − 1 do
5. begin
6. C[i, j] := 0;
7. for k := 0 to n − 1 do
8. C[i, j] := C[i, j] + A[i, k] × B[k, j];
9. endfor;
10. end MAT MULT
Algorithm 8.2 The conventional serial algorithm for multiplication of two n × n matrices.
1. procedure BLOCK MAT MULT (A, B, C)
2. begin
3. for i := 0 to q − 1 do
4. for j := 0 to q − 1 do
5. begin
6. Initialize all elements of Ci, j to zero;
7. for k := 0 to q − 1 do
8. Ci, j := Ci, j + Ai,k × Bk, j ;
9. endfor;
10. end BLOCK MAT MULT
Algorithm 8.3 The block matrix multiplication algorithm for n × n matrices with a block size of
(n/q) × (n/q).
1. procedure GAUSSIAN ELIMINATION (A, b, y)
2. begin
3. for k := 0 to n − 1 do /* Outer loop */
4. begin
5. for j := k + 1 to n − 1 do
6. A[k, j] := A[k, j]/A[k, k]; /* Division step */
7. y[k] := b[k]/A[k, k];
8. A[k, k] := 1;
9. for i := k + 1 to n − 1 do
10. begin
11. for j := k + 1 to n − 1 do
12. A[i, j] := A[i, j] − A[i, k] × A[k, j]; /* Elimination step */
13. b[i] := b[i] − A[i, k] × y[k];
14. A[i, k] := 0;
15. endfor; /* Line 9 */
16. endfor; /* Line 3 */
17. end GAUSSIAN ELIMINATION
Algorithm 8.4 A serial Gaussian elimination algorithm that converts the system of linear equations
Ax = b to a unit upper-triangular system U x = y. The matrix U occupies the upper-triangular
locations of A. This algorithm assumes that A[k, k] �= 0 when it is used as a divisor on lines 6 and
7.
1. procedure BACK SUBSTITUTION (U , x , y)
2. begin
3. for k := n − 1 downto 0 do /* Main loop */
4. begin
5. x[k] := y[k];
6. for i := k − 1 downto 0 do
7. y[i] := y[i] − x[k] × U [i, k];
8. endfor;
9. end BACK SUBSTITUTION
Algorithm 8.5 A serial algorithm for back-substitution. U is an upper-triangular matrix with all
entries of the principal diagonal equal to one, and all subdiagonal entries equal to zero.
1. procedure CHOLESKY (A)
2. begin
3. for k := 0 to n − 1 do
4. begin
5. A[k, k] := √A[k, k];
6. for j := k + 1 to n − 1 do
7. A[k, j] := A[k, j]/A[k, k];
8. for i := k + 1 to n − 1 do
9. for j := i to n − 1 do
10. A[i, j] := A[i, j] − A[k, i] × A[k, j];
11. endfor; /* Line 3 */
12. end CHOLESKY
Algorithm 8.6 A row-oriented Cholesky factorization algorithm.
1. procedure MAT MULT CREW PRAM (A, B, C , n)
2. begin
3. Organize the n2 processes into a logical mesh of n × n;
4. for each process Pi, j do
5. begin
6. C[i, j] := 0;
7. for k := 0 to n − 1 do
8. C[i, j] := C[i, j] + A[i, k] × B[k, j];
9. endfor;
10. end MAT MULT CREW PRAM
Algorithm 8.7 An algorithm for multiplying two n × n matrices A and B on a CREW PRAM,
yielding matrix C = A × B .
1. procedure MAT MULT EREW PRAM (A, B, C , n)
2. begin
3. Organize the n2 processes into a logical mesh of n × n;
4. for each process Pi, j do
5. begin
6. C[i, j] := 0;
7. for k := 0 to n − 1 do
8. C[i, j] := C[i, j]+
A[i, (i + j + k) mod n] × B[(i + j + k) mod n, j];
9. endfor;
10. end MAT MULT EREW PRAM
Algorithm 8.8 An algorithm for multiplying two n × n matrices A and B on an EREW PRAM,
yielding matrix C = A × B .