Skip to main content

Subsection C.1.3 Matrix-vector operations

The following "matrix-vector" operations play an important role.

  • Matrix-vector multiplication: \(y:= \alpha A x + \beta y \text{,}\) where \(A \in \R^{m \times n}\text{.}\)

    Let's ignore \(\beta \) because it almost always equals \(1 \text{.}\) If not, we can start by scaling \(y \text{.}\) Next, we observe that

    \begin{equation*} \alpha A x + y = \alpha \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) x + y = \left( \begin{array}{c} \alpha (\widetilde a_0^T x) + \psi_0\\ \hline \vdots \\ \hline \alpha (\widetilde a_{m-1}^T x) + \psi_{m-1} \end{array} \right). \end{equation*}

    We notice that the cost equals, roughly, \(m \) dot products with vectors of size \(n \) for a total of (approximately) \(2 m n \) flops.

  • Rank-1 update: \(A:= \alpha x y^T + A \text{,}\) where \(A \in \R^{m \times n}\text{.}\)

    Notice that

    \begin{equation*} \begin{array}{rcl} \alpha x y^T + A \amp = \amp \alpha x \left( \begin{array}{c | c | c} \psi_0 \amp \cdots \amp \psi_{n-1} \end{array} \right) + \left( \begin{array}{c | c | c} a_0 \amp \cdots \amp a_{n-1} \end{array} \right) \\ \amp = \amp \left( \begin{array}{c | c | c} ( \alpha \psi_0 ) x + a_0 \amp \cdots \amp ( \alpha \psi_{n-1} ) x + a_{n-1} \end{array} \right). \end{array} \end{equation*}

    We notice that the cost equals, roughly, \(n \) axpy operations products with vectors of size \(m \) for a total of (approximately) \(2 m n \) flops.

\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.3.1. 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.

Matrix-vector operations with an \(m \times n \) matrix require \(O( mn ) \) flops.

login