Algorithms and Parallel Computing

11.2 MATRIX MULTIPLICATION ALGORITHM

Assume we are given two compatible matrices M₂ and M₃ of dimensions I × K and K × J, respectively. Their product is matrix M₁ of dimension I × J. The matrix multiplication algorithm can be expressed as

(11.1)

This equation can be expressed in any serial algorithm (i.e., any computer code) as three nested loops. An outer loop iterates over the index i; the next inner loop iterates over the index j. The innermost loop iterates over the index k.

Variable M₁ in the above equation is an output variable, while variables M₂ and M₃ are input variables. The above matrix multiplication algorithm has three indices: i, j, and k, and we can think of these indices as coordinates of a point in a 3-D volume. We organize our indices in the form of a vector:

(11.2)

for given values of the indices, the vector corresponds to a point in the Z³ space [9].