矩阵的行主序和列主序布局

Question

在编写密集矩阵计算时，选择行主布局还是列主布局有什么原因吗？

我知道，根据所选矩阵的布局，我们需要编写适当的代码以有效利用缓存内存来提高速度。

行主布局似乎更自然和简单（至少对我来说是这样）。但像Fortran编写的LAPACK这样的主要库使用列主布局，因此必须有某种原因选择了这种布局。

- smilingbuddha

Answer 1

FORTRAN旨在解决科学和工程问题。从科学的角度来看，列主存储更加自然，因为一般的线性代数约定使用列向量，并且经常将矩阵视为列向量的连接。在矩阵-向量乘法中，列向量位于右侧(后乘)，连续的矩阵进一步添加到左侧，例如B*(A*x)。诸如COBOL、PL/1和C之类的语言将矩阵视为行记录的集合，因此对它们来说，行优先顺序更加自然。

在线性代数中，向量由其坐标表示：x = x[1]*e1 + x[2]*e2 + ... + x[n]*en，其中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 的列以坐标为系数的线性组合。在 FORTRAN 中，可以表示为：

A(1:n) * x(1:n)

! 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

这自动将优先选择A的列主存储。 这可能看起来很别扭，但在20世纪50年代出生的FORTRAN时期，FMAC硬件和寄存器优化并不像现在那样流行。

- Hristo Iliev

---

你将A*x看作是A的列的线性组合。我将A*x看作是x和A的行的点积向量。在你的示例中，先迭代k再迭代i，这样你就会得到一个更偏爱以行为主存储的A`版本。 - atablash

我很久以前在一本关于Fortran历史的书中读到过这个。不幸的是，记忆已经逐渐模糊，我不记得那本书的名字了，否则我会给出参考的。无论如何，列的线性组合方法被证明是一个好选择，因为它可以在早期向量超级计算机上实现高效，而点积向量需要一个能够执行水平求和的向量单元。 - Hristo Iliev

Answer 2

我没有看到任何区别。将多维矩阵转换为线性内存顺序的方式都很好。转换方程非常相似。

还有 / 和 \ ，以及大端和小端。有人做了一个选择，后来另一个人做出了另一种选择。

- M. S. B.