Subsection C.1.4 Matrix-matrix operations
ΒΆThe archetypical matrix-matrix operation is matrix-matrix multiplication:
\begin{equation*}
C := \alpha A B + \beta C,
\end{equation*}
where \(C \text{,}\) \(A \text{,}\) and \(B \) are \(m \times n \text{,}\) \(m \times k \text{,}\) and \(k \times n \text{,}\) respectively. We will ignore \(\beta \) since \(C \) can always be scaled by \(\beta \) first.
Notice that
\begin{equation*}
\begin{array}{rcl}
A B + C
\amp=\amp
A
\left( \begin{array}{c | c |c}
b_0 \amp \cdots \amp b_{n-1}
\end{array} \right)
+
\left( \begin{array}{c | c | c}
c_0 \amp \cdots \amp c_{n-1}
\end{array} \right) \\
\amp=\amp
\left( \begin{array}{c | c | c}
A b_0 + c_0 \amp \cdots \amp A b_{n-1} + c_{n-1}
\end{array} \right) .
\end{array}
\end{equation*}
Hence, this matrix-matrix multiplication requires \(n \) matrix-vector multiplications with a matrix of size \(m \times n \) for a cost of \(2 n ( m k ) = 2 m n k \text{.}\)
\begin{equation*}
\begin{array}{| l | l | c | l |}
\hline
\amp ~~\mbox{operation} \amp \mbox{cost (in flops)} \amp ~~~\mbox{comment}
\\ \hline
\mbox{gemm} \amp C := \alpha A B + \beta C \amp 2 m n k \amp
C \in \Rmxn, A \in \Rmxk, B \in \Rkxn,
\alpha, \beta \in \R \\
\amp \amp \amp \mbox{general matrix-vector multiplication}
\\ \hline
\mbox{syrk} \amp C := \alpha A A^T + \beta C \amp m^2k \amp
C \in \Rmxm, A \in \Rmxk,
\alpha, \beta \in \R \\
\amp \amp \amp C \mbox{ is symmetric} \\
\amp \amp \amp \mbox{symmetric rank-k update} \\ \hline
\mbox{trsm} \amp B := \alpha A^{-1} B \amp m^2n \amp A \in \Rmxm,
B \in \Rmxn, \alpha \in \R \\
\amp \amp \amp A \mbox{ is a triangular matrix} \\
\amp \amp \amp \mbox{triangular solve with }\\
\amp \amp \amp \mbox{multiple right-hand sides}
\\ \hline
\end{array}
\end{equation*}