On Sat, May 28, 2011 at 1:41 PM, Josh <joshua...@gmail.com> wrote: > Hi all, > > I would like to compute the nullspace basis of a dense (exact) > rational matrix. Is this possible in linbox? It looks like the methods > in solutions/nullspace.h only work for finite fields, as they use > FFLAS for the LU decomposition... (but I'm a little new to all these > linear algebra packages, so forgive me if this is a silly question). > > If it's not possible in linbox, does anyone have any suggestions of > packages that do this? (I was using GAP, but it was incredibly slow, > because the bit-sizes of the intermediate results get big, and it's > doing straightforward exact rational arithmetic rather than something > like p-adic lifting.)
I wrote code that is in Sage (see [1] and [2]), which is free and open source, to do this, that is a wrapper around IML [3] + Linbox + some of my own ideas. It can do nullspace of a 300x301 with 64-bit entries in about 4 seconds (the entries of the answers have over 10000 digits each). Here's an example of how to use Sage for this problem: sage: a = matrix(QQ, 2, 3, [1,2,7/9,8,4,6/3]) sage: a.right_kernel() Vector space of degree 3 and dimension 1 over Rational Field Basis matrix: [ 1 19/4 -27/2] For many more examples, see the worksheet I just published at [4]. For bigger problems you may need more RAM, which means installing Sage on your own computer. I compared some timings with GAP (as you'll see in [4]), and Sage is dramatically faster. This is probably partly because the released version of GAP (at least the one in Sage) doesn't even have asymptotically fast arbitrary precision integers (e.g., [5])... 10 x 11 -- Sage: 0.05 seconds, GAP: 0.03 seconds 20 x 21 -- Sage: 0.01 seconds, GAP: 0.20 seconds 30 x 31 -- Sage: 0.02 seconds, GAP: 0.93 seconds 40 x 41 -- Sage: 0.03 seconds, GAP: 2.77 seconds 50 x 51 -- Sage: 0.04 seconds, GAP: 7.77 seconds [1] http://sagemath.org [2] try instantly at http://flask.sagenb.org [3] http://www.cs.uwaterloo.ca/~astorjoh/iml.html [4] http://flask.sagenb.org/home/pub/72/ [5] http://mpir.org/ When I wrote this code in 2007, for some range of matrix sizes and bitsizes it was the fastest code in the world (even solidly beating Magma, which was the fastest before)... mainly since IML is so damned good. I don't know what the current situation is. -- William > > Thanks, > Josh > > -- > You received this message because you are subscribed to the Google Groups > "linbox-use" group. > To post to this group, send email to linbox-...@googlegroups.com. > To unsubscribe from this group, send email to > linbox-use+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/linbox-use?hl=en. > > -- William Stein Professor of Mathematics University of Washington http://wstein.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
