Skip to main content

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.

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.

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,k-1} \\ \alpha_{1,0} \amp \alpha_{1,1} \amp \cdots \amp \alpha_{1,k-1} \\ \vdots \amp \vdots \amp \amp \vdots \\ \alpha_{m-1,0} \amp \alpha_{m-1,1} \amp \cdots \amp \alpha_{m-1,k-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

Let the following picture represent data stored in memory starting at address A:

\begin{equation*} \begin{array}{ l r r} {\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

\begin{equation*} A = \end{equation*}
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.2

Let the following picture represent data stored in memory starting at address A.

\begin{equation*} \begin{array}{ l r r} {\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*}