稀疏矩阵
科学上有句谚语:归根结底,一切都归结为矩阵乘法。不管你是在物理或工程中解偏微分方程,还是在用经典模型或深度神经网络进行机器学习,最后,在数值上,都是矩阵和向量的相乘,按一定顺序重复。
这些矩阵通常非常大,比如1000000 x 1000000。在这种情况下,如果矩阵没有特定的结构,那么你就必须在内存中存储大量的值,而且运算也非常耗时。这叫做稠密矩阵。然而,在许多科学应用中,矩阵确实有一定的结构。
通常,矩阵的大部分值都是零,这样的矩阵就叫做稀疏矩阵。例如,如果1000000 x 1000000矩阵是对角线的,那么只需要存储10^6个值而不是10^12个值。如果用10^6个维向量乘以它,只需要做10^6次乘法而不是10^12次乘法和加法。
差别是巨大的!即使矩阵不是对角的,只要大多数值是零,内存和速度优势是巨大的,因为只需保存相对较少的非零值,而与向量的乘法只需要考虑那些非零值。
如何使用稀疏矩阵
Python的SciPy包有一个专门用于稀疏矩阵实现的子包。根据你的稀疏矩阵的结构和你想用稀疏矩阵做什么,包中有针对给定任务优化的不同表示。只要使用任何稀疏矩阵类,通常可以获得99%的速度和内存优势。
首先,考虑一个大的密集矩阵。我们用随机值填充它,都在-0.5和0.5之间:
然后使用numpy的matmul函数将⋅相乘
这在我的电脑上需要7.07秒。现在让我们以同样的方式使用一个对角矩阵,并将其存储为一个普通矩阵:
这在我的电脑上花了7秒,几乎是同一时间,尽管我们知道大多数乘法肯定是零。现在我们用同样的方法来处理稀疏矩阵。因为这里的矩阵是对角线的,我们可以使用scipy.sparse.diag:
如果你输出A_sparse,它会说:
所以它实际上是一个10000x10000的矩阵,但是稀疏并且以一种特殊的对角线格式存储。我们再做一次同样的乘法:
这在我的电脑上只花了0.003秒,比使用密集矩阵快了2000多倍。