Skip to main content

Unit C.1.5 Summary

We repeat the various tables regarding the cost of the various operations.

\begin{equation*} \begin{array}{| l | l | c | l |} \hline \amp ~~\mbox{operation} \amp \mbox{cost (in flops)} \amp ~~~\mbox{comment} \\ \hline \mbox{dot} \amp \alpha := x^T y \amp 2 m \amp x, y \in \Rm, \alpha \in \R \\ \hline \mbox{axpy} \amp y := \alpha x + y \amp 2 m \amp x, y \in \Rm, \alpha \in \R \\ \hline \mbox{scal} \amp x := \alpha x \amp m \amp x \in \Rm, \alpha \in \R \\ \hline \mbox{invscal} \amp x := x / \alpha \amp m \amp x \in \Rm, \alpha \in \R \\ \hline \end{array} \end{equation*}
Figure C.1.5.1. Cost of various vector-vector operations.
\begin{equation*} \begin{array}{| l | l | c | l |} \hline \amp ~~\mbox{operation} \amp \mbox{cost (in flops)} \amp ~~~\mbox{comment} \\ \hline \mbox{gemv} \amp y := \alpha A x + \beta y \amp 2 m n \amp A \in \Rmxn, x \in \Rn, y \in \Rm, \alpha, \beta \in \R \\ \amp \amp \amp \mbox{general matrix-vector multiplication} \\ \hline \mbox{ger} \amp A := \alpha x y^T + A \amp 2 m n \amp A \in \Rmxn, x \in \Rm, y \in \Rn, \alpha \in \R \\ \amp \amp \amp \mbox{rank-1 update} \\ \hline \mbox{syr} \amp A := \alpha x x^T + A \amp m^2 \amp A \in \Rmxm, x \in \Rm, \alpha \in \R \\ \amp \amp \amp A \mbox{ is symmetric} \\ \amp \amp \amp \mbox{symmetric rank-1 update} \\ \hline \mbox{syr2} \amp A := \alpha ( x y^T+y x^T ) + A \amp 2m^2 \amp A \in \Rmxm, x,y \in \Rm, \alpha \in \R \\ \amp \amp \amp A \mbox{ is symmetric} \\ \amp \amp \amp \mbox{symmetric rank-2 update} \\ \hline \mbox{trsv} \amp x := A^{-1} x \amp m^2 \amp A \in \Rmxm, x \in \Rm \\ \amp \amp \amp A \mbox{ is a triangular matrix} \\ \amp \amp \amp \mbox{triangular solve} \\ \hline \end{array} \end{equation*}
Figure C.1.5.2. Cost of various matrix-vector operations. For symmetric matrices, only the upper or lower triangular part is stored and updated. This (approximately) halves the cost. Instead of computing \(x := A^{-1} x \) when \(A \) is triangular, one solves \(A z = x \) and overwrites \(x\) with the result.
\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*}
Figure C.1.5.3. Cost of various matrix-matrix operations. For symmetric matrices, only the upper or lower triangular part is stored and updated. This (approximately) halves the cost. Instead of computing \(B := A^{-1} B \) when \(A \) is triangular, one solves \(A X = B \) and overwrites \(B\) with the result.