Increase performance for null space calculation on symbolic matrix

Hello,

I try to calculate the null space of a symbolic matrix (~10000x20).

The computation takes about 3 minutes if I generate the symbolic matrix and substitute the symbols with numerical values before calculating the null space. If I calculate the null space for the symbolic version of the same matrix, it runs for more than a day.

Is there a way to lower the computation time? I'm already using simplify before the null space calculation.

If it would be possible to use parallel computing with null(), that probably would help a lot since Matlab is only maxing out one thread. Also, using the GPU is not possible with symbols as I found out.

Essentially null(sym_matrix) is one line in the script that can't really be optimized and I already simplified the input.

Thanks in advance,

Chris

Answer 1

[John D'Errico]

Surely you need to recognize the difficulties here. If not, then you need to consider what is involved.

Let me give a trivial example. Consider this easy to create matrix:

M8 = magic(8),rank(M8)
M8 =
    64     2     3    61    60     6     7    57
     9    55    54    12    13    51    50    16
    17    47    46    20    21    43    42    24
    40    26    27    37    36    30    31    33
    32    34    35    29    28    38    39    25
    41    23    22    44    45    19    18    48
    49    15    14    52    53    11    10    56
     8    58    59     5     4    62    63     1

ans =
     3

Now, if I try to compute null(M8), you will see it has 5 dimensions, thus is spanned by 5 vectors.

But now, lets create an associated matrix, of size 13x8, with symbolic entries. Idon't need to be any more creative that to write it as:

syms a b c d e
M = [M8;a*rand(1,8);b*rand(1,8);c*rand(1,8);d*rand(1,8);e*rand(1,8)];

What does computation of the null space involve now? Depending on the values of a,b,c,d,e, the null space can have dimension anywhere from 3 to 8.

This is a more complex problem than merely computing the null space for a purely numerical matrix, since there are many possibilities. And that is for a trivial problem. Had I been more creative in the above matrix, things can get highly nonlinear, with the nullspace vectors themselves changing shape as well as dimension.

So seriously, can you be remotely surprised that null is inefficient for a large dimensional symbolic matrix?

Can you force the use of multiple threads? Not really easy here, since multiple threads work well when you can pass things to linear algebra routines like the BLAS. MATLAB does that automatically. But symbolic computations are not something the BLAS can handle. So the symbolic toolbox logically tends to stay single threaded, and I doubt that will change soon.

Finally, just consider tat the null space of a 10000x20 array will be of size 10000x9980.

[Chris B]

Hello John,

thanks for your answer. No, I'm not surprised that calculating the null space of a symbolic matrix needs more time. I'm even happy that it is possible. I was just wondering if it is possible to, for instance, decompose the null space calculation and process parts in parallel this way.

[John D'Errico]

Not really possible that I see. A big part of the problem is that branches are bad for any kind of parallel computations. Consider the matrix:

A= [1 1;v 1]

When v==1, the null space is non-trivial. For any other value of v, it is empty. But for the large problems you describe, much of the computation may just be in the set of all of the special cases that change the dimension of that null space. I'd think of it as equivalent to computing ALL of the roots of a large, nonlinear system. And the null space vectors themselves may change in nonlinear ways.