2
$\begingroup$

NullSpace function gives a list of vectors that forms a basis for the null space of the input matrix.

When the rank of the input argument matrix $M_{m\times n}$ is exactly $n-1$, then the null space becomes the only non-zero null vector $Z$ of $M$ such that: $M\cdot Z=0$, which can also be obtained by singular value decomposition of $M$.

But by comparing the time consumption of SingularValueDecomposition and NullSpace, the latter is usually much faster, this indicates they are using different algorithms.

Then: what is the algorithm used by NullSpace function? It seems there is no clue here.

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Depends on the type of matrix. For example if it is exact and numeric e.g. all integers, NullSpace will use some manner of Gaussian elimination and that will be faster than (exact) SVD. Absent some indication of matrix type and size though everything is just speculation. $\endgroup$
    – Daniel Lichtblau
    Commented Dec 11, 2014 at 15:44
  • $\begingroup$ @DanielLichtblau Are you aware of which "Method" would be most suitable in dealing with a symbolic (5 variables), large (666x667) but sparse (<10%) matrix? And is there any literature available on the performance of these methods in various context? $\endgroup$
    – DaveWasHere
    Commented Nov 27, 2022 at 21:12
  • 1
    $\begingroup$ @DaveWasHere I doubt any method would handle a matrix of that size unless the sparseness pattern made it exceptionally well behaved. But I'd pick OneStepRowReduction for this. (Except...sometimes DivisionFreeRowReduction performs better. Heuristics for this choice are not so easy to come by.) $\endgroup$
    – Daniel Lichtblau
    Commented Nov 28, 2022 at 17:55
  • $\begingroup$ @DanielLichtblau Thank you for the answer! So should I understand that in such complicated cases the option Automatic is to avoid? To me this makes more sense since we "help" Mathematica to make a choice causing it to "think less" in principle. $\endgroup$
    – DaveWasHere
    Commented Nov 28, 2022 at 19:44
  • $\begingroup$ @DaveWasHere Offhand I don't know which of the two the Automatic will select. But if you want to force one or the other method then by all means set that option explicitly. $\endgroup$
    – Daniel Lichtblau
    Commented Nov 29, 2022 at 0:47

1 Answer 1

Reset to default
2
$\begingroup$

NullSpace works on both numerical and symbolic matrices.

and implied by your link, under "Details" subsection, "Method" would sort of refer to the algorithm NullSpace uses.

Possible settings for the Method option include "CofactorExpansion", "DivisionFreeRowReduction", and "OneStepRowReduction". The default setting of Automatic switches among these methods depending on the matrix given.

So it depends on the matrix entries. So, as Daniel was saying, there is probably some form of Gaussian elimination at play.

Improve this answer
$\endgroup$

Your Answer

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

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