4.1.3.2 Algorithms for $C_{n_1\times n_3} \;:=\; C_{n_1\times n_3} + A_{n_1\times n_2} \ast B_{n_2\times n_3}$

1. inner product
   

   
        DO 
   $i \;:=\; 1  ,  n_1$ 
   
   
   DO 
   $j \;:=\; 1  ,  n_3$ 
   
   
   $c_{i,j} \;:=\; c_{i,j} + \left\langle A_{i,\ast},B_{\ast,j} \right\rangle$ 
   
   
   END DO 
   
   
   END DO 
   
   
   

   • Rowise access on $A$, columnwise access on $B$
     $\Longrightarrow$ memory access conflicts.
   • Access on $C$ is scalar $\Longrightarrow$ poor vectorization properties.
   • Parallelization $\Leftrightarrow$ Distribution of matrices.
2. middle product
   

   
        DO 
   $j \;:=\; 1  ,  n_3$ 
   
   
   DO 
   $k \;:=\; 1  ,  n_2$ 
   
   
   $C_{\ast,j} \;:=\; C_{\ast,j} + A_{\ast,k}\ast B_{k,j}$ 
   
   
   END DO 
   
   
   END DO 
   
   
   

   • In the inner loop $B_{k,j}$ acts as a scalar, the remaining terms are vectors. $\Longrightarrow$ Daxpy
   • $\Longrightarrow$ Efficient use of vector pipes and memory bandwidth from cache.
   • The loop on $k$ represents the Matrix-by-Vector operation from BLAS2.
   • Columnwise access on $A$ and $C$ is required.
   • If $A$ and $C$ are rowise stored then the subscripts $j$ and $i$ have to be exchanged in the algorithm.
3. outer product
   

   
        DO 
   $k \;:=\; 1  ,  n_2$ 
   
   
   DO 
   $j \;:=\; 1  ,  n_3$ 
   
   
   $C_{\ast,j} \;:=\; C_{\ast,j} + A_{\ast,k}\ast B_{k,j}$ 
   
   
   END DO 
   
   
   END DO 
   
   
   

   • Similar to middle product, vector $A_{\ast,k}$ is constant in the $j$-loop.