It was even slower than A.solve_right(check=False). The results from timeit (on my workstation) were
767 microseconds for b in A.column_space() and 481 microseconds for A.solve_right(b,check=False) but 10000 iterations of IsConsistent(A,b) in Magma (on the same computer -- called from SAGE) yielded 14 microseconds per iteration This was all with solving over the rationals. By contrast, (implicitly using Hermite normal form) it was 625 microseconds for A.solve_right(b), where now A was a matrix over Z (and not over Q as above). I was just glancing at the appropriate code and it is all written in cython. On first glance it appears to be doing the correct thing and not to be obviously wasting any time, but the huge discrepancy between it and Magma points to an important thing to be worked on. Victor On May 26, 1:46 pm, John Cremona <[email protected]> wrote: > Victor, > > How fast is it to do > > b in A.column_space() > > ? > > John > > On May 25, 7:48 pm, VictorMiller <[email protected]> wrote: > > > I have a sage program which involves a lot of calculations of the > > form: > > > solve for x, Ax = b, where A is an integral matrix and x and b are > > column vectors. A is an integer matrix, but the solution (if it > > exists) for x might be rational. Actually I want more than this: > > > I want to also determine the kernel of A. It turns out that magma has > > a function which does this: > > > IsConsistent(A,b) which returns a boolean (saying if it's solvable), a > > value for x, and the kernel of A. > > > I know that I can get the same functionality in Sage by doing > > something like: > > > try: > > x = A.change_ring(QQ).solve_right(b) > > K = A.right_kernel() > > # process x and K > > except: > > print "no solution" > > > This appears to be wasteful because, whatever elimination algorithm is > > being used by solve_right, would almost immediately yield the kernel, > > so that it's wasteful to redo the calculation. So, perhaps > > solve_right could have an optional argument like kernel=True, etc. > > > By the way, I've tried using hermite_form instead, but that's much > > much slower. > > > I've found however, that magma's IsConsistent function is MUCH faster > > than this (by over a factor of 30). > > As usual, it's impossible to figure out what algorithm Magma is > > using, but this indicates that some work should be done on the sage > > functions. To be specific, the matrices that I'm processing are > > fairly small (say 5 by 4) 0/1 matrices. > > > Victor > > -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
