Confusion about row-major and column-major

[Jef Driesen]

I'm working on a project where i need to exchange multidimensional data
between C/C++ (row-major) and matlab (column-major). I understand the
difference between those two mappings to linear memory.

Suppose I need an S1 x S2 x ... x Sn dimensional array A. I can have the
same layout in memory by reversing the dimensions:

A[S1]...[Sn] == A(Sn,...,S1)

where I used the C/C++ notation for row-major and the matlab notation
for column-major (and forget about the issue of zero-based vs one-based
access). So far no problem.

But when I start "naming" the dimensions (with row and column), this
reversing does not seem to hold anymore. Let my explain that by
progressively adding dimensions in both cases: (r=row,c=column,p=plane)

C/C++ (row-major):

1D: [c] --> row vector
2D: [r][c]
3D: [p][r][c]

Matlab (column-major):

1D: (r) --> column vector
2D: (r,c)
3D: (r,c,p)

As you can see in 3D, the order of the dimensions is not what I
expected. r and c are not in reverse order. And the more I start
reasoning about it, the more I get confused. What am I missing?

 

[Heinz Ozwirk]

C/C++ (row-major):

1D: [c] --> row vector
2D: [r][c]
3D: [p][r][c]

Matlab (column-major):

1D: (r) --> column vector
2D: (r,c)
3D: (r,c,p)

As you can see in 3D, the order of the dimensions is not what I expected.
r and c are not in reverse order. And the more I start reasoning about it,
the more I get confused. What am I missing?

You start with two different things - a row vector in C++ and a column
vector in Matlab. I don't know what Matlab does, but in C++ you get

int A1[n1];
one array with n1 elements

int A2[n2][n1];
n2 arrays, where each element is an array with n1 elements

int A3[n3][n2][n1];
n3 arrays, where each element is an array with n2 elements, where each
element is an array with n1 elements.

You can call A1 a row vector or a column vector. C++ doesn't care, but it
influences the use of 2D or 3D arrays. If you call A1 a row vector, the last
subscript refers to a column, the second to last to a row, and the third to
last to a plane. (I don't have names for other dimensions, so I better stop
here.) Now if you call A1 a column vector, the last subscript selects its
row, the second to last its column, and the third to last again selects a
plane. Using your notation, in the second case you get

1D: [r]
2D: [c][r]
3D: [p][c][r]

What you have to be carefull with, is the mapping to linear memory. For a 1D
array it is easy. In memory you have A1[0], A1[1], ... A1[n1-1]. For a 2D
array you get A2[0][0], A2[0][1], ... A2[0][n1-1], A2[1][...], ...
A2[n2-1][n1-1].

For a 3D array you'll find A3[i3][i2][i1] at offset (i3 * n2 + i2) * n1 + i1
in linear memory (ignoring the size of individual elements).

HTH
Heinz

 

[Jef Driesen]

C/C++ (row-major):

1D: [c] --> row vector
2D: [r][c]
3D: [p][r][c]

Matlab (column-major):

1D: (r) --> column vector
2D: (r,c)
3D: (r,c,p)

As you can see in 3D, the order of the dimensions is not what I expected.
r and c are not in reverse order. And the more I start reasoning about it,
the more I get confused. What am I missing?

You start with two different things - a row vector in C++ and a column
vector in Matlab. I don't know what Matlab does, but in C++ you get

I started with a row vector in C++ and a column vector in Matlab,
because that seemed to me the most "natural" way, associated with each
memory layout.

The matlab notation for a 3D array is A(row,column,plane).

int A1[n1];
one array with n1 elements

int A2[n2][n1];
n2 arrays, where each element is an array with n1 elements

int A3[n3][n2][n1];
n3 arrays, where each element is an array with n2 elements, where each
element is an array with n1 elements.

As long as you don't start naming the dimensions, everything is fine.
This is basically the structure (I hope my ascii drawing does not get
destroyed):

A3
---
| | -> A2
--- ---
| | | | -> A1
--- --- ---
| | | | | |
--- --- ---
| | | |
--- ---
| |
---

You can call A1 a row vector or a column vector. C++ doesn't care, but it
influences the use of 2D or 3D arrays. If you call A1 a row vector, the last
subscript refers to a column, the second to last to a row, and the third to
last to a plane. (I don't have names for other dimensions, so I better stop
here.) Now if you call A1 a column vector, the last subscript selects its
row, the second to last its column, and the third to last again selects a
plane. Using your notation, in the second case you get

1D: [r]
2D: [c][r]
3D: [p][c][r]

For the 3D case this is perfectly consistent with idea of reversing the
dimensions. But now the last dimensions (index [r], which is actually a
column) is stored continuously in memory. And this contradicts with the
term row-major.

What you have to be carefull with, is the mapping to linear memory. For a 1D
array it is easy. In memory you have A1[0], A1[1], ... A1[n1-1]. For a 2D
array you get A2[0][0], A2[0][1], ... A2[0][n1-1], A2[1][...], ...
A2[n2-1][n1-1].

For a 3D array you'll find A3[i3][i2][i1] at offset (i3 * n2 + i2) * n1 + i1
in linear memory (ignoring the size of individual elements).

Mapping an element to linear memory is not too difficult because it does
not depend on my naming issue.