作者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/m.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