0
$\begingroup$

From Scientific Parallel Computing by Scott Ridgway:

Definition: The work/memory ratio of an algorithm is the ratio $\rho_{wm}$ of the number of floating point operations to the number of memory locations referenced.

What is the ratio $\rho_{wm}$ of the number of floating point operations to the number of data values that have to be obtained from memory, or written to memory, in the computation of the product of two square matrices $A=(a_{ij})$ and $B$ which is defined by

$$(AB)_{ij}:=\sum_{k=1}^n a_{ik}b_{kj} ~~~~~~~\text{for $i, j=1,...,n$}$$

as a function of $n$? (Assume that both $A$ and $B$ must be obtained from memory and the product is written back to memory. However, the denominator should just be the volume of the data, not the number of memory references that might occur in particular algorithm. For example, the term $b_{11}$ occurs $n$ times in the above equation but should be counted only once.)


Attempted Solution:

The number $n$ of floating point operations is $n$ multiples times 2 and $(n-1)$ adds for each $(AB)_{ij}$ for a total of $(2n-1)2n=4n^2-2n$ FLOP's to compute AB.

The number of memory locations involved is $n^2$ for $A$, $n^2$ for $B$, and $n$ for AB. So, the total number of memory locations is $2n^2+n$.

Thus the ratio $\rho_{wm}$ of the number of floating point operations to the number of data values (i.e., number of memory locations) involved in the algorithm is

$$\rho_{wm}=\frac{4n^2-2n}{2n^2+n}\approx 2$$

for large $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.