Matrix-Matrix Multiplication
Suppose we want to multiply $m \times n$ matrix $A$ on $n \times p$ matrix $B$, we get an $m \times p$ matrix $C$
What is matrix-matrix multiplication in terms of Linear Transformations?
- Let $A$ be an $m \times n$ matrix,
- then there's a linear transformation $T_A \ : \ \mathbb R^n \to \mathbb R^m$: $T_A(\mathbf x) = A \mathbf x$ where $A \mathbf x$ is Matrix-Vector Multiplication
- now let $B$ be an $n \times k$ matrix, then $T_B \ : \ \mathbb R^m \to \mathbb R^k$: $T_B(\mathbf y) = B \mathbf x$
- what is $T_A \circ T_B$? It's $T_A \circ T_B \ : \ \mathbb R^k \to \mathbb R^m $
- $(T_A \circ T_B)(\mathbf x) = T_A \big( T_B(\mathbf x) \big) = T_A \big( B \mathbf x \big) = A \, B \, \mathbf x$
- $AB$ is matrix-matrix multiplication
Multiplication
We can see matrix by matrix multiplication from 5 different positions:
- row by column multiplication
- column at a time
- row at a time
- as sum of outer products
- block multiplication
All of them are equivalent and lead to the same result
Row By Columns
This is usual dot product multiplication:
- for each row of matrix $A$ we calculate a dot product with each column of matrix $B$
-
- $c_{ij} = (\text{row $i$ of $A$})^T \times (\text{col $j$ of $B$}) = \sum\limits_{k=1}^{m} c_{ik} b_{kj}$
Column at a Time
For each column $\mathbf{b}_j$ of $B$
- we multiply each column of $A$ with $\mathbf{b}_j$ - like in column at a time for matrix by vector
-
- [math]\mathbf{c}_j = \begin{bmatrix}
\mathop{a_1}\limits_|^| \ \mathop{a_2}\limits_|^| \ \cdots \ \mathop{a_n}\limits_|^|
\end{bmatrix} \times \mathbf{b}_j[/math]
- so each $\mathbf{c}_j$ is a combination of columns of $A$
Row at a Time
For each row $\mathbf{a}^T_i$ of $A$
- multiply $\mathbf{a}^T_i$ with each rows of $B$ - like for left vector multiplication
-
- $\mathbf{c}^T_i = \mathbf{a}^T_i \times B$
- Note that we can see this as Column at a Time case, but transposed:
- row at a time in $A\times B = C$ is the same as column at a time in $B^T \times A^T = C^T$
For $i$ from 1 to $n$,
- multiply column of $A$ $\mathbf{a}_i$ by row of $B$ $\mathbf{b}^T_i$
- it gives us a rank-1 matrix - an outer product
- then sum over all $i$
-
- $C = AB = \sum\limits_{i=1}^n \mathbf{a}_i \mathbf{b}^T_i$
Block Multiplication
$AB = \left[ \begin{array}{c|c}
A_1 & A_2 \\
\hline
A_3 & A_4
\end{array} \right] \times
\left[ \begin{array}{c|c}
B_1 & B_2 \\
\hline
B_3 & B_4
\end{array} \right] =
\left[ \begin{array}{c|c}
A_1B_1 + A_2B_3 & A_3B_1 + A_4B_3 \\
\hline
A_1B2 + A_2B_1 & A_3B_1 + A_4B_3
\end{array} \right] = C$
Properties
Transposition
- $(AB)^T = B^T A^T$
- $(A_1 \cdot \ ... \ \cdot A_n)^T = A_n^T \cdot \ ... \ \cdot A_1^T$
Inverse Matrices
$(AB)^{-1} = B^{-1} A^{-1}$
- inverse of product is product of inverses in the reversed order
- check:
- $AB \times B^{-1} A^{-1} = A \times (B B^{-1}) \times A^{-1} = A \times I \times A^{-1} A \times A^{-1} = I$
- $B^{-1} A^{-1} \times AB = B^{-1} \times (A^{-1} A) \times B = B^{-1} \times B = I$
Row Space and Column Space
Let's show the following:
- $C(A\, B) \subseteq C(A)$
- $R(A \, B) \subseteq R(B)$
- where $C(\cdot)$ is Column Space and $R(\cdot)$ is Row Space
Image of linear transformation
- first, let's consider a linear transformation of an $m \times n$ matrix $A$
- $T_A \ : \ \mathbb R^n \to \mathbb R^m$ : $T_A(\mathbf x) = A \mathbf x$
- Column Space of $A$ is the image of $T_A$ in $\mathbb R^m$
$C(A\, B) \subseteq C(A)$
- let $A$ be an $m \times n$ matrix and $B$ be an $k \times n$
- $A \, B$ corresponds to linear transformation $T_A \circ T_B$
- so need to show that $\text{image}(T_A \circ T_B) \subseteq \text{image}(T_A)$
-
What about $R(A \, B) \subseteq R(B)$?
- $R(A \, B) = C(B^T A^T) \subseteq C(B^T) = R(B)$
Implementation
Possible Ways to Implement
Suppose we want to implement the update $C = C + AB$:
- let $A$ be $m \times r$ matrix and $B$ be $r \times n$
- then $C$ is $m \times n$ matrix
- $C$ can be initialized as an array filled with zeros - then $C$ will contain the results of $AB$
for (int i = 0; i < m; i++) {
for (int j = 0; i < n; j++) {
for (int k = 0; k < r; k++) {
C[i, j] = C[i, j] + A[i, k] * B[k, j]
}
}
}
Note that here it is not important in which order we do the loop:
- it can be
ijk
, ikj
, etc, with $3! = 6$ possible ways
Order |
Inner Loop |
Outer Loops |
Inner Loop Access
|
ijk |
dot |
Vector-Matrix Mult |
$A$ row, $B$ col
|
jik |
dot |
Matrix-Vector Mult |
$A$ row, $B$ col
|
ikj |
saxpy |
Row gaxpy |
$B$ row, $C$ row
|
jki |
saxpy |
Col gaxpy |
$A$ col, $C$ col
|
kij |
saxpy |
row outer product |
$A$ row, $C$ row
|
kji |
saxpy |
col outer product |
$A$ col, $C$ col
|
Some details:
- The way inner loop accesses the data is important for storing the data to make it faster - data should be contiguos in memory
-
dot
is usual Vector-Vector multiplication
-
saxpy
(scalar $a$ times $x$ plus $y$): $y \leftarrow ax + y$
-
gaxpy
(generalized axpy
): $y \leftarrow y + Ax$
- outer product update: $A \leftarrow A + xy^T$
Suppose we have two sparce matrices $A$ and $B$
- we store these matrices as
(row_num, col_num, value)
triples
- it is easy to use SQL for this multiplication
Sparse matrix multiplication with SQL
select a.row_num, b.col_num, sum(a.value * b.value)
from A a, B b
where a.col_num = b.row_num
group by a.row_num, b.col_num;
MapReduce
- We can translate this SQL expression into MapReduce
- Link [1]
E.g. Apache Flink:
matrixA.join(matrixB).where(1).equalTo(0)
.map(new ProjectJoinResultMapper()).groupBy(0, 1).sum(2)
Full code of Matrix Multiplication in Flink: [2]
Sources