1
$\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$
  • $\begingroup$ What happens if you try SingularValueDecomposition[] on it? It's really hard to say anything meaningful otherwise without seeing your matrix. $\endgroup$ – J. M. will be back soon Sep 26 '17 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$ – Daniel Lichtblau Sep 26 '17 at 14:13
  • $\begingroup$ @J.M. SingularValueDecomposition doesn't seem to give any output in a reasonable time (~30m). $\endgroup$ – oscarafone Sep 26 '17 at 20:06
  • $\begingroup$ @DanielLichtblau I'd be happy to post the matrix. How should I do it? $\endgroup$ – oscarafone Sep 26 '17 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$ – Daniel Lichtblau Sep 26 '17 at 21:24
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$
  • $\begingroup$ Excellent, Daniel! Thanks! But how did you figure out that that setting would speed things up? $\endgroup$ – oscarafone Sep 27 '17 at 22:10
  • $\begingroup$ General experience. Possibly it should be the default when the matrix is exact and NumericQ, I'm not sure. $\endgroup$ – Daniel Lichtblau Sep 27 '17 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$
  • $\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$ – oscarafone Sep 26 '17 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 '17 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$ – oscarafone Sep 26 '17 at 23:03
  • $\begingroup$ @oscarafone, might be a bit more accurate to say that you have a sparse matrix with exact number entries. $\endgroup$ – J. M. will be back soon Sep 26 '17 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$ – oscarafone Sep 27 '17 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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