对于很多元素为零的稀疏矩阵，仅存储非零元素可使矩阵操作效率更高。现有许多种稀疏矩阵的存储方式，但是多数采用相同的基本技术，即存储矩阵所有的非零元素到一个线性数组中，并提供辅助数组来描述原数组中非零元素的位置。
以下是几种常见的稀疏矩阵存储格式：
1. Coordinate Format (COO)
这种存储方式的主要优点是灵活、简单。仅存储非零元素以及每个非零元素的坐标。
使用3个数组进行存储：values, rows, andcolumn
参数：矩阵中非零元素的数量 nnz，3个数组的长度均为nnz.
2. Diagonal Storage Format (DIA)
If the sparse matrix has diagonals containing only zero elements, then the diagonal storage format can be used to reduce the amount of information needed to locate the non-zero elements. This storage format is particularly useful in many applications where the matrix arises from a finite element or finite difference discretization.
The Intel MKL diagonal storage format is specified by two arrays:values anddistance, and two parameters:ndiag, which is the number of non-empty diagonals, andlval, which is the declared leading dimension in the calling (sub)programs.
A real or complex two-dimensional array is dimensioned aslval byndiag. Each column of it contains the non-zero elements of certain diagonal ofA. The key point of the storage is that each element invalues retains the row number of the original matrix. To achieve this diagonals in the lower triangular part of the matrix are padded from the top, and those in the upper triangular part are padded from the bottom. Note that the value ofdistance(i) is the number of elements to be padded for diagonali.
An integer array with dimension ndiag. Elementi of the arraydistance is the distance betweeni-diagonal and the main diagonal. The distance is positive if the diagonal is above the main diagonal, and negative if the diagonal is below the main diagonal. The main diagonal has a distance equal to zero.
3. Compressed Sparse Row Format (CSR)
The Intel MKL compressed sparse row (CSR) format is specified by four arrays: thevalues,columns,pointerB, andpointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.
A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the row-major storage mapping described above.
Element i of the integer array columns is the number of the column inA that contains thei-th value in thevalues array.
Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a rowj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1.
An integer array that contains row indices, such thatpointerE(j)-pointerB(1)is the index of the element in thevalues array that is last non-zero element in a row j of A.
4. Compressed Sparse Column Format (CSC)
The compressed sparse column format (CSC) is similar to the CSR format, but the columns are used instead the rows. In other words, the CSC format is identical to the CSR format for the transposed matrix. The CSR format is specified by four arrays: values, columns, pointerB, and pointerE. The following table describes the arrays in terms of the values, row, and column positions of the non-zero elements in a sparse matrixA.
A real or complex array that contains the non-zero elements ofA. Values of the non-zero elements ofA are mapped into thevalues array using the column-major storage mapping.
Element i of the integer array rows is the number of the row inA that contains thei-th value in thevalues array.
Element j of this integer array gives the index of the element in thevalues array that is first non-zero element in a columnj ofA. Note that this index is equal topointerB(j) -pointerB(1)+1.
An integer array that contains column indices, such thatpointerE(j)-pointerB(1)is the index of the element in thevalues array that is last non-zero element in a column j ofA.
5. Skyline Storage Format
The skyline storage format is important for the direct sparse solvers, and it is well suited for Cholesky or LU decomposition when no pivoting is required.
The skyline storage format accepted in Intel MKL can store only triangular matrix or triangular part of a matrix. This format is specified by two arrays:values andpointers. The following table describes these arrays:
A scalar array. For a lower triangular matrix it contains the set of elements from each row of the matrix starting from the first non-zero element to and including the diagonal element. For an upper triangular matrix it contains the set of elements from each column of the matrix starting with the first non-zero element down to and including the diagonal element. Encountered zero elements are included in the sets.
An integer array with dimension(m+1), where m is the number of rows for lower triangle (columns for the upper triangle).pointers(i) -pointers(1)+1gives the index of element invalues that is first non-zero element in row (column)i. The value ofpointers(m+1)is set tonnz+pointers(1), wherennz is the number of elements in the arrayvalues.
6. Block Compressed Sparse Row Format (BSR)
The Intel MKL block compressed sparse row (BSR) format for sparse matrices is specified by four arrays:values,columns,pointerB, andpointerE. The following table describes these arrays.
A real array that contains the elements of the non-zero blocks of a sparse matrix. The elements are stored block-by-block in row-major order. A non-zero block is the block that contains at least one non-zero element. All elements of non-zero blocks are stored, even if some of them is equal to zero. Within each non-zero block elements are stored in column-major order in the case of one-based indexing, and in row-major order in the case of the zero-based indexing.
Element i of the integer array columns is the number of the column in the block matrix that contains thei-th non-zero block.
Element j of this integer array gives the index of the element in thecolumns array that is first non-zero block in a rowj of the block matrix.
Element j of this integer array gives the index of the element in thecolumns array that contains the last non-zero block in a rowj of the block matrix plus 1.
7. ELLPACK (ELL)
8. Hybrid (HYB)
由ELL+COO两种格式结合而成。
选择稀疏矩阵存储格式的一些经验：
1. DIA和ELL格式在进行稀疏矩阵-矢量乘积(sparse matrix-vector products)时效率最高，所以它们是应用迭代法(如共轭梯度法)解稀疏线性系统最快的格式；
2. COO和CSR格式比起DIA和ELL来，更加灵活，易于操作；
3. ELL的优点是快速，而COO优点是灵活，二者结合后的HYB格式是一种不错的稀疏矩阵表示格式；
4. 根据Nathan Bell的工作，CSR格式在存储稀疏矩阵时非零元素平均使用的字节数(Bytes per Nonzero Entry)最为稳定（float类型约为8.5，double类型约为12.5），而DIA格式存储数据的非零元素平均使用的字节数与矩阵类型有较大关 系，适合于StructuredMesh结构的稀疏矩阵（float类型约为4.05，double类型约为8.10），对于Unstructured Mesh以及Random Matrix,DIA格式使用的字节数是CSR格式的十几倍；
5. 从我使用过的一些线性代数计算库来说，COO格式常用于从文件中进行稀疏矩阵的读写，如matrix market即采用COO格式，而CSR格式常用于读入数据后进行稀疏矩阵计算。
其他相关链接：
1. Intel MKL 库中使用的稀疏矩阵格式
http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-9FCEB1C4-670D-4738-81D2-F378013412B0.htm
2. Sparse Matrix Representations & Iterative Solvers, Lesson 1 by Nathan Bell
http://www.bu.edu/pasi/files/2011/01/NathanBell1-10-1000.pdf
欢迎来到我的CSDN博客：http://blog.csdn.net/anshan1984/
相关推荐
以下是关于几种常见的稀疏矩阵存储格式的详细说明及它们的存储效率对比： 1. **Coordinate (COO)**: COO是最直观的存储方式，每个非零元素由一个三元组（行号，列号，数值）表示。虽然易于理解，但这种格式存储冗余...
### Python稀疏矩阵-Sparse存储和转换详解 #### 一、引言 在科学计算、机器学习以及数据分析等领域，我们经常会遇到大型矩阵，其中大部分元素为零，这类矩阵被称为**稀疏矩阵**。如果直接使用Python标准库如NumPy来...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种特殊的矩阵表示形式，主要应用于处理大量元素为零的矩阵。由于实际应用中，很多矩阵大部分元素可能是0，如图像处理、网络分析等领域，直接存储所有元素会浪费大量...
在 MATLAB 中，稀疏矩阵（Sparse Matrix）是一种高效的数据结构，尤其适用于处理大量数据中包含大量零元素的情况。本文将深入探讨稀疏矩阵的概念、创建方法、存储方式、操作及优化，以及它在节点优化中的应用。 ...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种用于存储大量零元素的矩阵表示方法，因为对于具有大量零元素的矩阵，直接使用二维数组存储所有元素会浪费大量的存储空间。本教程将详细介绍如何使用C语言实现稀疏...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种用于存储大量零元素的矩阵数据结构，因为常规的二维数组表示方式在处理零元素众多的矩阵时会浪费大量的存储空间。稀疏矩阵转置是矩阵运算中的一个重要操作，它涉及...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种用于存储大量零元素的矩阵表示方法，尤其在处理大型数据集时非常有用。相比常规的二维数组表示，稀疏矩阵的存储和计算效率更高，因为它主要关注非零元素。本报告将...
在本示例中，作者使用C++实现了一个稀疏矩阵类`SparseMatrix`，其中包含了矩阵的基本操作方法，如转置等。接下来，我们将详细介绍该类的设计思路和关键方法的实现细节。 #### 四、类定义详解 ##### 4.1 `Sparse...
然后，编写相应的函数来执行上述运算，例如`SparseMatrix Add(SparseMatrix &m1, SparseMatrix &m2)`、`SparseMatrix Subtract(SparseMatrix &m1, SparseMatrix &m2)`、`SparseMatrix Multiply(SparseMatrix &m1, ...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种特殊的矩阵表示方法，主要应用于处理大量元素为零的矩阵。由于在很多实际问题中，非零元素的数量远少于矩阵的总元素数量，使用稀疏矩阵可以大大节省存储空间，提高...
在本课程设计中，我们将深入探讨稀疏矩阵的C++实现，旨在理解和应用这种数据结构来优化存储和计算性能。 稀疏矩阵的核心思想是只存储非零元素，避免浪费内存空间在大量的零元素上。常见的存储方法有两种：三元组...
2. **SparseMatrix 类**：实现稀疏矩阵的基本功能，包括初始化、转置、相乘和相加等操作。 ```cpp template class Trituple { public: int row, col; T value; void set(int r, int c, T v) { row = r; col = c...
再假设有一组非零元素的行、列和值，可以创建稀疏矩阵`SparseMatrix`： ```matlab inds1 = [1, 2, 4]; inds2 = [1, 2, 4]; numbers = [1, 2, 4]; SparseMatrix = sparse(inds1, inds2, numbers); ``` 最后，如果想将...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种特殊的矩阵表示方法，用于处理大量元素为零的矩阵。当矩阵中的非零元素远少于总元素数量时，使用稀疏矩阵可以显著节省存储空间和计算时间。本文将详细介绍如何用...
例如，可能有一个名为`SparseMatrix`的类，其中包含了构造函数初始化矩阵，`addElement`函数添加非零元素，`display`函数打印矩阵，以及`add`、`subtract`、`multiply`等函数实现矩阵的加减乘运算。 在实现稀疏矩阵...
其中，稀疏矩阵（Sparse Matrix）是一种特别适用于处理大量元素为零的矩阵的数据结构。当矩阵中非零元素的比例很小，使用常规的二维数组存储方式会浪费大量空间。为了解决这个问题，C语言提供了几种实现稀疏矩阵存储...
link *create_sparse_matrix(int s, int t) { link *head = (link *)malloc(sizeof(link)); ... return head; } ``` （3）插入结点函数： ```c void insert_node(link *head, int i, int j, datatype v) { link ...
在计算机科学中，稀疏矩阵（Sparse Matrix）是一种用于存储大量零元素的矩阵表示方法，因为对于具有大量零元素的矩阵，直接使用二维数组存储会浪费大量的存储空间。在这种情况下，三元组（Triplet）表示法是一种常用...
在实际应用中，选择合适的数据存储格式对于提高算法的性能、节省计算资源有着重要的意义。对于大规模稀疏矩阵的处理，MATLAB的稀疏矩阵存储方式显示出其独特的优势和重要性。它不仅可以有效地降低存储需求，还可以...
在计算机科学中，数据结构是组织和管理大量数据的关键元素，而稀疏矩阵（Sparse Matrix）是一种特殊的数据结构，尤其适用于处理大量元素为零的矩阵。稀疏矩阵运算的高效处理对于解决各种计算问题，特别是在图形学、...