8
$\begingroup$

I am trying to compute the null space of a large $n\times n$ sparse matrix. No matter how large the dimension of the matrix is, it will always look like as below:

enter image description here

The figure on the left shows the version of the matrix for with 10-dimension and the right panel is the ~1700 version. As can be seen, it will always be a very sparse matrix and I'm trying to find its null space. Are there any suggestions on what would be the most efficient way to do so? Or at least, is NullSpace[] the most efficient tool in this case?

In terms of dimensionality, I'm aiming to go as high as the computational power of Mathematica allows me. I have already seen the question here and I also have tried RowReduce as well, but I'm always getting the error "Result for RowReduce of badly conditioned matrix". Nullspace seems to work fine (albeit slow), at least up to n~40000 that I've tried so far.

Update

Link to a notebook that generates the matrix.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Indeed, NullSpace should be the way to go. Maybe Eigensystem[A, -1, Method->"Arnoldi"] with suitable shift might also help. But as always, it depends on your concrete matrix. Would you please share the code that generates it? $\endgroup$
    – Henrik Schumacher
    Commented Aug 1, 2019 at 0:14
  • 3
    $\begingroup$ Hmm. Apparently, {lambda, u} = Eigensystem[NullMatrix, -1, Method -> {"Arnoldi"}]; works fine. u[[1]] seems to be the only null vector. Or do you expect more than one? Then you can do, e.g., {lambda, u} = Eigensystem[NullMatrix, -20, Method -> {"Arnoldi"}]; and check the vector lambda of eigenvalues for zero (or near-zero) entries. $\endgroup$
    – Henrik Schumacher
    Commented Aug 1, 2019 at 3:26
  • 1
    $\begingroup$ Thank you very much for your comment! Really appreciate it. To answer your questions, yes, in the actual system (based on physical reasoning), I only expect one null vector. And the system is some sort of special generalization of steady-state mean-field theory for spins other than 1/2. $\endgroup$
    – Arian
    Commented Aug 1, 2019 at 4:42
  • 3
    $\begingroup$ @DanielLichtblau Very interesting approach; I will keep it in mind (+1). However, I am not convinced that this will work out in OP's example: Szabolcs had a very tall matrix in the other post, so the nullspaces of top can be expected to be rather small. However, this matrix here is a square $n \times n$-matrix, so Nullspace[top] will have at least $n$ elements... and I doubt that Nullspace[top] will be particularly sparse. $\endgroup$
    – Henrik Schumacher
    Commented Aug 2, 2019 at 13:09
  • 2
    $\begingroup$ @HenrikSchumacher All good points. The method I linked to would probably not be so good here, barring someone figuring out improvements that elude me (and perhaps simply do not exist). $\endgroup$
    – Daniel Lichtblau
    Commented Aug 2, 2019 at 16:02

1 Answer 1

Reset to default
5
$\begingroup$

Turning a comment into an answer.

Apparently, 

{lambda, u} = Eigensystem[NullMatrix, -1, Method -> {"Arnoldi"}];

works fine. u[[1]] seems to be the only null vector. Or do you expect more than one? Then you can do, e.g., 

{lambda, u} = Eigensystem[NullMatrix, -20, Method -> {"Arnoldi"}];

and check the vector lambda of eigenvalues for zero (or near-zero) entries.

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.