Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

In programming dense matrix computations, is there any reason to choose a row-major layout of the over the column-major layout?

I know that depending on the layout of the matrix chosen, we need to write the appropriate code to use the cache memories effectively for speed purposes.

The row-major layout seems more natural and simpler (at least to me). But major libraries like LAPACK which are written in Fortran use the column major layout, so there must be some reason for having made this choice.

share|improve this question
    
If we consider computing b=A*x with x column vector, for row-major A we may use inner-products of vectors, A(i,:)^T x to get b(i); for column-major we may only need scalar multiplying vectors, sum_i A(:,i) x(i). It seems to me column major is much better! What do you think? –  Hui Zhang Dec 2 '12 at 7:54
    
Train yourself to like column-major. It's easy when you visualize vectors as columns, or their transposition as rows. It makes visualization of matrix multiplication very simple, and makes it easy to follow lots of published math. –  Mike Dunlavey Dec 3 '12 at 20:12

2 Answers 2

The column major layout is the scheme used by Fortran and that's why it's used in LAPACK and other libraries.

In general it is much more efficient in terms of memory bandwidth usage and cache performance to access the elements of an array in the order in which they're laid out in memory. Depending on how your matrices are stored, you'll want to pick algorithms that take advantage of this.

share|improve this answer

In vacuum without considering any existing software, there's no reason to prefer column major over row major from the code point of view. However, most mathematical literature is written in a way that groups vectors into a matrix by storing them as columns instead of rows. For example when you write the full eigenvalue equation $AX=X\Lambda$, the $X$ matrix contains all the eigenvectors written out in columns. You never really see it written the other way (though I hear that statistics folks like row vectors). Therefore, it was natural that the earliest software assumed column major format so that if you have a matrix which is a set of vectors, the storage of any single vector is contiguous. Thus, I imagine that tradition has just been carried forward to the present day, and if you want to interact with the ye olde Fortran, you want to use column major. So pretty much all highly efficient numerical linear algebra is done in column major.

The reason C is row major is somewhat of a consequence of its array syntax; you declare a 3 row by 2 column array as double a[3][2], and later indices vary faster than earlier indices, which for 2D arrays makes it row major. Combine this with the natural Western reading order from left to right, it makes row major seem more natural.

share|improve this answer
    
I think these are poor arguments. The fact that the last index in '''double a[3][2]''' varies fastest is not a coincidence -- it was a concious design decision in just the same way as it was a conscious design decision in Fortran to do it the other way around when you have a '''real(3,2)''' array. –  Wolfgang Bangerth Dec 2 '12 at 5:20
    
Furthermore, it's not true any more that pretty much all highly efficient numerical linear algebra is column major. This may still be true for BLAS and LAPACK, but it's not true at all for every major linear algebra library that has appeared in the past 15 years: for example, both PETSc and Trilinos use row major sparse matrix storage formats. –  Wolfgang Bangerth Dec 2 '12 at 5:22
    
I'm aware that the C convention was a conscious decision, probably based off of natural reading order. I meant that it probably wasn't designed with numerical linear algebra in mind, making it a coincidence that it's row major. Second, I didn't intend the argument to hold for sparse matrices, only dense. For sparse, it's a bit of a mixed back out there, with both compressed row and column formats. –  Victor Liu Dec 2 '12 at 10:58
4  
Not to belabor the point, but C was originally a systems language, based off earlier languages B and BCPL, running on systems like the PDP-11 which did not originally have floating point numbers. To say that they designed it with numerics in mind is quite a stretch. –  Victor Liu Dec 2 '12 at 20:19
5  
Been there, etc. The reason matrices in C move the last index fastest is because C does not have matrices. It has vectors of vectors, that can be transparently implemented as solid blocks of memory, or as arrays of pointers to arrays. Making index-order compatible with Fortran was (I'm guessing) not even on Dennis Ritchie's radar. –  Mike Dunlavey Dec 3 '12 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.