[問題] 降低 QR 分解的演算複雜度

[j0958322080 (Tidus)]

之前在解最小平方法寫了 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)
→ yeebon: chx64的1/2悖論真的很經典呢
！！！！！！！！！！！！！！簽名檔破555000點擊率啦！！！！！！！！！！！！！！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.74.14
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1522865204.A.4CE.html
推 DJWS: 剛剛找了一些資料  真的都沒講到 Q = H1...Hn 應該怎麼乘
→ DJWS: http://www.seas.ucla.edu/~vandenbe/133A/lectures/qr.pdf
→ DJWS: 最後一頁上半部有講怎麼乘
→ j0958322080: 我是已經這樣算了，但這樣複雜度還是O(m*m*n*n)
→ j0958322080: QR分解裡面的迴圈都是從 k 開始不是從 1 開始
→ s89162504: 平行?
推 FRAXIS: 在 DJWS 提供的資料的 6-31 頁第一個公式？
→ j0958322080: 好像沒辦法這樣算耶，要先把 H 算出來才可以乘 A
推 DJWS: QR分解裡面的迴圈確實是從k開始   算Q的時候卻不是從k開始
→ j0958322080: Q其實也可以從 k 開始，因為拆成方塊矩陣後左上角的
→ j0958322080: 是單位矩陣，所以只需要乘右下角的矩陣，但這樣複雜
→ j0958322080: 度還是m*m*n*n
推 DJWS: 然後如同FRAXIS所說的  公式裡的點積  看起來必須預先計算
→ DJWS: vk^T  dot  x_k:m  應該要預先計算
→ DJWS: 修正  vk  dot  x_k:m  應該要預先計算
→ j0958322080: 這樣感覺有點像是用空間換時間??
推 DJWS: 對