知识卡片

普通读书笔记卡 · 3602.a.1.a

斯特拉森重组七个乘积

理解等级:中级

Strassen 先以 10 个子矩阵和差构造中间量,再计算 7 个乘积,最后用 12 次加减将其组合进四个输出块。

展开每个乘积并消去交叉项,可验证四块恰等于普通矩阵乘积;右侧展开式只是正确性证明,不是实际执行的额外乘法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第4章 分治策略 · 查看原书依据

      The only multiplications that the algorithm performs are those in the middle column of these equations. The right-hand column just shows what these products equal in terms of the original submatrices created in step 1, but the terms are never explicitly calculated by the algorithm.

    参考来源

    - 位置:《算法导论(第4版)》第 4 章 4.2 节(`OEBPS/chapter004.xhtml`,文本字符 [25000, 30000))。 - 结论依据:原文列出 S₁–S₁₀、P₁–P₇ 的构造和四个 C 子块的更新式,并逐块对应普通乘法公式。 - 原始内容:The only multiplications that the algorithm performs are those in the middle column of these equations. The right-hand column just shows what these products equal in terms of the original submatrices created in step 1, but the terms are never explicitly calculated by the algorithm.