10

我知道两个完整矩阵相乘的下限是 Ω(n^2)。矩阵乘法

我一直在尝试使用问题变换方法证明两个下三角矩阵相乘的下界。

我最初的想法是（1）变换下三角矩阵，（2）估计这种变换的时间复杂度。

T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))>Ω(full_matrix_multiplication(n)) = Ω(n^2)

现在，我只需要证明O(lower_triangular_matrix_transformation(n))并且我需要使三角矩阵成为一个完整的矩阵，所以为了简单起见，我只是让这个三角矩阵乘以它自身的一个变体，比如转置。

原因是下三角矩阵的平方仍然是下三角矩阵，而下三角矩阵乘以它的转置变化是一个“满矩阵”。

所以我只需要分析一个三角矩阵乘以它的转置变化的复杂度。

谁能指出我的想法是否“合理”？

4

2 回答 2

3

我不相信通过构建算法足以证明下限，因为仍然不能排除存在复杂度较低的不同算法。

很明显，下限不会高于 O(n^2)，因为一般乘法总是适用于 lower_triangle_matrices (ltm)。

现在，由于任意矩阵到一个或多个 ltm 的任何转换本身都是 O(n^2) 复杂度的操作，因此我们可能不会推断出任何此类算法都不存在。

您的推理大纲似乎表明增加复杂性遵循“正常”算术规则。不是这种情况！
由此产生的复杂性总是（至少）是算法部分复杂性的最大值。

所以你的推理似乎不合理。

您可以尝试以下方法之一：


  1. 当目标为 O(ltm) < O(n^2) 时，构造一个复杂度较低的算法（证明存在）
  2. 找到一个复杂度 < O(n^2) 并产生 ltm 的变换。那么任何具有较低复杂度的 ltm 乘法算法都将为具有复杂性的任意矩阵提供算法这将与您的初始命题相矛盾。
    然而，这需要足够低复杂度的转换。如果这不知道。该参数不可用。

在我看来，T()+O() > O(n^2) 的步骤似乎没有很好的基础。从此，只需证明 (O(ltm)) 的结论就被打破了。

于 2016-03-21T13:37:08.673 回答
2

我在想解决方案可能是将 A 转换为 A+A'。转置和加号操作的复杂度都是 O(n^2)。所以，O(lower_triangular_matrix_transformation(n))=n^2。因为 A A 和 (A+A') (A+A') 的下界也是 Ω(n^2)，所以 T(lower_triangular_matrix_multiplication(n))>Ω(full_matrix_multiplication(n))-O( lower_triangular_matrix_transformation(n))，表示三角矩阵的下界与全矩阵的下界相同。

量子点

于 2016-03-15T08:10:55.713 回答