[Eigen中文文档] 稀疏矩阵操作

文档总目录

英文原文(Sparse matrix manipulations)

处理和解决稀疏问题涉及各种模块，总结如下：

稀疏矩阵格式

在许多应用中（例如，有限元方法），通常要处理非常大的矩阵，其中只有少数系数不为零。在这种情况下，可以通过使用仅存储非零系数的特殊表示来减少内存消耗并提高性能。这样的矩阵称为稀疏矩阵。

SparseMatrix 类

类 SparseMatrix 是 Eigen 的稀疏模块的主要稀疏矩阵表示；它提供高性能和低内存使用率。它实现了广泛使用的压缩列（或行）存储方案的更通用变体。 它由四个紧凑数组组成：

• Values：存储非零的系数值。
• InnerIndices：存储非零系数的行（或列）索引。
• OuterStarts：存储每一列（或行）第一个非零系数在前两个数组中的索引，最后一个元素为前两个数组的大小。
• InnerNNZs：存储每列（或行）的非零系数个数。

其中，Inner 指的是内部向量，它是列主矩阵的列，或行主矩阵的行。Outer 指的是另一个方向。

如下例子中更好的解释了这个存储方案：

有矩阵：
$$ \begin{bmatrix} 0&3&0&0&0 \\ 22&0&0&0&17 \\ 7&5&0&1&0 \\ 0&0&0&0&0 \\ 0&0&14&0&8 \\ \end{bmatrix} $$
其可能的稀疏列主元表示之一为：

Values:          22   7    _    3    5    14   _    _    1    _    17    8
InnerIndices:    1    2    _    0    2    4    _    _    2    _    1     4
OuterStarts:     0    3    5    8    10   12
InnerNNZs:       2    2    1    1    2

目前，保证给定内部向量的元素始终按递增的内部索引排序。_ 表示可用于快速插入新元素的可用空间。假设不需要重新分配，随机元素的插入复杂度为 O(nnz_j) ，其中 nnz_j 是相应内部向量的非零系数个数。另一方面，在给定的内部向量中插入具有递增内部索引的元素效率更高，因为这只需要增加相应的 InnerNNZs 条目，这是一个 O(1) 操作。

没有可用空间的情况是一种特殊情况，称为压缩模式。它对应于广泛使用的压缩列（或行）存储方案（CCS 或 CRS）。任何 SparseMatrix 对象都可以通过调用 SparseMatrix::makeCompressed() 函数转换为这种形式。在这种情况下，可以注意到 InnerNNZs 数组与 OuterStarts 是冗余的，因为有等式：InnerNNZs[j] == OuterStarts[j+1] - OuterStarts[j]。因此，实际上调用 SparseMatrix::makeCompressed() 会释放这个缓冲区。

值得注意的是，Eigen 对外部库的大多数包装器都需要压缩矩阵作为输入。

Eigen 运算的结果总是产生压缩的稀疏矩阵。另一方面，将新元素插入 SparseMatrix 会将其转换为未压缩模式。

这是先前以压缩模式表示的矩阵：

Values:         22   7    3    5    14   1    17   8
InnerIndices:   1    2    0    2    4    2    1    4
OuterStarts:    0    2    4    5    6    8

SparseVector 是 SparseMatrix 的特例，其中仅存储 Values 和 InnerIndices 数组。SparseVector 没有压缩/未压缩模式的概念。

第一个示例

在描述每个单独的类之前，让我们从以下典型示例开始：使用有限差分格式和 Dirichlet 边界条件在规则二维网格上求解拉普拉斯方程 $Δu=0$ 。这样的问题可以在数学上表示为以下形式的线性问题，$Ax = b$，其中 $x$ 是大小为 $m$ 的未知向量（在我们的例子中，是像素的值），$b$ 是由边界条件产生的右侧矢量，并且 $A$ 是一个大小为 $m*m$ 由拉普拉斯算子离散化产生的仅包含少数非零元素的矩阵。

示例代码如下：

#include <Eigen/Sparse>
#include <vector>
#include <iostream>

typedef Eigen::SparseMatrix<double> SpMat; // declares a column-major sparse matrix type of double
typedef Eigen::Triplet<double> T;

void buildProblem(std::vector<T>& coefficients, Eigen::VectorXd& b, int n);
void saveAsBitmap(const Eigen::VectorXd& x, int n, const char* filename);

