Timeline for How to solve a system of linear equations without storing the matrix?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2012 at 12:38 | vote | accept | Ruslan | ||
| Dec 7, 2012 at 18:50 | answer | added | Dirk | timeline score: 6 | |
| Dec 7, 2012 at 16:03 | comment | added | Ruslan | @Per Alexandersson Of course, this is not an option. Even if HDD/SSD speed were comparable with RAM speed, it'd take petabytes of space for about a gig of RAM. | |
| Dec 7, 2012 at 15:16 | comment | added | Per Alexandersson | I assume reading parts of the matrix, modify them, and write back is out of the question, since this is essentially as having a huge swap...? | |
| Dec 7, 2012 at 14:21 | answer | added | Brian Borchers | timeline score: 3 | |
| Dec 7, 2012 at 12:40 | comment | added | Brendan McKay | If you don't need the exact solution but some approximation, you can use an iterative method like Gauss-Seidel. | |
| Dec 7, 2012 at 12:27 | comment | added | Emil Jeřábek | In principle, determinants, and therefore solutions of non-singular linear systems, are computable in $\mathrm{NC}^2$, and therefore in space $O(\log^2n)$ (not including the input and output). However, I rather doubt such algorithms would be practical. In particular, they need time $n^{O(\log n)}$, which most likely wouldn’t count as “not much slower”. | |
| Dec 7, 2012 at 11:57 | history | asked | Ruslan | CC BY-SA 3.0 |