稀疏矩阵时间计算

Question

如果我将一个稠密矩阵存储为一个坐标明智的稀疏矩阵而不是n×n二维数组，那么时间效率是多少？如果我将它作为稀疏矩阵存储，显然这将是不好的。

Answer 1

您应该考虑您感兴趣的操作，因为各种操作的效率因存储格式不同而不同。请参阅Scipy Sparse中的各种格式（和典型用例）。

通常情况下，'稀疏矩阵'被定义为一个矩阵，您可以通过利用许多元素为零的事实获得一些性能优势。因此，以稀疏格式存储稀疏矩阵应该有优势。

坐标格式（COO）的空间需求为3 * nnzs。所以只要3 * nnzs < N^2（您的矩阵顺序）可以节省存储空间。其他格式（如CSR）在空间方面效率更高（2 * nnzs + N），并且还有效地支持常用操作（例如稀疏矩阵向量乘法）。