int main(int argc, char** argv)
{
   
  if(argc!=2) 
  {
   
    std::cerr << "Error: expected one and only one argument.\n";
    return -1;
  }

  int n = 300;  // size of the image
  int m = n*n;  // number of unknowns (=number of pixels)

  // Assembly:
  std::vector<T> coefficients;            // list of non-zeros coefficients
  Eigen::VectorXd b(m);                   // the right hand side-vector resulting from the constraints
  buildProblem(coefficients, b, n);

  SpMat A(m,m);
  A.setFromTriplets(coefficients.begin(), coefficients.end());

  // Solving:
  Eigen::SimplicialCholesky<SpMat> chol(A); // performs a Cholesky factorization of A
  Eigen::VectorXd x = chol.solve(b);        // use the factorization to solve for the given right hand side

  // Export the result to a file:
  saveAsBitmap(x, n, argv[1]);

  return 0;
}

在此示例中，首先定义 double SparseMatrix<double> 的列优先稀疏矩阵类型，以及相同标量类型 Triplet<double> 的三元组列表。三元组是将非零条目表示为三元组的简单对象：行索引、列索引、值。

在 main 函数中，我们声明了一个三元组系数列表（作为标准矢量）和由 buildProblem 函数填充的右侧矢量 b。然后将非零系数的原始和平面列表转换为真正的 SparseMatrix 对象 A。请注意，列表的元素不必排序，可能的重复系数将被合并。

最后一步是有效地解决组装的问题。由于生成的矩阵 A 在结构上是对称的，可以通过 SimplicialLDLT 类执行直接的 Cholesky 分解，该类的行为类似于密集对象的 LDLT 对应操作。

生成的向量 x 包含作为一维数组的像素值，该数组保存到如下图所示的 jpeg 文件中。

buildProblem 和 saveAsBitmap 函数超出了本教程的范围。出于好奇和可重复性的目的，可在这里下载。

SparseMatrix 类

矩阵和向量属性

SparseMatrix 和 SparseVector 类采用三个模板参数：标准类型（例如 double） 存储顺序（ColMajor 或 RowMajor，默认为 ColMajor） 内部索引类型（默认为 int）。

对于稠密矩阵对象，构造函数需要传入对象的大小。这里有些例子：

// declares a 1000x2000 column-major compressed sparse matrix of complex<float>
SparseMatrix<std::complex<float> > mat(1000,2000);   
// declares a 1000x2000 row-major compressed sparse matrix of double
SparseMatrix<double,RowMajor> mat(1000,2000);  
// declares a column sparse vector of complex<float> of size 1000
SparseVector<std::complex<float> > vec(1000);   
// declares a row sparse vector of double of size 1000
SparseVector<double,RowMajor> vec(1000);

在本教程的其余部分，mat 和 vec分别表示任何稀疏矩阵和稀疏向量对象。

可以使用以下函数查询矩阵的维度：

// 标准维度
mat.rows()
mat.cols()
vec.size()
// 内部/外部尺寸维度
mat.innerSize()
mat.outerSize()
// 非零系数
mat.nonZeros() 
vec.nonZeros()

迭代非零系数

稀疏对象的元素可以通过coeffRef(i, j)函数进行随机访问。然而，这个函数涉及到一个相当消耗资源的二分搜索。在大多数情况下，我们只想迭代非零元素。这可以通过标准循环遍历外部维度来实现，然后使用InnerIterator 迭代内部向量的非零元素。因此，非零系数必须按照存储顺序进行访问。以下是一个示例：

SparseMatrix<double> mat(rows,cols);
for (int k=0; k<mat.outerSize(); ++k)
{
   
    for (SparseMatrix<double>::InnerIterator it(mat,k); it; ++it)
    {
   
        it.value();
        it.row();   // row index
        it.col();   // col index (here it is equal to k)
        it.index(); // inner index, here it is equal to it.row()
    }
}

SparseVector<double> vec(size);
for (SparseVector<double>::InnerIterator it(vec); it; ++it)
{
   
      it.value(); // == vec[ it.index() ]
      it.index();
}

对于可写表达式，可以使用 valueRef() 函数修改引用值。如果稀疏矩阵或向量的类型依赖于模板参数，则需要typename关键字来表明InnerIterator表示一个类型；更多详细信息参见 The template and typename keywords in C++

填充稀疏矩阵

