# Cache efficient matrix multiplication

Consider these matrices:

$A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$

$B=\begin{bmatrix}-1 & -2\\-3 & -4\end{bmatrix}$

Using standard algorithm:

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

Transpose B and do dot product row wise for A and B

$B^T=\begin{bmatrix}-1 & -3\\-2 & -4\end{bmatrix}$

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

I'd like to know whether the second version is correct in general?

And whether the second version is more cache efficient than the standard algorithm?

Why has matrix multiplication been defined as row with column?

NOTE: I do know real world implementations such as BLAS use different techniques than the naive implementation.

• If you care about cache efficiency in theory, you can have a look at cache oblivious algorithms. In practice, a lot depends on the way you set up data structures, memory accesses, and so on. – Juho Jan 5 '18 at 19:54
• "Why has matrix multiplication been defined as row with column". Because row by row or column by column doesn't give a result that is useful for anything. – gnasher729 Jan 6 '18 at 21:15

It is correct.

Mathematically, $A$, $B$ and $C$ are foremostly linear mappings between vector spaces. Say, $A:W\to X$ and $B: V\to W$, then $C = A\circ B$ is a linear mapping $V\to X$. Practically speaking, and that's where the matrix representation stems from, you represent a mapping $V\to W$ as a member of the tensor space $V^\ast\otimes W$, where $V^\ast$ is the dual space of $V$, that is, any linear mapping $V\to W$ can be written in the form $$B(v) = \sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)$$ where $b_{jk}$ are the coefficients characterising the mapping, and the $w_j$ form a convention-chosen basis of $W$ and the $f_k:V\to \mathbb{R}$ (or whatever field you're working over) basis of $V^\ast$. Then, we can see what the composition comes out as: \begin{align} C(v) = A(B(v)) =& \sum_l\sum_i x_l\cdot a_{li}\cdot g_i\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr) \\ =& \sum_{lijk} x_l\cdot a_{li}\cdot b_{jk}\cdot g_i(w_j)\cdot f_k(v) \end{align} The basis of $W$'s dual space will be chosen so that $g_i(w_j)=\delta_{ij}$, so \begin{align} C(v) =& \sum_{ljk} x_l\cdot a_{lj}\cdot b_{jk}\cdot f_k(v) \\ =:& \sum_{lk} x_l\cdot c_{lk}\cdot f_k(v) \end{align} where you have your matrix multiplication $$c_{lk} = \sum_j a_{lj}\cdot b_{jk}.$$ There are two alternative, equivalent ways to look at linear mappings, and one of them you found: you basically group $$A(w) = \sum_{li} x_l\cdot a_{li}\cdot g_i(w) = \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)(w)$$ ...which you can do because the dual space is also a vector space; $\Bigl(\sum_i a_{li}\cdot g_i\Bigr)$ are just the row vectors of $A$ which are not in fact vectors but co-vectors—and now \begin{align} A(B(v)) =& \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr) \\ =& \sum_{lk} x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_jw_j\cdot b_{jk}\Bigr)\cdot f_k(v) \end{align} ..and there in the middle is that scalar product between a row vector of $A$ and a column vector of $B$ (or, if you will, a row vector of $B^T$).

So yeah, this can be done and is often done in algorithms.

Does it help with cache? It can certainly help, if you naturally come by $B$ in transposed form. I think e.g. the Eigen library exploits this a lot, through lazy evaluation and pre-arranging intermediate results to come out transposed in the first place if deemend useful. If all you got is $B$ in un-transposed form though, well, the cost of transposing it (which is also not readily cache-friendly) may outweigh the cache penalty of multiplying in suboptimal order.

There are many approaches to this, it's a well studied field. But there's no silver bullet for the optimal transposition policy. (An interesting approach is to store matrices in Morton order, so that always both rows and columns have some cache coherence.)

• Where can I look for different approaches for doing matrix multiplication especially regarding 2D Convolution? – MinusInfinity Jan 6 '18 at 0:46
• @MinusInfinity the first consideration for a convolution is always: can you FFT it? Because that completely avoids the matrix multiplication. – leftaroundabout Jan 6 '18 at 0:50
• Does that means there should be symmetry in matrix? – MinusInfinity Jan 6 '18 at 1:04
• I don't quite understand what you mean there; perhaps you should flesh it out as a seperate question? – leftaroundabout Jan 6 '18 at 1:07
• Sure. Thanks for detailed explanation – MinusInfinity Jan 6 '18 at 1:09