[问题] 降低 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