知识卡片

普通读书笔记卡 · 3683.a.5.a.1

矩阵乘法可归约为块矩阵求逆

理解等级:高级

构造含A、B的3n阶上三角块矩阵,其逆矩阵右上块给出AB。

若求逆复杂度I(n)至少平方级且满足I(3n)=O(I(n)),则乘法可在O(I(n))时间完成;这是复杂度归约,并非日常乘法建议。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第28章 矩阵运算 · 查看原书依据

      To compute their product C = AB, define the 3n × 3n matrix D by The inverse of D is and thus to compute the product AB, just take the upper right n × n submatrix of D−1.

    参考来源

    - 位置:《算法导论(第4版)》第28章《矩阵运算》(OEBPS/chapter028.xhtml,文本字符[20000,30000))。 - 结论依据:定理28.1 的构造及 `OEBPS/images/Art_P933.jpg`、`Art_P934.jpg`:D 为3n阶上三角块矩阵,D⁻¹右上块为 AB;定理前提 I(n)=Ω(n²)、I(3n)=O(I(n)),故 M(n)=O(I(n))。 - 公式图核读:D=[[I,A,0],[0,I,B],[0,0,I]];D⁻¹=[[I,−A,AB],[0,I,−B],[0,0,I]],各块为 n×n。 - 原始内容:To compute their product C = AB , define the 3 n × 3 n matrix D by The inverse of D is and thus to compute the product AB , just take the upper right n × n submatrix of D −1 .