Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Calculating the null space of a matrix with univariate polynomial entries?

• To: mathgroup at smc.vnet.net
• Subject: [mg67227] Calculating the null space of a matrix with univariate polynomial entries?
• From: "scott.morrison at gmail.com" <scott.morrison at gmail.com>
• Date: Tue, 13 Jun 2006 01:07:25 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

Hi,

I'm having great difficulty calculating null spaces of (fairly sparse)
matrices with univariate polynomial entries. There's an example below.

First, I'm finding NullSpace[m, Method->OneStepRowReduction] gives much
better results than any of the other methods, but it still very
unsatisfactory. My typical experience with larger matrices (roughly
40x40), such as the one below, is that Mathematica will work for quite
some time (25 minutes, in the example below), and then start allocating
huge amounts of memory (hundreds of MBs), causing paging and an
eventual crash.

This doesn't seem reasonable, although I haven't yet tried these
examples in any other computer algebra systems.

Does anyone know what's going on? Is there something I can do to avoid
this issue? Does anyone know of an implementation of NullSpace specific
to univariate polynomial matrices?

Any help much appreciated!

Scott Morrison,
UC Berkeley

This example is also online at
http://math.berkeley.edu/~scott/A1_2_5_0.m in case it gets munged here.
Incidentally, I know the null space is meant to be 6 dimensional, if
that happens to help (and I'll always know this dimension for my other
examples).

{{q^4*(q^(-1) + q), 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {q^4*(q^(-1) + q), q^4*(q^(-1) + q), 0, 0, q^2*(q^(-1) + q), 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {q^2*(q^(-1) + q), 0, q^4*(q^(-1) + q), 0, 0, q^2*(q^(-1) + q), 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, q^2*(q^(-1) + q), q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q),
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, q^(-1) + q, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, q^4*(q^(-1) + q),
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, q^2*(q^(-1) + q), 0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, q^2*(q^(-1) + q), 0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, q^2*(q^(-1) + q), q^2*(q^(-1) +
q),
  0, q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, q^(-1) + q, 0, 0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), q^(-1) + q,
0, 0,
  0, 0, 0, 0, q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0}, {0, 0, 0, 0, 0, 0, 0, q^(-1) + q, q^(-1) + q, 0, 0, 0, 0, 0,
0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), 0, q^(-1) + q, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
  q^2*(q^(-1) + q), q^2*(q^(-1) + q), 0, q^(-1) + q, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q,
0, 0,
  q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1)
+ q,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), q^(-1) + q, 0,
  q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1)
+ q,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, q^(-1) + q, 0, q^(-1)
+ q,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, (q^(-1) + q)/q^2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^4*(q^(-1) +
q),
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), 0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q),
0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q),
  q^2*(q^(-1) + q), 0, q^2*(q^(-1) + q), 0, 0, 0, 0, q^(-1) + q, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0,
0,
  q^2*(q^(-1) + q), 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1)
+ q),
  q^(-1) + q, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) +
q,
  q^(-1) + q, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), 0, q^(-1) + q,
0, 0,
  0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0,
0, 0,
  0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^2*(q^(-1) + q), q^2*(q^(-1) + q), 0, q^(-1) + q, 0, 0, 0,
0,
  q^(-1) + q, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0,
0, 0,
  0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, q^(-1) + q, 0, 0, q^(-1) + q, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,
  q^2*(q^(-1) + q), q^(-1) + q, 0, q^(-1) + q, 0, 0, 0, 0, q^(-1) + q,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  q^(-1) + q, q^(-1) + q, 0, q^(-1) + q, 0, 0, 0, 0, q^(-1) + q, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, q^(-1) + q, (q^(-1) + q)/q^2, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, q^2*(q^(-1) + q), q^(-1) + q, 0, (q^(-1) + q)/q^2, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, q^(-1) + q, q^(-1) + q, 0, (q^(-1) + q)/q^2, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, q^(-1) + q, (q^(-1) + q)/q^2, (q^(-1) + q)/q^2,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), 0, q^(-1) + q, 0, 0,
0, 0,
  (q^(-1) + q)/q^2, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  q^2*(q^(-1) + q), q^2*(q^(-1) + q), 0, q^(-1) + q, 0, 0, 0, 0,
  (q^(-1) + q)/q^2, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  q^(-1) + q, 0, 0, q^(-1) + q, 0, 0, 0, 0, (q^(-1) + q)/q^2, 0, 0, 0,
0, 0,
  0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), q^(-1) +
q, 0,
  q^(-1) + q, 0, 0, 0, 0, (q^(-1) + q)/q^2, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, q^(-1) + q, 0,
  q^(-1) + q, 0, 0, 0, 0, (q^(-1) + q)/q^2, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q^(-1) + q, (q^(-1) +
q)/q^2,
  0, 0, 0, 0, 0, (q^(-1) + q)/q^2, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, q^2*(q^(-1) + q), q^(-1) + q, 0, (q^(-1) +
q)/q^2, 0,
  0, (q^(-1) + q)/q^2, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, q^(-1) + q, 0, (q^(-1) + q)/q^2, 0, 0,
  (q^(-1) + q)/q^2, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, q^(-1) + q, (q^(-1) + q)/q^2, (q^(-1) + q)/q^2, 0, 0,
  (q^(-1) + q)/q^2}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 
  0, 0, 0, 0, 0, q^(-1) + q, (q^(-1) + q)/q^2, (q^(-1) + q)/q^4}}

• Follow-Ups:
  • Re: Calculating the null space of a matrix with univariate polynomial entries?
    • From: Daniel Lichtblau <danl@wolfram.com>