Timeline for Cholesky Rank-1 downdate extension
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 1, 2011 at 16:21 | comment | added | Brian Borchers | My oops- I had thought there was an $O(n^2)$ way to get the inverse of a lower triangular matrix but my memory was faulty. Sorry about that. For the product form cholesky factorization, look at the 2005 paper by Goldfard and Scheinberg, "Product-form Cholesky factorization in interior point methods for second-order cone programming" and follow references back from there. See portal.acm.org/citation.cfm?id=1058105 | |
| May 1, 2011 at 11:06 | comment | added | R Turner | Thanks, Solving $L x = y$ is $O(n^2)$, but it seems that computing $L^{-1}$ would require solving that system for each unit vector and thus be $O(n^3)$ unless there are some tricks I am unaware of. They don't seem to be implemented in matlab if they exist. What are the best references to solving this problem using the product form Cholesky? | |
| May 1, 2011 at 11:03 | comment | added | Federico Poloni | Seconded. As usual with computations that involve inverses, you need to ask yourself "do I really need to compute this inverse element-by-element, or can I store it in some factored form that still allows to compute matvec products in $O(n^2)$ and matmat in $O(n^3)$?". In most cases, the second option holds, and the factored form is faster and stabler. | |
| Apr 30, 2011 at 20:04 | history | answered | Brian Borchers | CC BY-SA 3.0 |