[問題] 降低 QR 分解的演算複雜度 j0958322080 PTT批踢踢實業坊

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

作者: j0958322080 (Tidus) 2018-04-05 02:06:40

之前在解最小平方法寫了 QR 分解，(A 為 m by n 的矩陣)
雖然寫得出來，可是演算複雜度高達 O(m*m*n*n)，
看書上是寫演算複雜度是 O(m*n*n)，
主要是因為要一直重複矩陣乘法，所以沒辦法很快。
code 如下
http://codepad.org/DsAtdHDK
感謝各位

作者: yeebon 2018-07-22 16:41:00

chx64的1/2悖論真的很經典呢

作者: DJWS (...) 2018-04-05 07:05:00

剛剛找了一些資料真的都沒講到 Q = H1...Hn 應該怎麼乘http://www.seas.ucla.edu/~vandenbe/133A/lectures/qr.pdf最後一頁上半部有講怎麼乘

作者: j0958322080 (Tidus) 2018-04-05 09:18:00

我是已經這樣算了，但這樣複雜度還是O(m*m*n*n)QR分解裡面的迴圈都是從 k 開始不是從 1 開始

作者: s89162504 (阿本) 2018-04-05 09:44:00

平行?

作者: FRAXIS (喔喔) 2018-04-05 10:28:00

在 DJWS 提供的資料的 6-31 頁第一個公式？

作者: j0958322080 (Tidus) 2018-04-05 14:04:00

好像沒辦法這樣算耶，要先把 H 算出來才可以乘 A

作者: DJWS (...) 2018-04-05 20:19:00

QR分解裡面的迴圈確實是從k開始算Q的時候卻不是從k開始

作者: j0958322080 (Tidus) 2018-04-05 20:26:00

Q其實也可以從 k 開始，因為拆成方塊矩陣後左上角的是單位矩陣，所以只需要乘右下角的矩陣，但這樣複雜度還是m*m*n*n

作者: DJWS (...) 2018-04-05 20:36:00

然後如同FRAXIS所說的公式裡的點積看起來必須預先計算vk^T dot x_k:m 應該要預先計算修正 vk dot x_k:m 應該要預先計算

作者: j0958322080 (Tidus) 2018-04-09 21:14:00

這樣感覺有點像是用空間換時間??

作者: DJWS (...) 2018-04-10 05:25:00

對

繼續閱讀

[請益] 四元樹找鄰WoodChen [問題] 變形的浮點數逆運算(PMbus)chrisdar [問題] codility StoneWallken1325 [問題] uva 1209 wordfishkeke0421 Re: [問題] 一題greedy (codeforces #451 pD)outofyou Re: [問題] 一題greedy (codeforces #451 pD)ckc1ark [問題] 一題greedy (codeforces #451 pD)GYLin [問題] 單做數值計算有需要再學資料結構嗎？j0958322080 [問題] tree isomorphism 時間複雜度分析powertodream Re: [問題] 解最小平方法的問題 Ax~bj0958322080