2
$\begingroup$

Below is a matrix diagram, produced in Mathematica. In this case it's a $956\times 950$ rectangular matrix. The white parts are all zero.

sa = Import["https://pastebin.com/raw/fiErKrhU", "Package"];
MatrixPlot[sa]

MatrixPlot

I'm wondering if there is a way to efficiently compute the null space of this matrix. From a different calculation entirely (using a Molien series), I know in advance there should be 6 linearly independent vectors in this null space, and I already know one of them.

The NullSpace routine takes too long to be feasible. I am hoping that there is a better way. I know that using NullSpace[N[m]] will return the answer rather quickly, but I am hoping to be able to do this symbolically.

Any help would be appreciated.

Update

Added SparseArray data for this matrix. It was too large for this message so I put it on pastebin.

https://pastebin.com/raw/fiErKrhU

$\endgroup$
7
  • $\begingroup$ What happens if you try SingularValueDecomposition[] on it? It's really hard to say anything meaningful otherwise without seeing your matrix. $\endgroup$ Sep 26, 2017 at 3:20
  • $\begingroup$ If the nonzero entries are approximate numbers then it should be quite fast. Really hard to say more without the actual input (which can be added explicitly to the question as a SparseArray) $\endgroup$ Sep 26, 2017 at 14:13
  • $\begingroup$ @J.M. SingularValueDecomposition doesn't seem to give any output in a reasonable time (~30m). $\endgroup$
    – user48731
    Sep 26, 2017 at 20:06
  • $\begingroup$ @DanielLichtblau I'd be happy to post the matrix. How should I do it? $\endgroup$
    – user48731
    Sep 26, 2017 at 20:08
  • $\begingroup$ I think it would be good to create it as SparseArray[{{rowi,rowj}->valueij,...}] and put that in your question. From the picture there should be "only" a few thousand values so that should not overly bloat the question. $\endgroup$ Sep 26, 2017 at 21:24

2 Answers 2

4
$\begingroup$

Turns out this can be done with exact methods and a good option setting. And a dose of patience. I won't copy the matrix itself. In my session I named it mat as below.

AbsoluteTiming[
 nullspace = NullSpace[mat, Method -> "OneStepRowReduction"];]

(* Out[18]= {1839.141297, Null} *)

Check size and correctness:

Length[nullspace]

(* Out[19]= 6 *)

LeafCount[nullspace]

(* Out[20]= 50803 *)

Max[Abs[mat.Transpose[N[nullspace]]]]

(* Out[21]= 1.00182351685*10^-10 *)

I also have tried the method here but with no luck thus far. Oh well (I blame the author...)

$\endgroup$
2
  • $\begingroup$ Excellent, Daniel! Thanks! But how did you figure out that that setting would speed things up? $\endgroup$
    – user48731
    Sep 27, 2017 at 22:10
  • $\begingroup$ General experience. Possibly it should be the default when the matrix is exact and NumericQ, I'm not sure. $\endgroup$ Sep 27, 2017 at 23:20
0
$\begingroup$

I think you're having problems because the numbers in the array are rationals. I copy/pasted your matrix, it gives a sparse array object that I named 's'. Then N[ ] transforms it into floating point numbers, and

NullSpace[N[s]] // Length

returns 6.

$\endgroup$
6
  • $\begingroup$ Yes, I know this. In fact this is what I meant when I said "using machine precision resolves the issue but I am aiming for a symbolic solution." I used clumsy wording and that's probably why you didn't realize I said that. Anyway, I appreciate the help regardless. $\endgroup$
    – user48731
    Sep 26, 2017 at 22:11
  • $\begingroup$ OK -- but it seems a stretch to say that this is a "different calculation entirely". Also, you are misusing the term "symbolic", your matrix has no symbols, only rationals. $\endgroup$
    – bill s
    Sep 26, 2017 at 22:18
  • $\begingroup$ I didn't say it was a different calculation entirely, I'm not sure why you quoted that. Also forgive me, I'm not sure what the appropriate word to use is in this case. Perhaps "non-decimal"? $\endgroup$
    – user48731
    Sep 26, 2017 at 23:03
  • $\begingroup$ @oscarafone, might be a bit more accurate to say that you have a sparse matrix with exact number entries. $\endgroup$ Sep 26, 2017 at 23:06
  • $\begingroup$ @bills I understand now. I actually computed the rank of the null space by using a Molien series -- that's how I got the number 6. That is what I meant by "different calculation entirely". Sorry for the confusion. $\endgroup$
    – user48731
    Sep 27, 2017 at 2:36

Your Answer

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