Timeline for Lower Bound on the Cost of Solving Linear System
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Jan 21, 2011 at 17:19 | comment | added | Suvrit | Good point Igor; somehow I oversaw that in my haste. But I guess then one could argue that if even an inexact solution cannot be done better than in some time, say T, then getting an exact solution should be ever harder. | |
| Jan 21, 2011 at 15:34 | comment | added | Igor Rivin | Notice that the OP specifically asks for "exact" solution. | |
| Jan 20, 2011 at 14:30 | comment | added | David Harris | Gaussian Elimination over a black-box field $F$ requires $O(n^3)$ arithmetic operations, where an arithmetic operation is defined to be an access to the arithmetic oracle for $F$. In some fields, such as finite fields of fixed size, there is no coefficient growth so this estimate is exactly right. For fields such as $\mathbf R$ or $\mathbf C$, typically one approximates these with floating-point representations. In this case, Gauss Elimination uses $O(n^3)$ flops (but may commit some inaccuracy in the result). | |
| Jan 20, 2011 at 9:48 | history | edited | Suvrit | CC BY-SA 2.5 |
added link to spielman
|
| Jan 20, 2011 at 9:12 | history | answered | Suvrit | CC BY-SA 2.5 |