知识卡片
矩阵乘法可归约为块矩阵求逆
构造含A、B的3n阶上三角块矩阵,其逆矩阵右上块给出AB。
若求逆复杂度I(n)至少平方级且满足I(3n)=O(I(n)),则乘法可在O(I(n))时间完成;这是复杂度归约,并非日常乘法建议。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 .