matrix-multiplication - 两个下三角矩阵相乘的复杂度

Question

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

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

我最初的想法是(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))我需要使三角矩阵成为一个完整的矩阵，所以为了简单起见，我只是让这个三角矩阵乘以它自己的一个变体，比如转置。

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

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

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

Answer 1

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

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

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

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

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

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

构建一个复杂度较低的算法(证明存在)
当目标是 O(ltm) < O(n^2)

找到一个复杂度 < O(n^2) 并且产生的变换
长然后任何具有较低复杂度的 ltm 乘法算法
将为具有复杂性的任意矩阵提供算法
这将与您最初的提议相矛盾。
然而，这需要足够低复杂度的转换。
如果这是不知道的。论据是不可用的。

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