作者j0958322080 (Tidus)
看板Prob_Solve
标题[问题] 降低 QR 分解的演算复杂度
时间Thu Apr 5 02:06:40 2018
之前在解最小平方法写了 QR 分解，(A 为 m by n 的矩阵)
虽然写得出来，可是演算复杂度高达 O(m*m*n*n)，
看书上是写演算复杂度是 O(m*n*n)，
主要是因为要一直重复矩阵乘法，所以没办法很快。
code 如下
http://codepad.org/DsAtdHDK
感谢各位
--
！！！！！！！！！！！！！签名档破555000点击率啦！！！！！！！！！！！！！！！
Fw: [问卦] 电影：决胜21点的机率问题
https://goo.gl/2BpbB7 #1MfN3FgZ (joke)
1F：→ yeebon: chx64的1/2悖论真的很经典呢07/22 16:41
！！！！！！！！！！！！！！签名档破555000点击率啦！！！！！！！！！！！！！！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.74.14
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1522865204.A.4CE.html
2F：推 DJWS: 刚刚找了一些资料 真的都没讲到 Q = H1...Hn 应该怎麽乘 04/05 07:05
4F：→ DJWS: 最後一页上半部有讲怎麽乘 04/05 07:21
5F：→ j0958322080: 我是已经这样算了，但这样复杂度还是O(m*m*n*n) 04/05 09:18
6F：→ j0958322080: QR分解里面的回圈都是从 k 开始不是从 1 开始 04/05 09:20
7F：→ s89162504: 平行? 04/05 09:44
8F：推 FRAXIS: 在 DJWS 提供的资料的 6-31 页第一个公式？ 04/05 10:28
9F：→ j0958322080: 好像没办法这样算耶，要先把 H 算出来才可以乘 A 04/05 14:04
10F：推 DJWS: QR分解里面的回圈确实是从k开始 算Q的时候却不是从k开始 04/05 20:19
11F：→ j0958322080: Q其实也可以从 k 开始，因为拆成方块矩阵後左上角的 04/05 20:26
12F：→ j0958322080: 是单位矩阵，所以只需要乘右下角的矩阵，但这样复杂 04/05 20:26
13F：→ j0958322080: 度还是m*m*n*n 04/05 20:26
14F：推 DJWS: 然後如同FRAXIS所说的 公式里的点积 看起来必须预先计算 04/05 20:36
15F：→ DJWS: vk^T dot x_k:m 应该要预先计算 04/05 20:38
16F：→ DJWS: 修正 vk dot x_k:m 应该要预先计算 04/05 20:38
17F：→ j0958322080: 这样感觉有点像是用空间换时间?? 04/09 21:14
18F：推 DJWS: 对 04/10 05:25