Added to Favorites

Popular Searches

In computing, row-major order and column-major order describe methods for storing multidimensional arrays in linear memory. Following standard matrix notation, rows are identified by the first index of a two-dimensional array and columns by the second index. Array layout is critical for correctly passing arrays between programs written in different languages. It is also important for performance when traversing an array because accessing array elements that are contiguous in memory is usually faster than accessing elements which are not, due to caching.## Row-major order

In row-major storage, a multidimensional array in linear memory is accessed such that rows are stored one after the other. It is the approach used by the C programming language as well as many other languages, with the notable exceptions of Fortran and MATLAB.offset = row*NUMCOLS + column
Where NUMCOLS is the number of columns in the array.## Column-major order

Column-major order is a similar method of flattening arrays onto linear memory, but the columns are listed in sequence. The programming languages Fortran and MATLAB use column-major ordering. The arrayoffset = row + column*NUMROWS
where NUMROWS represents the number of rows in the array—in this case, 2.## Generalization to higher dimensions

# sum_{k=1}^d left(prod_{ell

k+1}^d N_ell right) n_k
# sum_{k=1}^d left(prod_{ell

1}^{k-1} N_ell right) n_k
## See also

## References

Row-major order is used in C; column-major order is used in Fortran and Matlab.

When using row-major order, the difference between addresses of array cells in increasing rows is larger than addresses of cells in increasing columns. For example, consider this 2×3 array:

1 2 3

4 5 6

Declaring this array in C as

would find the array laid-out in linear memory as:

1 2 3 4 5 6

The difference in offset from one column to the next is 1 and from one row to the next is 3. The linear offset from the beginning of the array to any given element A[row][column] can then be computed as:

Note that this technique generalizes, so a 2×2×2 array looks like:

1 2 3

4 5 6

if stored in linear memory with column-major order would look like the following:

1 4 2 5 3 6

With columns listed first. The memory offset could then be computed as:

Treating a row-major array as a column-major array is the same as transposing it. Because performing a transpose requires data movement, and is quite difficult to do in-place for non-square matrices, such transpositions are rarely performed explicitly. For example, software libraries for linear algebra, such as the BLAS, typically provide options to specify that certain matrices are to be interpreted in transposed order to avoid the necessity of data movement.

It is possible to generalize both of these concepts to arrays with greater than two dimensions. For higher-dimensional arrays, the ordering determines which dimensions of the array are more consecutive in memory. Any of the dimensions could be consecutive, just as a two-dimensional array could be listed column-first or row-first. The difference in offset between listings of that dimension would then be determined by a product of other dimensions. It is uncommon, however, to have any variation except ordering dimensions first to last or last to first. These two variations correspond to row-major and column-major, respectively.

More explicitly, consider a d-dimensional array with dimensions N_{k} (k=1...d). A given element of this array is specified by a tuple $(n\_1,\; n\_2,\; ldots,\; n\_d)$ of d (zero-based) indices $n\_k\; in\; [0,N\_k\; -\; 1]$. In row-major order, the memory-offset of this element is given by:

- $n\_d\; +\; N\_d\; cdot\; (n\_\{d-1\}\; +\; N\_\{d-1\}\; cdot\; (n\_\{d-2\}\; +\; N\_\{d-2\}\; cdot\; (cdots\; +\; N\_2\; n\_1)cdots)))$

In column-major order, the memory-offset of this element is given by:

- $n\_1\; +\; N\_1\; cdot\; (n\_2\; +\; N\_2\; cdot\; (n\_3\; +\; N\_3\; cdot\; (cdots\; +\; N\_\{d-1\}\; n\_d)cdots)))$

Note that the difference between row-major and column-major order is simply that the order of the dimensions is reversed. Equivalently, in row-major order the rightmost indices vary faster as one steps through consecutive memory locations, while in column-major order the leftmost indices vary faster.

- Matrix representation
- Vectorization (mathematics), the equivalent of turning a matrix into the corresponding column-major vector.

- Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (Addison-Wesley: New York, 1997).

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 24, 2008 at 14:52:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 24, 2008 at 14:52:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.