Timeline for fast merging of orthogonal bases
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2010 at 8:13 | comment | added | Federico Poloni | If $p\gg \max(r_1,r_2)$, then the coefficient in front of both QR and matrix product is 2, so the matrix products are indeed slower than the QR --- a good "cheatsheet" reference for the computational costs is Appendix C of Higham, "Functions of matrices". Other things matter such as the so-called "level-3 factor", but I think in a good BLAS implementation the costs are of the same order of magnitude. Frankly I don't think the orthogonality of the other matrix can be exploited; if you manage to exploit it, let me know because the same idea could apply to an algorithm I'm working on. :) | |
| Jul 28, 2010 at 5:55 | comment | added | RedSnow | True, so the complexity is $O(\text{matrix product} + \text{QR})=O(pr_1r_2 + p\text{ min}(r_1, r_2)^2=O(pr^2)$ for $r\approx r_1 \approx r_2$. Now that's the theoretical big $O$. But where can the orthonormality of $U_2$ be used, to give at least some boost for practical applications? The QR part is obviously much slower than the multiplication, so never mind the matrix product for now. | |
| Jul 27, 2010 at 17:23 | comment | added | Federico Poloni | You're missing something in your computational cost, the first matrix product costs $O(pr_1r_2)$. I don't think you can save more than that, though. | |
| Jul 26, 2010 at 15:34 | comment | added | RedSnow | Nice, cheers. The way I read that formula, it drops complexity from $O(p(r_1 + r_2)^2)$ (QR of $U^{p \times (r_1+r_2)}$ to $O(p\text{ min}(r_1, r_2)^2)$ (QR of whichever $V$ is smaller), which is not bad but I think we should be able to do better. | |
| Jul 26, 2010 at 13:05 | history | answered | Federico Poloni | CC BY-SA 2.5 |