行主要与列主要布局的矩阵 [英] Row major versus Column major layout of matrices

问题描述

在编程密集矩阵计算中，是否有任何理由选择列主布局的行主布局？我知道取决于所选矩阵的布局，我们需要编写适当的代码以有效地使用高速缓存以达到速度目的。

行主布局看起来更自然，更简单（在至少对我来说）。但是使用Fortran编写的LAPACK等主要库使用列主要布局，因此必须有一些原因做出选择。 解决方案

FORTRAN旨在解决科学和工程问题。从科学角度来看，列主存储更自然，因为一般的线性代数约定使用列向量，并且经常将矩阵视为列向量的连接。在矩阵向量乘法中，列向量驻留在右侧（乘法后），连续的矩阵在左侧进一步加入，例如， B *（A * X）。像COBOL，PL / 1和C这样的语言把矩阵当作行记录的集合，因此对他们而言，行优先级更自然。

在线性代数，一个向量由它的坐标表示： x = x [1] * e1 + x [2] * e2 + ... + x [n] * en code> x [i] 是矢量坐标， ei 是 i - 基向量。在矩阵表示中，基向量是列向量。然后，作用于 x 的线性算子 A 给出：

  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）
  

在矩阵表示中，线性算子 A 由 n 列，列 i 是 A 作用于 i - >基向量，而 A * x 就是 A 的列的线性组合，系数的坐标为 x 。在FORTRAN中，这将是：



 ！将结果向量零
 DO k = 1，n 
 y（k）= 0.0 
 END DO 
 
！遍历A 
 DO i = 1，n 
的列！将第i列加入到权重为x（i）
w = x（i）
 DO k = 1，n 
y（k）= y（k）+ w * A（k，i）
 END DO 
 END DO 
  

自动优先选择 A 的列主存储。这似乎很尴尬，但早在50年代，当FORTRAN出生时，FMAC硬件和寄存器优化并不像现在这样受欢迎。

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.

解决方案

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.

这篇关于行主要与列主要布局的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！