如果您有一个固定维度的矩阵,则建立可靠答案的最佳方法就是试错法。然而,如果您不知道矩阵/向量的维度,则有以下经验法则:
您的稀疏向量应该具有有效的非零条目数量
对于矩阵来说,这意味着
您的N x N
稀疏矩阵应该具有<= c * N
个非零条目,其中c
是一个“远小于”N
的常数。
让我们为这个规则提供一个伪理论解释。我们将考虑一个相当简单的任务,即使用双值坐标的两个向量的标量(或点)积。现在,如果您有两个相同长度N
的密集向量,则您的代码将如下:
//define vectors vector, wector as double arrays of length N
double sum = 0;
for (int i = 0; i < N; i++)
{
sum += vector[i] * wector[i];
}
这个过程涉及 N
次加法,N
次乘法和 N
次条件分支(循环操作)。最耗费时间的是条件分支,以至于我们可以忽略乘法和加法。为什么它如此昂贵,这个问题在this question的答案中有所解释。
更新:实际上,在 for 循环中,你只有在循环结束时才会决定选择哪个分支,因为按照定义,进入循环的默认分支将会被选择。这导致每个标量积运算最多只会有一次 pipeline 重启。
现在让我们看一下 BLAS 中如何实现稀疏向量。在那里,每个向量由两个数组编码:一个是值,另一个是相应索引,类似于
1.7 -0.8 3.6
171 83 215
(再加上一个整数,表示所述长度N
)。在BLAS文档中指出,索引的排序在此处不起作用,因此数据
-0.8 3.6 1.7
83 215 171
编码相同的向量。这个备注提供了足够的信息来重构标量积算法。给定由数据int[] indices, double[] values
和int[] jndices, double[] walues
编码的两个稀疏向量,将按照以下“代码”中的行计算它们的标量积:
double sum = 0;
for (int i = 0; i < indices.length; i++)
{
for (int j = 0; j < jndices.length; j++)
{
if(indices[i] == jndices[j])
{
sum += values[indices[i]] * walues[jndices[j]];
}
}
}
这给我们提供了一个总数为indices.length * jndices.length * 2 + indices.length
的条件分支。这意味着为了应对密集算法,您的向量最多只能有sqrt(N)
个非零条目。关键在于依赖于N
已经是非线性的,因此没有必要问您需要填充1%、10%还是25%。10%对于长度为10的向量来说是完美的,对于长度为50的向量来说还算可以,但对于长度为100的向量来说就已经彻底毁掉了。
更新:在这段代码片段中,您有一个if
分支,错误路径的概率为50%。因此,两个稀疏向量的标量积将导致大约0.5到1倍(每个稀疏向量的平均非零条目数)的管道重启,具体取决于您的向量有多稀疏。这些数字需要进行调整:在没有else
的if
语句中,将首先执行最短的指令,即"什么也不做",但仍然会执行。
请注意,最有效率的操作是一个稀疏向量和一个密集向量的标量积。给定一个稀疏向量的
indices
和
values
以及一个密集向量
dense
,您的代码将如下所示:
double sum = 0;
for (int i = 0; i < indices.length; i++)
{
sum += values[indices[i]] * dense[indices[i]];
}
例如,您将拥有indices.length
个条件分支,这是很好的。
更新。再次说明,我打赌每个操作最多只会有一个管道重启。请注意,据我所知,在现代多核处理器中,两种替代方案都在两个不同的核心上并行执行,因此在替代分支中,您只需要等待最长的分支完成即可。
现在,当矩阵与向量相乘时,您基本上会取#行标量向量积。矩阵与矩阵相乘意味着取第二个矩阵中的#(非零)列的矩阵乘以向量乘积。欢迎您自己计算复杂度。
这就是所有关于不同矩阵存储的深层理论的黑魔法开始的地方。您可以将稀疏矩阵存储为稠密的稀疏行数组,稀疏的稠密行数组或稀疏的稀疏行数组。列也是一样。问题中引用的Scipy中的所有有趣缩写都与此有关。
如果您用稀疏行构建一个矩阵并与一个密集矩阵或密集列的矩阵相乘,那么您将“始终”具有速度优势。您可能希望将稀疏矩阵数据存储为对角线的密集向量 - 因此在卷积神经网络的情况下 - 然后您将需要完全不同的算法。您可能希望将矩阵转换为块矩阵 - 就像BLAS一样 - 并获得合理的计算提升。您可能希望将数据存储为两个矩阵 - 比如一个对角线和一个稀疏矩阵,这是有限元法的情况。如果您始终将一行存储矩阵乘以列向量,而避免矩阵乘法,则可以利用疏密性进行常规神经网络(例如快速前馈、极限学习机或回声状态网络),但是请避免矩阵乘法。并且,如果您遵循经验法则,始终使用稀疏矩阵,那么您将“始终”获得优势 - 对于有限元和卷积网络有效,但对于储备计算而言则无效。