Row major versus Column major layout of matrices

Question

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.

Answer 1

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.

Answer 2

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.