The arrangement of data in computer memory is a continuing source of discussion and confusion because the language is also used in the context of arranging data in data files. We will discuss, and hopefully clarify, the usage of the language of row- and column-major ordering.

When a vector, or a 1-dimensional matrix, is stored in computer memory, the values are, ideally, stored next to each other. For example, the vector

\[A = \begin{bmatrix}1.1 & 2.2 & 3.3 & 4.4\end{bmatrix}\]

has 4 floating point values. Assuming the computer memory isn’t fragmented, the values are stored next to each other in memory. To get the first value of the vector in the C language we would use A(0), while in Fortran, by default, the first value is obtained with A(1). In the C language array indices start at 0 (0-based array index system), while Fortran array indices start at 1 (Fortran is 1-based).

If we reshape the 4 values of A into a 2×2 matrix, as

\[A = \begin{bmatrix}1.1 & 2.2\\3.3 & 4.4\end{bmatrix}\]

this can be stored in two ways in computer memory. First, lets be clear about the meaning of indices when addressing the elements of the matrix. We will adopt 1-based array indexing, so the lowest value the array indices can have will be 1, and the first element of the matrix is

\[A(1, 1) \rightarrow 1.1\]

The first index in the pair of indices \((i, j)\) is the x-, or row-value. The second index is the y-, or column-value. Then the value of the first row and second column of A is

\[A(1, 2) \rightarrow 2.2\]

while the value of the second row and first column is

\[A(2, 1) \rightarrow 3.3\]

The computer must hold the matrix A in memory, and there are two possible ways to arrange the values. The first is to list each row in order, one after another

\[A(\text{row-ordered}) = \begin{bmatrix}1.1 & 2.2 & 3.3 & 4.4\end{bmatrix}\]

which in the computer’s memory looks like

\[A(\text{row-ordered in computer memory}) = \begin{bmatrix} … \\1 & 1.1\\ 2 & 2.2\\ 3 & 3.3\\ 4 & 4.4\\ … \end{bmatrix}\]

The left column above shows example memory addresses while the right column indicates the value of the matrix element at that memory address. The important thing to note is that the data values of the matrix A are stored in contiguous memory locations. This arrangement of data values in computer memory is referred to as row-major ordering, and C is an example of a row-ordered language. The fastest way to do calculations on a matrix is always to access elements of the matrix that are close to each other in the computer’s memory. In C, the loops to go through a 3×3 matrix as quickly as possible look like

```
for(i = 0; i < 3; i++) {
```

for(j = 0; j < 3; j++) {
do_something with A[i][j];
}
}

Notice that the y-, or column-indices are the inside loop, and so, vary the fastest. This results in adjacent memory locations being accessed in turn. C is only one of the row-major languages.

The other possibility is to list the columns in order, one after another

\[A(\text{column-ordered}) = \begin{bmatrix}1.1 & 3.3 & 2.2 & 4.4\end{bmatrix}\]

\[A(\text{column-ordered in computer memory}) = \begin{bmatrix} … \\1 & 1.1\\ 2 & 3.3\\ 3 & 2.2\\ 4 & 4.4\\ … \end{bmatrix}\]

Again, the left column above shows example memory addresses while the right column indicates the value of the matrix element at that memory address. The important thing to note is that the data values of the matrix A are stored in contiguous memory locations. This arrangement of data values in computer memory is referred to as column-major ordering, and Fortran is an example of a column-ordered language. The fastest way to do calculations on a matrix is always to access elements of the matrix that are close to each other. In Fortran, the loops to go through a 3×3 matrix as quickly as possible look like

DO j = 1, 3 DO i = 1, 3 do_something_with_A(i,j) END DO END DO

In this case, the row index is varying the fastest – it is in the inside loop. This arrangement accesses elements of A stored in contiguous memory locations. This inside loop with the index i varying the fastest is going through the rows in each column. Fortran is one example of a language that uses column major ordering, others are Matlab and GNU Octave.

The key point here is that the arrangement of data in computer memory can vary with the computer language that you are using. As a programmer, you need to be aware of these structures to write efficient code.

To extend these ideas to higher dimensional matrices:

**column-major ordering**: left-most index varies fastest and work your way to the right. The left-most index will be used in the inner loop. For example, using Fortran syntax, we would write a 3-dimensional matrix in column-major order as

DO k = 1, nz DO j = 1, ny DO i = 1, nx WRITE (*,*) A(i, j, k) END DO END DO END DO

**row-major ordering**: right-most index varies fastest and work your way to the left. The right-most index will be used in the inner loop. Again, using Fortran syntax, we would write a 3-dimensional matrix in row-major order as

DO i = 1, nx DO j = 1, ny DO k = 1, nz WRITE (*,*) A(i, j, k) END DO END DO END DO

This language (i.e. row/column major) is also used away from computer languages and placement of matrices in memory. Visualization software may expect data sets in one ordering or the other. For example, in the VTK data file format, the data points are always listed in column major order. This means that the array was written by loops ordered with x varying the fastest. In an older package called OpenDX, you could specify the ordering of the data with the appropriate keyword in an input file. When using visualization software, the expected ordering of data in data files should be checked to ensure that the data appear correctly in the coordinate system.

The ordering of data in computer memory has led to language that leads to some confusion because the terms are also used in the context of ordering data in data files. When reading or writing a column-ordered data file, the data needs to be read in loops with the right-most index varying the fastest, regardless of the programming language you are using. When reading data into a visualization package, check the ordering that the package expects, to ensure that the data are placed correctly in the coordinate system.

## Leave A Comment