对于 Eigen SparseMatrix，innerIndexPtr() 和 outerIndexPtr() 到底代表什么？

Question

我正在使用 Eigen::SparseMatrix，但我无法理解 innerIndexPtr 和 outerIndexPtr 的含义。 the official page 的解释对我来说非常模糊。直觉上，我认为 innerIndexPtr 是非零元素的行索引， outerIndexPtr 是非零元素的列索引，但显然事实并非如此。请看下面的例子，

std::vector<Eigen::Triplet<double>> triplet;

triplet.emplace_back(0, 0, 10);
triplet.emplace_back(2, 0, 11);

Eigen::SparseMatrix<double> A(3, 3);

A.setFromTriplets(triplet.begin(), triplet.end());

std::cout << A.innerIndexPtr()[0] << std::endl; // prints 0
std::cout << A.innerIndexPtr()[1] << std::endl; // prints 2
std::cout << std::endl;
std::cout << A.outerIndexPtr()[0] << std::endl; // prints 0
std::cout << A.outerIndexPtr()[1] << std::endl; // prints 2, but I thought it should print 0
std::cout << std::endl;
std::cout << A.valuePtr()[0] << std::endl; // prints 10
std::cout << A.valuePtr()[1] << std::endl; // prints 11

谁能给我解释一下 innerIndexPtr 和 outerIndexPtr 到底代表什么？

Answer 1

你的矩阵看起来像这样：

    (0) (1) (2)
(0)  10   0   0
(1)   0   0   0
(2)  11   0   0

在内部，稀疏由四个紧凑数组组成：

Values: stores the coefficient values of the non-zeros.

InnerIndices: stores the row (resp. column) indices of the non-zeros.

OuterStarts: stores for each column (resp. row) the index of the first non-zero in the previous two arrays.

InnerNNZs: stores the number of non-zeros of each column (resp. row). The word inner refers to an inner vector that is a column for a column-major matrix, or a row for a row-major matrix. The word outer refers to the other direction.

（参见 Sparse matrix manipulations）

您的矩阵存储为：

      Values: 10 11
InnerIndices:  0  2

 OuterStarts:  0  2  2
   InnerNNZs:  2  0  0

引用说明书：

Low-level API

sm1.valuePtr();      // Pointer to the values
sm1.innerIndexPtr(); // Pointer to the indices.
sm1.outerIndexPtr(); // Pointer to the beginning of each inner vector

因此，valuePtr() returns [10, 11], innerIndexPtr() returns [0, 2], outerIndexPtr() returns [0, 2, 2]。这应该可以解释您观察到的结果。

关于OuterStarts数组的一些解释：编号为1和2的列由零组成。这不会影响外部索引。编号为 1 的列从位置 2 开始并在位置 2 结束。编号为 2 的列也从位置 2 开始并在位置 2 结束。它们完全由零组成的事实仅意味着它们的大小为零。我同意手册中对 OuterStarts 的解释有点误导。将 "the fist non-zero" 视为尾后元素。

Answer 2

Eigen 使用 CSC（压缩稀疏列）格式（另请参阅 https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)）。

outerIndexPtr()[i] 表示从第 i 列开始的其他数组的索引。它在下一列开始的 outerIndexPtr()[i+1] 处结束。如果这两个索引彼此相等，则该列为空。

innerIndexPtr() 是元素行索引的数组， valuePtr() 是对应值的数组。

因此，为了说明这一点，此代码遍历第 i 列

int k_start = A.outerIndexPtr()[i];
int k_end   = A.outerIndexPtr()[i+1];

for (k = k_start; k < k_end; k++) {
    int j = A.innerIndexPtr()[k];
    double v = A.valuePtr()[k];
    // v is value of the element at position (j,i)
}

以上都是针对列优先存储，这是Eigen中的默认设置。对于行优先，交换上面描述中的行 <-> 列。

对于 Eigen SparseMatrix，innerIndexPtr() 和 outerIndexPtr() 到底代表什么？

For Eigen SparseMatrix, what does innerIndexPtr() and outerIndexPtr() exactly represent?

c++

eigen

eigen3