5
$\begingroup$

My problem is composed of two parts, a large sparse matrix $L$ ($m$x$n$ where $m=10^3$, and $n=10^5$, with $10^7$ non-zero complex numbers), and a dense, symbolic matrix $F$ ($m$x$m$ where $m=10^3$), which is the partial derivative of the outer product of a symbolic vector: $F = \partial_x ( A^TA ) $ where $A=\{1,x,y,z,x^2,xy,...\}$. Note that this leaves F with a very large null space whose dimension is $m-2$, and is actually very easy and fast to compute.

My problem is that I want to find the null space of $L^*FL$.

Further, it even doesn't have to be with Mathematica if there is a solution in another fashion. Is this computationally feasible? It isn't through just a conventional call since the computer runs out of memory just constructing $L^*FL$. Are there properties of matrices that I am overlooking that would be useful here?

Edit: Specifically, $A$ is a vector of all powers of $x,y,z$ that form a power series up to some maximum total power, and $x,y,z$ are all real valued. Their ordering is not important.

Improve this question
$\endgroup$
14
  • $\begingroup$ $F$ is symmetric, then? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Oct 23, 2015 at 15:34
  • $\begingroup$ Yes, and the three unknown symbols ($x,y,z$) that comprise it are real valued. $\endgroup$
    – Craig
    Commented Oct 23, 2015 at 15:38
  • $\begingroup$ Would it be feasible for you to generate the eigensystem of $F$? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Oct 23, 2015 at 15:41
  • 1
    $\begingroup$ @J.M. what about the simpler route of determining whether the two eigenvectors of $\mathbf{F}$ that don't lie in its null-space also lie in the null space of $\mathbf{L}$? If they do, then doesn't the null-space of $\mathbf{L}^\ast\mathbf{F}\mathbf{L}$ span the entire space? $\endgroup$
    – rcollyer
    Commented Oct 23, 2015 at 16:24
  • 1
    $\begingroup$ @rcollyer If those vectors are also null then L^*FL is all zeros. $\endgroup$
    – Daniel Lichtblau
    Commented Oct 23, 2015 at 18:07

1 Answer 1

Reset to default
8
$\begingroup$

The null space is going to be a very large matrix. I'll show how to generate the space of nonnull vectors (I think that might be called the coimage or something like that).

I will demonstrate this method for dimensions 56 by 1000 (56 because that's how many xyz monomials there are through degree 5).

deg = 5;
monoms = Union[
   Flatten[Outer[Times, Sequence @@ Table[{1, x, y, z}, deg]]]];
amat = Outer[Times, monoms, monoms];
dabara = D[Transpose[amat].amat, x];
dims = {Dimensions[dabara][[1]], 10^3};

I'll make a 56x1000 sparse array with 1s in 56 random locations.

SeedRandom[123456789];
lmat = SparseArray[
   Thread[Transpose[{RandomInteger[{1, dims[[1]]}, dims[[1]]], 
       RandomInteger[{1, dims[[2]]}, dims[[1]]]}] -> 1], dims];

Now we can generate nonnull vectors just by checking (non)nullity of all the unit vectors. Ordinarily this would not work so well but for this size null space it seems fine.

Timing[
 nonnullgenerators = 
   Cases[Table[
     Transpose[lmat].(dabara.(lmat.UnitVector[dims[[2]], j])), {j, 
      dims[[2]]}], Except[{0 ..}]];]
Length[nonnullgenerators]

(* Out[155]= {16.56656, Null}

Out[156]= 54 *)

We can remove excess to get the generators by row reduction.

Timing[rred = RowReduce[nonnullgenerators];]
nonnullspace = Cases[rred, Except[{0 ..}]];
Length[nonnullspace]

(* Out[157]= {29.7926, Null}

Out[159]= 2 *)

When the dimensions get to the point where this is unwieldy, an alternative might be to interleave row reduction with finding nonnulls.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wait, I am confused, this sounds like it will work for the non-null vectors, but I wanted the nullspace of $L^*FL$ $\endgroup$
    – Craig
    Commented Oct 23, 2015 at 20:49
  • $\begingroup$ Actually this is not even quite what I stated. It is the image, not coimage (I reduced the image vectors). So here is the question. How do you propose to describe the null space generators? For your dimensions there will be around 10^5 of them, and each will be of around that same length. That set could take up a lot of space. You can easily handle those that are simply unit vectors, describing by sparse matrices. But the others? $\endgroup$
    – Daniel Lichtblau
    Commented Oct 23, 2015 at 21:09

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.