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

FORTRAN was designed to solve scientific and engineering problems. Column-major storage is more natural from a scientific point of view, since the general linear algebra convention uses column-vectors and often treats matrices as concatenations of column-vectors. In matrix-vector multiplications, column-vectors reside on the right side (post-multiplication), with successive matrices added further on the left side, e.g. B*(A*x). Languages such as COBOL, PL/1, and C treat matrices as collections of row-records, hence for them the row-major order is more natural.

In linear algebra, a vector is represented by its coordinates: x = x[1]*e1 + x[2]*e2 + ... + x[n]*en where x[i] are the vector coordinates and ei is the i-th basis vector. In matrix representation, the basis vectors are column-vectors. A linear operator A then, acting on x, gives:

y = A*x = A*{x[1]*e1 + x[2]*e2 + ... x[n]*en}
        = x[1]*(A*e1) + x[2]*(A*e2) + ... x[n]*(A*en)

In matrix representation, the linear operator A consists of n columns, with column i being the result of A acting on the i-th basis vector, and A*x is then simply the linear combination of the columns of A with coefficients coming for the coordinates of x. In FORTRAN this would be:

! Zero out the result vector
DO k = 1,n
  y(k) = 0.0
END DO

! Iterate over the columns of A
DO i = 1,n
  ! Add the i-th column to the linear combination with a weight of x(i)
  w = x(i)
  DO k = 1,n
    y(k) = y(k) + w*A(k,i)
  END DO
END DO

This automatically gives preference to column-major storage of A. It might seem awkward, but back in the 50's, when FORTRAN was born, FMAC hardware and register optimisations were not at all that popular like they are now.