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

Question

I am working with Eigen::SparseMatrix and I am having trouble understanding the meaning of innerIndexPtr and outerIndexPtr. The explanation at the official page is very vague to me. Intuitively, I thought innerIndexPtr is the row indices for non zero elements and outerIndexPtr is the column indices for the non zero elements but apparently that's not the case. Please see below example,

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

Can someone explain to me what innerIndexPtr and outerIndexPtr exactly represents?

Answer 1

You matrix looks like this:

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

Internally, a sparse consists of four compact arrays:

• 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.

(See Sparse matrix manipulations)

Your matrix is stored as:

      Values: 10 11
InnerIndices:  0  2

 OuterStarts:  0  2  2
   InnerNNZs:  2  0  0

To quote the manual:

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

Therefore, valuePtr() returns [10, 11], innerIndexPtr() returns [0, 2], and outerIndexPtr() returns [0, 2, 2]. This should explain the result you observe.

---

Some explanation on the OuterStarts array: the columns numbered 1 and 2 consist of zeros. This doesn't affect the outer index. The column numbered 1 starts at position 2 and ends at position 2. The column numbered 2 also starts at position 2 and ends at position 2. The fact that they consist entirely of zeros just means they are zero-sized. I agree that the explanation for OuterStarts in the manual is a bit misleading. Think of "the fist non-zero" as the past-the-end element.

Answer 2

Eigen uses CSC (compressed sparse column) format (see also https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)).

outerIndexPtr()[i] indicates the index into other arrays where i-th column starts. It ends at outerIndexPtr()[i+1], where the next column begins. If these thwo indices are equal to each other, the column is empty.

innerIndexPtr() is an array of row indices of elements, and valuePtr() is an array of corresponding values.

So, to illustrate it, this code iterates through i-th column

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)
}

---

All above is for column-major storage, which is default in Eigen. For row-major, exchange row <-> column in the description above.