由于 SparseMatrix 的特殊存储方案，在添加新的非零系数时必须特别小心。例如，向稀疏矩阵中随机插入一个元素的成本是O(nnz)，其中nnz是当前非零系数的数量。

因此，创建稀疏矩阵并保证良好性能的最简单方法是首先构建所谓的三元组列表，然后将其转换为SparseMatrix。

这是一个典型的用法示例：

typedef Eigen::Triplet<double> T;
std::vector<T> tripletList;
tripletList.reserve(estimation_of_entries);
for(...)
{
   
  // ...
  tripletList.push_back(T(i,j,v_ij));
}
SparseMatrixType mat(rows,cols);
mat.setFromTriplets(tripletList.begin(), tripletList.end());
// mat is ready to go!

std::vector中的三元组元素可能以任意顺序存储，并且可能包含重复元素，这些元素将被setFromTriplets()函数进行求和处理。有关更多详细信息，请参阅SparseMatrix :: setFromTriplets()函数和类Triplet。

然而，在某些情况下，可以通过直接将非零元素插入目标矩阵来实现稍高的性能和较低的内存消耗。这种方法的典型场景如下所示：

SparseMatrix<double> mat(rows,cols);       // default is column major
mat.reserve(VectorXi::Constant(cols,6));
for each i,j such that v_ij != 0
  mat.insert(i,j) = v_ij;                  // alternative: mat.coeffRef(i,j) += v_ij;
mat.makeCompressed();                      // optional

• 这里的关键是第2行，我们为每列预留了6个非零项的空间。在许多情况下，每列或每行的非零元素数量可以很容易地预先知道。如果每个内部向量的非零元素数量差异很大，则可以通过提供具有operator[](int j)方法（返回第 j 个内部向量的保留大小）的向量对象（例如通过VectorXi或std::vector<int>实现）来为每个内部向量指定保留大小。如果只能得到每个内部向量的非零元素数量的粗略估计，则强烈建议将其高估而不是低估。如果省略此行，则将为新元素的第一次插入每个内部向量保留2个元素的空间。

• 第4行执行了一个排序插入。在这个例子中，理想情况是第 j 列不是满的，并且包含内部索引比 i 小的非零元素。在这种情况下，此操作可以简化为 O(1) 操作。

• 调用insert(i,j)时，元素i，j不能已经存在，否则使用coeffRef(i,j)方法，这将允许累加值，例如，此方法首先执行二分搜索，如果元素不存在，则最终调用insert(i,j)。它比insert()更灵活，但代价更高。

• 第5行代码抑制了剩余的空白空间，并将矩阵转换为压缩列存储格式。

支持的运算符和函数

由于稀疏矩阵具有特殊的存储格式，它们不能像稠密矩阵那样提供同样级别的灵活性。在Eigen的稀疏模块中，我们选择仅暴露可以有效实现的稠密矩阵API子集。在下面的描述中，sm表示稀疏矩阵，sv表示稀疏向量，dm表示稠密矩阵，dv表示稠密向量。

基本操作

稀疏表达式支持大多数一元和二元系数运算：

sm1.real()   sm1.imag()   -sm1                    0.5*sm1
sm1+sm2      sm1-sm2      sm1.cwiseProduct(sm2)

然而，一个强制性的限制是存储顺序必须匹配。例如，在下面的例子中：

sm4 = sm1 + sm2 + sm3;

sm1、sm2和sm3必须全是行优先或者全是列优先。另一方面，目标矩阵sm4没有限制。例如，这意味着对于 $A^T+A$，矩阵 $A^T$ 必须被计算成一个具有兼容存储顺序的临时矩阵：

parseMatrix<double> A, B;
B = SparseMatrix<double>(A.transpose()) + A;

二项式系数的操作符也可以混合稀疏和稠密表达式：

m2 = sm1.cwiseProduct(dm1);
dm2 = sm1 + dm1;
dm2 = dm1 - sm1;

就性能而言，对于稀疏和稠密矩阵的加减操作最好分成两步进行。例如，不要直接执行 dm2 = sm1 + dm1，而应该先执行以下操作：

dm2 = dm1;
dm2 += sm1;

这种方式的优点是充分利用稠密存储的更高性能（没有间接寻址、SIMD等），而只在稀疏矩阵的少数非零元素上花费低效的稀疏计算成本。

稀疏表达式也支持转置：

sm1 = sm2.transpose();
sm1 = sm2.adjoint();

