Timeline for Complexity of linear solvers vs matrix inversion
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2015 at 12:18 | comment | added | Federico Poloni | It sounds like OP is interested in the theoretical big-O-complexity problem. It is true that these algorithms are not usable in practice, but I believe that the question still stand on its own (and it is a good MO question). | |
| Dec 8, 2015 at 18:02 | comment | added | Carlo Beenakker | my phrasing was not accurate, the complexity $N^2$ is after the factorization (which has to be done only once) | |
| Dec 8, 2015 at 17:59 | comment | added | Alm | I just commented your first line "A linear solver with optimal complexity $N^2$...". It seemed that you were referring to Cholesky decomposition, which is not optimal. I find curious that an algorithm for solving linear equations has the same computational cost when applied for inverting a matrix. In the case of the decomposition, this comes because you can use it multiple times, as you said. But is there some smart way that uses the linear solver as a black-box for solving efficiently the inversion. | |
| Dec 8, 2015 at 17:54 | comment | added | Carlo Beenakker | @AlbertoMontina --- Cholesky decomposition solves the first linear equation with $N^3$ cost, the remaining $(N-1)$ linear equations each with $N^2$ cost (because the factorization can be reused), so the total cost for matrix inversion via Cholesky decomposition is order $N^3$, as worked out in the paper to which I have linked --- or have I misunderstood your question? | |
| Dec 8, 2015 at 15:46 | comment | added | Alm | But Cholesky decomposition does not have $N^2$ complexity when applied for solving linear equations. The computational time of solving linear equations or inverting matrices has the same identical power law by using the decomposition. This puzzles me. I am wondering if the two problems are essentially equivalent in the end. | |
| Dec 8, 2015 at 14:46 | history | edited | Carlo Beenakker | CC BY-SA 3.0 |
added 9 characters in body
|
| Dec 8, 2015 at 14:30 | history | answered | Carlo Beenakker | CC BY-SA 3.0 |