对线性方程 Ax=b 当 A 是稀疏数组时直接求解。本质上类似于 LU 分解或者 Cholesky 分解,但是保留了矩阵的稀疏性。这通常需要通过对变量重新排序来实现。
稀疏矩阵一般只存储非零元,存储 Θ(k),计算矩阵向量乘法也只需要 Θ(k)。
图表示
对称矩阵可以用无向图表示,而非对称矩阵可以用有向图表示。本质上说,重新排序就是将这个图切分成几片,它们之间通过比较少的边相连。
图的结构通常和矩阵的来源有关,例如一维、二维和三维的 PDE 离散化之后通常会得到具有一维、二维和三维的图。
维数 | 空间 | 时间 |
---|
1 | O(N) | O(N) |
2 | O(NlogN) | O(N3/2) |
3 | O(N4/3) | O(N2) |
相关内容
参考文献