In principle, computing the nullspace of a matrix is not a difficult thing to do. Gaussian elimination provides a simple algorithm which settles the problem completely and requires just a cubic number of operations. But in practice, if the coefficients of the system at hand are exact rational numbers or even polynomials in one or more indeterminates, the actual performance of classical Gaussian elimination can be much worse than the theory suggests. As a matter of fact, software packages like Maple or Mathematica sometimes already have difficulties solving systems of size 50x50 or so within a reasonable amount of time. If a dense linear system with thousands of unknowns is to be solved exactly, it is advisable to switch to finite fields, where computations can be done quickly, and then to reconstruct the rational solution from its homomorphic images. Also this technique was already known to Gauss, and it is nowadays a standard tool in all areas of computer algebra. We will explain it for the special situation of solving linear systems.
Forschungs-