对矩形矩阵的分而治之
Divide and conquer on rectangular matrices
对于这个问题的含糊不清，我深表歉意，但我正在尝试确定一种方法来执行矩形矩阵 A 和 B 的分而治之乘法，使得 A = n x m 和 B = m x p
我读了一些书，Strassen 的方法似乎很有前途，但我无法确定如何在矩形矩阵上使用该算法。我看到有些人提到 "padding" 用零使两个矩阵都平方然后 "unpadding" 结果，但我不清楚去填充阶段需要什么。
感谢您的指教！
结果矩阵将在 "added" 操作数矩阵的所有项目上包含零。要返回矩形结果，您只需裁剪结果，即根据操作数的维度取结果矩阵的左上角。
然而，仅在 n、m 和 p 非常接近的情况下，填充本身似乎才是明智的。当这些不成比例时，您将进行大量的零矩阵乘法运算。
例如，如果 n = 2m = p，Strassen 算法会将乘法分成 m 大小矩阵的 7 次乘法。但是，其中 4 次乘法将涉及零矩阵，因此没有必要。
我认为有两种方法可以提高性能：
- 使用填充并记住填充矩阵的哪一部分。然后对于每个乘法步骤，检查您是否没有乘以零矩阵。如果这样做，结果也将是一个零矩阵，无需计算它。这将消除与填充相关的大部分成本。
- 不使用填充。 NonSquare_Strassen：将矩形矩阵划分为正方形区域和余数。 运行 方形区域上的香草施特拉森。 运行 NonSquareStrassen 再次讨论余数。然后，合并这些结果。这个算法很可能比第一个算法更快，但并不完全容易实现。但是，其逻辑与 Strassen 的方阵算法非常相似。
为了简单起见，我会选择第一个选项。
注意：
请记住，您也可以将 Strassen 的方法用于矩形矩阵，并且在特定矩阵大小以下，额外矩阵添加的 O(n^2) 成本变得更加重要，最好使用普通三次乘法来完成小尺寸。这意味着 Strassen 的方法对于非方阵仍然很容易实现。以上期望您已经实现了方矩阵的算法。
对于这个问题的含糊不清，我深表歉意，但我正在尝试确定一种方法来执行矩形矩阵 A 和 B 的分而治之乘法，使得 A = n x m 和 B = m x p
我读了一些书，Strassen 的方法似乎很有前途，但我无法确定如何在矩形矩阵上使用该算法。我看到有些人提到 "padding" 用零使两个矩阵都平方然后 "unpadding" 结果，但我不清楚去填充阶段需要什么。
感谢您的指教！
结果矩阵将在 "added" 操作数矩阵的所有项目上包含零。要返回矩形结果，您只需裁剪结果，即根据操作数的维度取结果矩阵的左上角。
然而，仅在 n、m 和 p 非常接近的情况下，填充本身似乎才是明智的。当这些不成比例时，您将进行大量的零矩阵乘法运算。
例如，如果 n = 2m = p，Strassen 算法会将乘法分成 m 大小矩阵的 7 次乘法。但是，其中 4 次乘法将涉及零矩阵，因此没有必要。
我认为有两种方法可以提高性能：
- 使用填充并记住填充矩阵的哪一部分。然后对于每个乘法步骤，检查您是否没有乘以零矩阵。如果这样做，结果也将是一个零矩阵，无需计算它。这将消除与填充相关的大部分成本。
- 不使用填充。 NonSquare_Strassen：将矩形矩阵划分为正方形区域和余数。 运行 方形区域上的香草施特拉森。 运行 NonSquareStrassen 再次讨论余数。然后，合并这些结果。这个算法很可能比第一个算法更快，但并不完全容易实现。但是，其逻辑与 Strassen 的方阵算法非常相似。
为了简单起见，我会选择第一个选项。
注意： 请记住，您也可以将 Strassen 的方法用于矩形矩阵，并且在特定矩阵大小以下，额外矩阵添加的 O(n^2) 成本变得更加重要，最好使用普通三次乘法来完成小尺寸。这意味着 Strassen 的方法对于非方阵仍然很容易实现。以上期望您已经实现了方矩阵的算法。