但是，没有transposeInPlace()方法。

矩阵乘积

Eigen支持多种不同类型的稀疏矩阵乘积，如下所述：

• 稀疏和稠密矩阵相乘

dv2 = sm1 * dv1;
dm2 = dm1 * sm1.adjoint();
dm2 = 2. * sm1 * dm1;

• 对称的稀疏和稠密矩阵相乘

​ 使用selfadjointView()指定对称性，可以优化稀疏对称矩阵与密集矩阵（或向量）的乘积。

dm2 = sm1.selfadjointView<>() * dm1;        // if all coefficients of sm1 are stored
dm2 = sm1.selfadjointView<Upper>() * dm1;   // if only the upper part of sm1 is stored
dm2 = sm1.selfadjointView<Lower>() * dm1;   // if only the lower part of sm1 is stored

• 稀疏和稀疏矩阵相乘

​ 对于稀疏矩阵的乘积，有两种不同的算法可用。默认算法是保守的，并保留可能出现的显式零值。

sm3 = sm1 * sm2;
sm3 = 4 * sm1.adjoint() * sm2;

​ 第二种算法可以即时裁剪显式零值或小于给定阈值的值。它通过 prune() 函数启用和控制。

sm3 = (sm1 * sm2).pruned();              // removes numerical zeros
sm3 = (sm1 * sm2).pruned(ref);           // removes elements much smaller than ref
sm3 = (sm1 * sm2).pruned(ref,epsilon);   // removes elements smaller than ref*epsilon

• 排列

​ 最后，排列操作也可以应用于稀疏矩阵。

PermutationMatrix<Dynamic,Dynamic> P = ...;
sm2 = P * sm1;
sm2 = sm1 * P.inverse();
sm2 = sm1.transpose() * P;

块操作

关于读取访问权限，稀疏矩阵与密集矩阵相同，公开了用于访问子矩阵（如块、列和行）的API。有关详细介绍，请参见块操作。但是，出于性能考虑，向子稀疏矩阵的写入要受到更多限制，目前仅限于连续的列（或行）集，这些列（或行）是列主（或行主）稀疏矩阵可写的。此外，这些信息必须在编译时知道，不能使用诸如block(...)和corner*(...)之类的方法。下面总结了向SparseMatrix写入访问权限的可用API：

SparseMatrix<double,ColMajor> sm1;
sm1.col(j) = ...;
sm1.leftCols(ncols) = ...;
sm1.middleCols(j,ncols) = ...;
sm1.rightCols(ncols) = ...;

SparseMatrix<double,RowMajor> sm2;
sm2.row(i) = ...;
sm2.topRows(nrows) = ...;
sm2.middleRows(i,nrows) = ...;
sm2.bottomRows(nrows) = ...;

此外，稀疏矩阵提供了SparseMatrixBase::innerVector()和SparseMatrixBase::innerVectors()方法，它们是针对列优先存储的col/middleCols方法和针对行优先存储的row/middleRows方法的别名。

三角形视图和自共轭视图

与密集矩阵一样，triangularView()函数可用于处理矩阵的三角部分，并对具有密集右侧的矩阵进行三角求解：

dm2 = sm1.triangularView<Lower>(dm1);
dv2 = sm1.transpose().triangularView<Upper>(dv1);

selfadjointView()函数允许进行各种操作。

• 优化稀疏-稠密矩阵乘积

dm2 = sm1.selfadjointView<>() * dm1;        // if all coefficients of sm1 are stored
dm2 = sm1.selfadjointView<Upper>() * dm1;   // if only the upper part of sm1 is stored
dm2 = sm1.selfadjointView<Lower>() * dm1;   // if only the lower part of sm1 is stored

• 复制三角形部分

// makes a full selfadjoint matrix from the upper triangular part
sm2 = sm1.selfadjointView<Upper>();  
// copies the upper triangular part to the lower triangular part
sm2.selfadjointView<Lower>() = sm1.selfadjointView<Upper>();

• 对称排列的应用

PermutationMatrix<Dynamic,Dynamic> P = ...;
// compute P S P' from the upper triangular part of A, and make it a full matrix
sm2 = A.selfadjointView<Upper>().twistedBy(P);     
// compute P S P' from the lower triangular part of A, and then only compute the lower part
sm2.selfadjointView<Lower>() = A.selfadjointView<Lower>().twistedBy(P);