The RationalDenseNullSpace command computes the nullspace of the input Matrix. It does this by computing nullspaces modulo primes (see LinearAlgebra:-Modular:-RowReduce) followed by rational reconstruction (see iratrecon). Bad primes are discarded in the same way as in the modular gcd algorithm. The algorithm is output sensitive: the CPU time depends not only on the size of the input, but also on the output. Specifically, the number of primes that are used depends on the largest entry in the output. If its size is well below the theoretical upper bound, which is usually the case, then the algorithm will be very efficient. By default, it does not return an answer unless a correctness test is passed. If the test does not pass, an additional prime is used to update the answer and the test is run again (and so on, until the test passes).

To ensure that the algorithm returns the correct answer, it checks that M times the output is zero. However, this multiplication can cost more CPU time than the rest of the computation combined. If the option skiptest is given, that correctness check is skipped. This is most useful in code where the correctness of the answer can be verified more efficiently later.

$\mathrm{with}\left(\mathrm{SolveTools}\left[\mathrm{LinearSolvers}\right]\right)\:$

$N≔200\:$$n≔100\:$$r≔\mathrm{rand}\left(-1000..1000\right)\:$

$M≔\mathrm{Matrix}\left(N+n\,N\right)\:$

$$\begin{gathered} \mathbf{for}i\mathbf{to}N+n\mathbf{do} \\ \mathbf{for}j\mathbf{from}\max \left(1\,i-n\right)\mathbf{to}N\mathbf{do} \\ M\left[i,j\right]≔r\left(\right) \\ \mathbf{end}\mathbf{do} \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$

$\mathrm{V1}≔M·\mathrm{Vector}\left(\left[\mathrm{seq}\left(r\left(\right)\,i=1..N\right)\right]\right)\:$

$\mathrm{V2}≔M·\mathrm{Vector}\left(\left[\mathrm{seq}\left(r\left(\right)\,i=1..N\right)\right]\right)\:$

$M≔⟨\mathrm{V1}\left|\mathrm{V2}\right|M⟩\:$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{LinearAlgebra}:-\mathrm{NullSpace}\left(M\right)\right)\:$

memory used=11.36GiB, alloc change=333.86MiB, cpu time=80.69s, real time=72.35s, gc time=12.41s

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{RationalDenseNullSpace}\left(M\right)\right)\:$

memory used=21.30MiB, alloc change=484.00KiB, cpu time=98.00ms, real time=98.00ms, gc time=0ns

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{RationalDenseNullSpace}\left(M\,'\mathrm{skiptest}'\right)\right)\:$

memory used=1.84MiB, alloc change=476.00KiB, cpu time=51.00ms, real time=51.00ms, gc time=0ns