Skip to main content

Subsection 4.4.5 {Cost}

Consider the matrix-matrix multiplication \(C = A B \) where \(C \in \mathbb{R}^{m \times n} \text{,}\) \(A \in \mathbb{R}^{m \times k} \text{,}\) and \(B \in \mathbb{R}^{k \times n} \text{.}\) Let us examine what the cost of this operation is:

  • We argued that, by definition, the \(j \)th column of \(C \text{,}\) \(c_j \text{,}\) is computed by the matrix-vector multiplication \(A b_j \text{,}\) where \(b_j \) is the \(j \)th column of \(B \text{.}\)

  • Last week we learned that a matrix-vector multiplication of a \(m \times k \) matrix times a vector of size \(k \) requires \(2 m k \) floating point operations (flops).

  • \(C \) has \(n \) columns (since it is a \(m \times n \) matrix.).

Putting all these observations together yields a cost of

\begin{equation*} n \times ( 2 m k ) = 2 m n k \mbox{ flops}. \end{equation*}
Ponder This 4.4.5.1.

Recall that the dot product of two vectors of size \(k \) requires (approximately) \(2 k \) flops. We learned in the previous units that if \(C = A B \) then \(\gamma_{i,j} \) equals the dot product of the \(i \)th row of \(A \) and the \(j \)th column of \(B \text{.}\) Use this to give an alternative justification that a matrix multiplication requires \(2 m n k \) flops.

Solution

\(C \) has \(m n \) elements, each of which is computed with a dot product of size \(k\text{.}\) Thus, the cost is, approximately, \(m n ( 2 k ) = 2 m n k \text{.}\)

login