稀疏矩阵通常按列主序还是行主序存储？
Are sparse matrices typically stored in column major order or row major order?
一点背景知识：我有兴趣研究一下稀疏矩阵*向量乘法。
我一直在浏览这个稀疏矩阵数据库：
The University of Florida Sparse Matrix Collection
我注意到矩阵有 3 种格式可用：
- MATLAB (.mat)
- 矩阵市场 (.mtx)
- Harwell-Boeing (.rb)
矩阵似乎是按列主要顺序存储的（即列是一个接一个地存储，而不是一个接一个地存储行）。然而，在文献中似乎压缩稀疏行 (CSR) 格式显然是最常见的格式（参见 "Scientific Computing Kernels on the Cell Processor Samuel"）。我知道以某种方式只存储了索引 (i,j) 和这些坐标处的值，但我想我必须先重新格式化数据才能有效地执行矩阵*向量乘法。
对于我的实现，将数据按行主要顺序存储更有意义，这样一行中的元素可以按顺序访问，因为它们将存储在连续的内存地址中。
CSR 格式似乎假定数据按行主要顺序存储。所以我想知道的是：
对于稀疏矩阵，数据通常如何存储在内存中？稀疏矩阵*向量计算的一部分是否涉及将数据从列优先顺序重新分组到行优先顺序？
我问是因为我想知道这种转换是否通常在稀疏矩阵基准测试结果中被考虑。
这不是答案，但不能写在评论中。最佳表示格式取决于底层实现。例如，
让
M = [m_11 m_12 m_13; == [r1; == [c1 c2 c3]
m_21 m_22 m_23] r2]
其中 r1,2 是行，c1,2,3 是列
和
v = [v1;
v2;
v3]
您可以将 M*v 实现为
M*v = [r1.v;
r2.v]
作为向量的点积，或
M*v = v1*c1 + v2*c2 + v3*c3
其中 * 是标量向量乘法。
您可以根据矩阵的稀疏性选择格式，从而最大限度地减少操作次数。通常 rows/columns 越少越好。
恐怕没有简短的答案。最佳存储方案取决于您要解决的问题。要考虑的事情不仅是存储大小，而且从计算和硬件的角度来看，这种存储格式的访问和操作效率如何。
对于稀疏矩阵向量乘法，CSR 是一种很好的格式，因为它允许线性访问矩阵行的元素，这有利于内存和缓存性能。然而，CSR 在被乘数中引入了一种更不规则的访问模式：根据您从行中检索的索引，在不同的位置获取元素；这对缓存性能不利。 CSC 矩阵向量乘法可以消除被乘数上的不规则访问，但代价是解向量中的更多不规则访问。根据您的矩阵结构，您可以选择一个或另一个。例如，具有几行长行且具有类似非零分布的矩阵在 CSC 格式中处理可能更有效。
知名软件中的一些例子packages/tools:
- 据我所知，Matlab 默认使用列存储。
基于 Fortran 的科学代码（和 BLAS）默认也使用列存储。这主要是由于历史原因，因为 Fortran 数组最初是面向 AFAIK 列的，并且大量 Dense/Sparse BLAS 代码最初是用 Fortran 编写的。
Eigen 也默认使用列存储，但这可以自定义。
Intel MKL 要求您选择 IIRC。
Boost ublas默认使用基于行的存储格式。
PetSC, which is a widely used tool in larger scale scientific computing, uses a row based format (SequentialAIJ stands for CSR), but also allows you to choose from a wide variety of storage formats (see the MatCreate* functions on their documentation)
这个清单还可以继续。如您所见，各种工具之间存在一些差异，我怀疑标准是 SpMV 操作的性能 :) 可能是目标问题域中的通用存储格式、目标问题域中程序员的典型期望等方面，与其他库方面和现有代码的集成是使用 CSR / CSC 的主要原因。显然，这些因工具而异。
无论如何，可以找到关于稀疏存储格式的简短概述here，但在稀疏矩阵研究中提出了更多的存储格式were/are：
- 还有块存储格式，它们试图利用矩阵的局部密集子结构。例如，参见 Richard W. Vuduc 和 Hyun-Jin Moon 的 "Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure"。
- 有关稀疏格式
http://docs.scipy.org/doc/scipy/reference/sparse.html 的 Python scipy 文档中可以找到一些常见存储格式的非常简短但有用的概述。
- 有关各种格式优势的更多信息，请参阅以下文本（以及许多其他文本）：
- 稀疏线性系统的迭代方法，Yousef Saad
- SPARSKIT：用于稀疏矩阵计算的基本工具包，Tech。代表 CSRD TR 1029，CSRD，伊利诺伊大学厄巴纳，伊利诺伊州，1990 年。
- LAPACK 工作说明 50：用于线性代数运算的分布式稀疏数据结构，技术。 Rep. CS 92-169，田纳西大学计算机科学系，田纳西州诺克斯维尔，1992 年。
我一直在研究稀疏矩阵领域，为稀疏矩阵算法（例如 SpMV）创建自定义硬件架构。根据经验，一些稀疏矩阵基准测试往往会忽略各种格式之间转换的开销。这是因为，原则上，可以假设您可以调整整个算法的存储格式。 SpMV 本身很难单独使用，通常是一些较大的迭代算法（例如线性或非线性求解器）的一部分。在这种情况下，格式之间的转换成本可以分摊到整个算法的多次迭代和总运行时间中。当然，您必须证明您的假设在这种情况下成立。
作为免责声明，在我所在的领域，我们特别倾向于做出尽可能多的假设，因为实施 硬件架构 的线性求解器基准测试的成本和时间一种新的 SpMV 存储格式通常很重要（大约几个月）。在软件中工作时，通过 运行 尽可能多的基准来测试、限定和量化您的假设要容易得多，这可能需要不到一周的时间来设置 :D
一点背景知识：我有兴趣研究一下稀疏矩阵*向量乘法。
我一直在浏览这个稀疏矩阵数据库：
The University of Florida Sparse Matrix Collection
我注意到矩阵有 3 种格式可用：
- MATLAB (.mat)
- 矩阵市场 (.mtx)
- Harwell-Boeing (.rb)
矩阵似乎是按列主要顺序存储的（即列是一个接一个地存储，而不是一个接一个地存储行）。然而，在文献中似乎压缩稀疏行 (CSR) 格式显然是最常见的格式（参见 "Scientific Computing Kernels on the Cell Processor Samuel"）。我知道以某种方式只存储了索引 (i,j) 和这些坐标处的值，但我想我必须先重新格式化数据才能有效地执行矩阵*向量乘法。
对于我的实现，将数据按行主要顺序存储更有意义，这样一行中的元素可以按顺序访问，因为它们将存储在连续的内存地址中。
CSR 格式似乎假定数据按行主要顺序存储。所以我想知道的是： 对于稀疏矩阵，数据通常如何存储在内存中？稀疏矩阵*向量计算的一部分是否涉及将数据从列优先顺序重新分组到行优先顺序？ 我问是因为我想知道这种转换是否通常在稀疏矩阵基准测试结果中被考虑。
这不是答案，但不能写在评论中。最佳表示格式取决于底层实现。例如，
让
M = [m_11 m_12 m_13; == [r1; == [c1 c2 c3]
m_21 m_22 m_23] r2]
其中 r1,2 是行，c1,2,3 是列 和
v = [v1;
v2;
v3]
您可以将 M*v 实现为
M*v = [r1.v;
r2.v]
作为向量的点积，或
M*v = v1*c1 + v2*c2 + v3*c3
其中 * 是标量向量乘法。
您可以根据矩阵的稀疏性选择格式，从而最大限度地减少操作次数。通常 rows/columns 越少越好。
恐怕没有简短的答案。最佳存储方案取决于您要解决的问题。要考虑的事情不仅是存储大小，而且从计算和硬件的角度来看，这种存储格式的访问和操作效率如何。
对于稀疏矩阵向量乘法，CSR 是一种很好的格式，因为它允许线性访问矩阵行的元素，这有利于内存和缓存性能。然而，CSR 在被乘数中引入了一种更不规则的访问模式：根据您从行中检索的索引，在不同的位置获取元素；这对缓存性能不利。 CSC 矩阵向量乘法可以消除被乘数上的不规则访问，但代价是解向量中的更多不规则访问。根据您的矩阵结构，您可以选择一个或另一个。例如，具有几行长行且具有类似非零分布的矩阵在 CSC 格式中处理可能更有效。
知名软件中的一些例子packages/tools:
- 据我所知，Matlab 默认使用列存储。
基于 Fortran 的科学代码（和 BLAS）默认也使用列存储。这主要是由于历史原因，因为 Fortran 数组最初是面向 AFAIK 列的，并且大量 Dense/Sparse BLAS 代码最初是用 Fortran 编写的。
Eigen 也默认使用列存储，但这可以自定义。
Intel MKL 要求您选择 IIRC。
Boost ublas默认使用基于行的存储格式。
PetSC, which is a widely used tool in larger scale scientific computing, uses a row based format (SequentialAIJ stands for CSR), but also allows you to choose from a wide variety of storage formats (see the MatCreate* functions on their documentation)
这个清单还可以继续。如您所见，各种工具之间存在一些差异，我怀疑标准是 SpMV 操作的性能 :) 可能是目标问题域中的通用存储格式、目标问题域中程序员的典型期望等方面，与其他库方面和现有代码的集成是使用 CSR / CSC 的主要原因。显然，这些因工具而异。
无论如何，可以找到关于稀疏存储格式的简短概述here，但在稀疏矩阵研究中提出了更多的存储格式were/are：
- 还有块存储格式，它们试图利用矩阵的局部密集子结构。例如，参见 Richard W. Vuduc 和 Hyun-Jin Moon 的 "Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure"。
- 有关稀疏格式
http://docs.scipy.org/doc/scipy/reference/sparse.html的 Pythonscipy文档中可以找到一些常见存储格式的非常简短但有用的概述。 - 有关各种格式优势的更多信息，请参阅以下文本（以及许多其他文本）：
- 稀疏线性系统的迭代方法，Yousef Saad
- SPARSKIT：用于稀疏矩阵计算的基本工具包，Tech。代表 CSRD TR 1029，CSRD，伊利诺伊大学厄巴纳，伊利诺伊州，1990 年。
- LAPACK 工作说明 50：用于线性代数运算的分布式稀疏数据结构，技术。 Rep. CS 92-169，田纳西大学计算机科学系，田纳西州诺克斯维尔，1992 年。
我一直在研究稀疏矩阵领域，为稀疏矩阵算法（例如 SpMV）创建自定义硬件架构。根据经验，一些稀疏矩阵基准测试往往会忽略各种格式之间转换的开销。这是因为，原则上，可以假设您可以调整整个算法的存储格式。 SpMV 本身很难单独使用，通常是一些较大的迭代算法（例如线性或非线性求解器）的一部分。在这种情况下，格式之间的转换成本可以分摊到整个算法的多次迭代和总运行时间中。当然，您必须证明您的假设在这种情况下成立。
作为免责声明，在我所在的领域，我们特别倾向于做出尽可能多的假设，因为实施 硬件架构 的线性求解器基准测试的成本和时间一种新的 SpMV 存储格式通常很重要（大约几个月）。在软件中工作时，通过 运行 尽可能多的基准来测试、限定和量化您的假设要容易得多，这可能需要不到一周的时间来设置 :D