One of my favorite little-known algorithmic facts is that a sparse system of n linear equations in n unknowns over a finite field can be solved in time O(mn) if

One of my favorite little-known algorithmic facts is that a sparse system of n linear equations in n unknowns over a finite field can be solved in time O(mn) if the corresponding matrix has m nonzero entries[1]. I'm surprised at how hard it is to extend this to the reals - it seems like dealing with the precision issues is much tougher than I imagined. [1] http://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Wiedemann86.pdf http://www.enseignement.polytechnique.fr/profs/informatique/...