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