c++ - 如何从稀疏矩阵中获取右下角的部分？

Question

以“坐标格式”获取稀疏矩阵右下四分之一的最佳方法是什么？我需要它来补充 Schur。

坐标从 1 开始索引(我使用的是 MUMPS)。

示例:

int order_of_matrix = 4

int row_coords[] = {1,1,2,3,3,4};
int col_coords[] = {1,3,3,3,4,4};
int vals[]       = {1,2,3,4,5,6};

所以我的矩阵应该是这样的:

|1 0 2 0|
|0 0 3 0|
|0 0 4 5|
|0 0 0 6|

现在，我需要像这样从右下角获取值:

int schur_complement_size = 1
|6|

int schur_complement_size = 2
|4 5|
|0 6|

int schur_complement_size = 3
|0 3 0|
|0 4 5|
|0 0 6|

int schur_complement_size = 4
|1 0 2 0|
|0 0 3 0|
|0 0 4 5|
|0 0 0 6|

有没有什么优雅的方法可以在不将矩阵转换为密集格式的情况下实现这一点？密集格式对我来说是一个很大的问题，因为在我的程序的实际使用中矩阵会非常大。

Answer 1

假设您无法更改稀疏矩阵的建模方式，您可以试试这个:

• 确保 row_coords 已排序(如您提供的示例所示)。请注意，您也可以选择 col_coords，您需要的是两个数组之一是有序的。
• 计算 q = order_of_matrix - order_of_submatrix + 1
• 在排序后的数组 (row_coords) 中进行二分查找，找出第一个元素 row_coords[i]=q 的索引

• 现在您可以使用 3 个新数组(您知道它们的最大大小)创建子矩阵并仅在 col_coords[i]>=q 时添加一个元素。

  sub_col_coords[j] = col_coords[i] - q + 1;sub_row_coords[j] = col_coords[i] - q + 1;sub_vals[j] = vals[i];