Timeline for Complexity of computing matrix rank over integers
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2011 at 20:42 | vote | accept | user1855 | ||
| May 9, 2011 at 20:42 | vote | accept | user1855 | ||
| May 9, 2011 at 20:42 | |||||
| Apr 28, 2011 at 15:36 | comment | added | Charles | Right, using Bareiss' algorithm space needed is at most 0.5 n lg n + O(n) due to a theorem of Hadamard. This means that each operation takes time $O(n(\log n)^{2+\varepsilon})$ giving overall time complexity $O(n^4(\log n)^{2+\varepsilon}).$ | |
| Apr 28, 2011 at 13:14 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
clarify and include refs
|
| Apr 28, 2011 at 11:13 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |