我尝试实现稀疏矩阵
存储格式。维基百科说:this
我需要CRS
算法。但是我无法理解算法到底。我有链接示例中的矩阵
0 0 0 0
5 8 0 0
0 0 3 0
0 6 0 0
和3个数组
A = [ 5 8 3 6 ]
IA = [ 0 0 2 3 4 ]
JA = [ 0 1 2 1 ]
好的,我明白了,什么 A - 所有元素都不为零 JA - 行中第一个非零元素的列索引 但是 IA 的逻辑是什么???
最佳答案
AI[]
vector 存储开始一行的位置。
例如 i
行的所有非零元素将它们的值存储在 A[k]
中及其相关的 j 指数在 AJ[k]
中其中 k
是这样的
AI[i] <= k <= AI[i+1]-1
要掌握的中心思想包含在接下来的两行中:
AI[i]
: 是在 row i
开头跳转的偏移量
AI[i+1]-1
: 是在 row i+1
开头跳转的偏移量, 但是 当我们删除 1 时,它成为 row i
的最后一个元素
为了说明这一点,我们可以在两种情况下计算矩阵向量乘积 y=A.x:密集格式和 CRS 格式(伪代码):
当 A 是稠密的时,我们有:
for (i = 0; i < N; i++) // row i
{
y[i] = 0;
for (j = 0; j < N; j++) // column j
y[i] += A[i][j] * x[j];
}
与使用 CRS 格式存储 A 的情况进行比较:
for (i = 0; i < N; i++) // row i
{
y[i]=0;
for (k = AI[i]; k < AI[i+1]; k++) // nonzero element of row i
{
y[i] += A[k] * x[AJ[k]];
}
}
关于algorithm - IA 阵列的稀疏矩阵 CRS 逻辑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47100492/