Unit 1.2.1 Mapping matrices to memory
¶ Matrices are usually visualized as two-dimensional arrays of numbers while computer memory is inherently one-dimensional in the way it is addressed. So, we need to agree on how we are going to store matrices in memory.
VIDEO
Consider the matrix
\begin{equation*}
\left(\begin{array}{rrr} 1 \amp -2 \amp 2\\ -1 \amp 1 \amp 3\\ -2 \amp 2 \amp -1 \end{array}\right)
\end{equation*}
from the opener of this week. In memory, this may be stored in a one-dimentional array A by columns:
\begin{equation*}
\begin{array}{ l r r}
{\tt A[0]} \amp\longrightarrow\amp 1 \\
{\tt A[1]}\amp \longrightarrow\amp -1 \\
{\tt A[2]} \amp\longrightarrow\amp -2
\\ \hline
{\tt A[3]}\amp \longrightarrow\amp -2 \\
{\tt A[4]} \amp \longrightarrow\amp 1 \\
{\tt A[5]} \amp \longrightarrow \amp 2 \\ \hline
{\tt A[6]} \amp \longrightarrow \amp 2 \\
{\tt A[7]} \amp \longrightarrow \amp 3 \\
{\tt A[8]} \amp \longrightarrow \amp -1 \\
\end{array}
\end{equation*}
which is known as column-major ordering.
VIDEO
More generally, consider the matrix
\begin{equation*}
\left(\begin{array}{c c c c}
\alpha_{0,0} \amp \alpha_{0,1} \amp \cdots \amp \alpha_{0,n-1} \\
\alpha_{1,0} \amp \alpha_{1,1} \amp \cdots \amp \alpha_{1,n-1} \\
\vdots \amp \vdots \amp \amp \vdots \\
\alpha_{m-1,0} \amp \alpha_{m-1,1} \amp \cdots \amp \alpha_{m-1,n-1}
\end{array}
\right).
\end{equation*}
Column-major ordering would store this in array A as illustrated by Figure 1.2.1 . .
\begin{equation*}
\begin{array}{ l r l c c }
{\tt A[0]} \amp \amp
{\tt A[{\color{red} 0}*m+{\color{blue} 0}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} 0},{\color{red} 0}} \\
{\tt A[1]} \amp \amp
{\tt A[{\color{red} 0}*m+{\color{blue} 1}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} 1},{\color{red} 0}} \\
\amp \amp
\amp \vdots \\
{\tt A[m-1]} \amp \amp
{\tt A[{\color{red} 0}*m+{\color{blue} {(m-1)}}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} {m-1}},{\color{red} 0}}
\\ \hline
{\tt A[m]} \amp \amp {\tt A[{\color{red} 1}*m+{\color{blue} 0}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} 0},{\color{red} 1}} \\
{\tt A[m+1]} \amp \amp
{\tt A[{\color{red} 1}*m+{\color{blue} 1}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} 1},{\color{red} 1}} \\
\amp \amp
\amp \vdots \\
\amp \amp
{\tt A[{\color{red} 1}*m+{\color{blue} {(m-1)}}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} {m-1}},{\color{red} 1}}
\\ \hline
\amp \amp
~ \amp \vdots \amp \\
\amp \amp
{\tt A[{\color{red} j}*m+{\color{blue} i}]} \amp \longrightarrow \amp
\alpha_{{\color{blue} i},{\color{red} j}} \\
\\
\amp \amp
\amp \vdots \amp
\\ \hline
\amp \amp
{\tt A[{\color{red} {(n-1)}}*m+{\color{blue} 0}]} \amp \longrightarrow \amp
\alpha_{{\color{blue} 0},{\color{red} {n-1}}} \\
\amp \amp
{\tt A[{\color{red} {(n-1)}}*m+{\color{blue} 1}]} \amp \longrightarrow \amp
\alpha_{{\color{blue} 1},{\color{red} {n-1}}} \\
\amp\amp\amp \vdots \\
\amp \amp
{\tt A[{\color{red} {(n-1)}}*m+{\color{blue} {(m-1)}}]} \amp \longrightarrow\amp
\alpha_{{\color{blue} {m-1}},{\color{red} {n-1}}}
\\
\end{array}
\end{equation*}
Figure 1.2.1. Mapping of \(m \times n \) matrix \(A \) to memory with column-major order. Obviously, one could use the alternative known as row-major ordering.
Homework 1.2.1.1 .
Let the following picture represent data stored in memory starting at address A:
\begin{equation*}
\begin{array}{ l r r}
\amp \amp 3 \\
{\tt A[0]} \amp\longrightarrow\amp 1 \\
\amp\amp -1 \\
\amp\amp -2
\\
\amp\amp -2 \\
\amp\amp 1 \\
\amp\amp 2 \\
\amp\amp 2 \\
\end{array}
\end{equation*}
and let \(A \) be the \(2 \times 3 \) matrix stored there in column-major order. Then
\(A = \)
Answer
\begin{equation*}
A =
\left(\begin{array}{rrr}
1 \amp -2 \amp 1 \\
-1 \amp -2 \amp 2
\end{array}
\right)
\end{equation*}
Homework 1.2.1.2 .
Let the following picture represent data stored in memory starting at address A.
\begin{equation*}
\begin{array}{ l r r}
\amp \amp 3 \\
{\tt A[0]} \amp\longrightarrow\amp 1 \\
\amp\amp -1 \\
\amp\amp -2
\\
\amp\amp -2 \\
\amp\amp 1 \\
\amp\amp 2 \\
\amp\amp 2 \\
\end{array}
\end{equation*}
and let \(A \) be the \(2 \times 3 \) matrix stored there in row-major order. Then
\begin{equation*}
A =
\end{equation*}
Answer
\begin{equation*}
A =
\left(\begin{array}{rrr}
1 \amp -1 \amp -2 \\
-2 \amp 1 \amp 2
\end{array}
\right)
\end{equation*}
