Define the Hermite Normal form $H$ for a matrix $A\in Z^{n\times n}$ as following:

$$H=UA$$ which in Mathematica is given as {u, h} = HermiteDecomposition[a]

Then for a system of homogeneous equations $Ax = [0]_{n}$ we normally compute a basis for the Nullspace of $A$, so any vector $x$ in $Ker(A)$ satisfies the system.

It results that $$Ax=[0]_{n} \rightarrow U^{-1}Hx =[0]_{n} \rightarrow Hx = [0]_{n}$$

Then computing such a basis for $A$ can be done in terms of $H$, where $H$ is an upper triangular matrix, so at first glance NullSpace runs faster for $H$ instead of $A$.

But I'm not very familiarized with the time-complexity of Mathematica's implementation of HermiteDecomposition and Nullspace (this last one over a prime modulus). I don't think this would be a good idea for big dimensions, this is, big $n$.

The thing is that I need a $\textit{fast}$ and efficient method for computing a basis for the nullspace of $A$ over $F_2$ when $n$ is considerably big. What can I do?

P.D = As a recommendation from MarcoB the time lapses are given with an example matrix of size $100\times 100$:

NullSpace only call: $0.010054$s

HermiteDecomposition + NullSpace: $0.071549$s

LatticeReduce + NullSpace: $0.258836$s

where the NullSpace call is always taken over $F_2$.

  • 2
    $\begingroup$ Well, since both functions HermiteDecomposition and Nullspace are already available, couldn't you just make up some fake number with which to try both out and compare timings (e.g. with RepeatedTiming)? $\endgroup$
    – MarcoB
    Nov 19, 2019 at 20:39
  • $\begingroup$ I thought the same on my way to home. Will post time lapses as soon as I return to my research. Thanks. $\endgroup$
    – kub0x
    Nov 19, 2019 at 21:04
  • $\begingroup$ @MarcoB: New day, new tests. Included time lapses for my method with an example squared matrix with $n=100$. When $n=2500$ it takes $1$ minute approximately to compute such a basis over $F_2$, so what can I do to optimize this procedure in Mathematica? Any alternative that I can implement and you can point me to? Thanks for your kind help. $\endgroup$
    – kub0x
    Nov 20, 2019 at 12:03
  • $\begingroup$ Thank you for running the tests. Please include the specific code and data you used in your question, so others can play around with it and chime in. $\endgroup$
    – MarcoB
    Nov 20, 2019 at 13:51
  • $\begingroup$ Why not just use NullSpace[mat,Modulus->2]? $\endgroup$ Nov 20, 2019 at 15:43

1 Answer 1


There are at least a few ways to improve matters. First is to use


This is still memory hungry though. There is a splitting method, useful when the row count is large, that is shown here.

Another method, which can be used in tandem with splitting, is to use bit strings to represent rows. The null space can then be extracted with ResourceFunction["BitStringNullSpace"], documentation for which is found here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.