Re: complexity of Mathematica NullSpace[]
- To: mathgroup at smc.vnet.net
- Subject: [mg28545] Re: [mg28528] complexity of Mathematica NullSpace[]
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 25 Apr 2001 19:21:52 -0400 (EDT)
- References: <200104250530.BAA19339@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
axc at poincare.EECS.cwru.edu wrote:
>
> anyone know what algorithm Mathematica uses in NullSpace[] and its complexity
> and while you're at it, if it's easier to find NullSpace[B] when B is
> boolean, and when it's over {-1,0,1}?
>
> alan calvitti
> case western reserve u
For inexact matrices Mathematica finds the singular value decomposition
and works from there. For other matrices the idea is to do row reduction
to reduced echelon form, then use that to find a spanning set of null
vectors. If the matrix is square with n rows these methods all use
O(n^3) field operations. For general rectangular matrices, say m x n, I
think it is O(m^2*n). Note that in the exact or symbolic case
intermediate growth can mean the bit complexity is much worse.
For the boolean case, use Modulus->2. For the other case you can use
Modulus->3 and then symmetrize so that 2-->-1. The both suffer no
intermediate swell, hence complexity is O(n^3) bit operations.
An alternative for the boolean case might be to represent each row as a
big integer and use BitXor for the reduction steps. This can be superior
for sufficiently large matrices. I have code to do this sort of thing in
a notebook from our 1999 Developer's conference. It may be found at
http://library.wolfram.com/conferences/devconf99/
(find the appropriate notebook and click) or look at the HTML version at
http://library.wolfram.com/conferences/devconf99/lichtblau/
Daniel Lichtblau
Wolfram Research
- References:
- complexity of Mathematica NullSpace[]
- From: axc@poincare.EECS.cwru.edu
- complexity of Mathematica NullSpace[]