algorithm - F_2 上的矩阵乘法算法仅需 O(n^2.81/(log n)^0.4)。创建算法。但是怎么做？

Question

我们有一个矩阵，其元素在整数模 2 (F_2) 的字段中。我们正在寻找将 nxn 矩阵乘以 F_2 的算法O(n^2.81/(log n)^0.4)

怎么可能？

我知道，Strassen 的算法给出了O(n^2.81)，但是我们怎么能得到这个因子(log n)^0.4呢？

Answer 1

您可以执行以下操作：

取每个可能的矩阵，其维度为。有这样的矩阵（）。

预先计算这些矩阵的乘法结果。这为您提供了带有尺寸的表格。然后在 Strassen 算法的递归阶段，如果所需的乘法矩阵足够小，您可以在此表中使用预先计算的值（如果小于您可以用零填充适当的行和列）。让. 所以你有以下递归：

注意，递归深度是，所以你有：

使用几何级数公式：