GEMV: With fused-vector operations

Content

We now consider matrix partitions that contain more than one row or column:

Algorithm for GEMV

Considering the two kinds of partitions, we get

  • \(y \leftarrow \beta\, y\)

  • \(\mathbf{if}\; \text{incRow}_\text{A} > \text{incCol}_\text{A}\)

    • \(\text{Consider row-wise quasi-equidistant partitions with respect to}\;f:\)

      • \[A = \begin{pmatrix}\mathbf{A}_0 \\\hline\mathbf{A}_1 \\\hline\vdots \\\hline\mathbf{A}_{m_b-1} \\\hline\mathbf{A}_{m_b}\end{pmatrix}, \quad y = \begin{pmatrix}\mathbf{y}_0 \\\hline\mathbf{y}_1 \\\hline\vdots \\\hline\mathbf{y}_{m_b-1} \\\hline\mathbf{y}_{m_b}\end{pmatrix}, \quad m_b = \left\lfloor \frac{m}{f} \right\rfloor\]
    • \(\mathbf{for}\; i=0,\dots,m_b-1\)

      • \( \mathbf{y}_i \leftarrow \mathbf{y}_i + \alpha\, \mathbf{A}_i x \)

    • Consider \(A_{m_b}\) row wise

    • \(\mathbf{for}\; i=m_b \cdot f,\dots,m\)

      • \( y_i \leftarrow y_i + \alpha\, a_i^T x \)

  • \(\mathbf{else}\)

    • \(\text{Consider column-wise quasi-equidistant partitions with respect to}\;f:\)

      • \[A = \left(\begin{array}{c|c|c|c}\mathbf{A}_0 &\mathbf{A}_1 &\dots &\mathbf{A}_{n_b}\end{array}\right), \quad x = \left(\begin{array}{c}\mathbf{x}_1 \\\mathbf{x}_2 \\\vdots \\\mathbf{x}_{n_b}\end{array}\right), \quad n_b = \left\lfloor \frac{n}{f} \right\rfloor\]
    • \(\mathbf{for}\; j=0,\dots,n_b-1\)

      • \( y \leftarrow y + \alpha\, \mathbf{A}_{j} \mathbf{x}_j \)

    • Consider \(A_{n_b}\) col wise

    • \(\mathbf{for}\; j=n_b \cdot f,\dots,n\)

      • \( y \leftarrow y + \alpha\, a_{j} x_j \)

Exercise