压缩行存储（CRS）中row ptr数组的工作原理及生成方式咨询

Let me break this down with a concrete example—this is exactly the kind of thing that clicks when you map the array values directly to the original sparse matrix. I remember getting stuck on row_ptr too when I first learned CRS, so I feel your pain!

Core Purpose of row_ptr #

First, let's recap: row_ptr is a boundary array that tells you where each row's non-zero elements start and end in the val and col_ind arrays. It has a length of number of rows + 1 (let's call the number of rows n), so it goes from row_ptr[1] to row_ptr[n+1] if we're using 1-based indexing (which is what your reference uses).

Example Breakdown (Matching Your Question) #

Let's assume the example matrix from your article looks like this (aligned with the row_ptr values you mentioned: [1, 3, 6, 7]):

Row 1: [5, 0, 7, 0]          # 2 non-zero elements
Row 2: [0, 3, 2, 4]          # 3 non-zero elements
Row 3: [0, 0, 0, 9]          # 1 non-zero element

Total non-zero elements (nnz) = 2 + 3 + 1 = 6.

Now let's map this to row_ptr:

• row_ptr[1] = 1: The first non-zero element of Row 1 is at position 1 in the val/col_ind arrays (1-based).
• row_ptr[2] = 3: This is the start position for Row 2's non-zero elements. Since Row 1 has 2 non-zero elements, they take up positions 1 and 2 in val/col_ind. So Row 2 has to start at position 3. That's where the second 3 comes from!
• row_ptr[3] = 6: Row 2 has 3 non-zero elements, which take up positions 3, 4, 5. So Row 3's first non-zero element starts at position 6—hence the third 6.
• row_ptr[4] = 7: This is the row_ptr[n+1] value (since n=3, n+1=4).

Why row_ptr[n+1] = nnz + 1? #

This is the "terminator" entry in row_ptr. Think of it this way:

• All nnz non-zero elements occupy positions 1 to nnz (1-based) in val/col_ind.
• row_ptr[n+1] marks the position right after the last non-zero element. For our example, nnz=6, so nnz+1=7—which matches row_ptr[4].
• This makes it easy to calculate the number of non-zero elements in any row: for Row k, it's row_ptr[k+1] - row_ptr[k]. For Row 3, that's 7 - 6 = 1, which is exactly the count of non-zeros we have.
• It also simplifies looping through rows: you can iterate from row_ptr[k] to row_ptr[k+1]-1 to get all elements for Row k, no need for special logic for the last row.

If we used 0-based indexing (more common in code), this rule would translate to row_ptr[n] = nnz—since elements are indexed from 0 to nnz-1, the boundary after the last element is nnz. Your article uses 1-based, hence the nnz + 1 wording.

内容的提问来源于stack exchange，提问作者CCC