Echelon Form and Nullspace

• Echelonization over fields and euclidean domains
• Nullspace (many different techniques including sparse, p-adic and modular algorithms)
• Determinant (modular algorithms over $\mbox{\bf Z}$ and $\mbox{\bf Q}$)
• Solution of systems of linear equations

Given a 301 by 300 matrix over $\mbox{\bf Z}$ with random entries between 0 and 10, Magma can compute its nullspace in 9.1 seconds on a 400Mhz Sun SPARC workstation (using the fast p-adic algorithm). (The nullity is nearly always 1, and the integer entries of the non-zero null vector usually have about 450 digits each.) This can be compared with an algorithm of J. Buchmann and D. Squirrel for computing nullspaces in the Lidia system[4] which takes 3 hours and 54 minutes for the same problem on an SPARC (speed unspecified). Even assuming conservatively that they have used a 200Mhz processor (so we halve their time), Magma is thus about 750 (sic) times faster.