Let's consider a system of linear equations with integer coefficients: n=3 m=5 A=random_matrix(ZZ,n,m) b=random_vector(ZZ,n)
What is the best way to find an integer vector x such that Ax=b? A rational solution is of course found by A.solve_right(b). A random example: A=matrix(ZZ,3,5,[-1, 0, -1, -1, 1, 0, -2, -1, 1, -8,-1, 0, 2, -8, -2]) b=vector(ZZ,3,[-1,-1,15]) A.solve_right(b) gives (-13/3, -13/6, 16/3, 0, 0), although there are integer solutions, e.g.: (-221, 13, 144, 65, -13) Is there also a good way to get all integer solutions? In the example above that would be something like: [-10*t0 - 30*t1 - 221, -2*t0 + 3*t1 + 13, 7*t0 + 19*t1 + 144, 3*t0 + 9*t1 + 65, -2*t1 - 13] for integer variables t0 and t1. The best way I could think of is to implement the algorithm from section 4.5.2 from Knuth's TAOCP. (This is also where the solutions above come from) Is there a simpler way to do that in sage? Of course to we could formulate the same question in terms of linear equations instead of matrices, but then solve() also gives rational, non-integer solutions. Maybe the right thing to use would be isolve from maple, but the interface is broke ( see http://trac.sagemath.org/sage_trac/ticket/12295 ). To consider the problem as linear program and use MixedIntegerLinearProgram() with integer constrains works, but it is very very slow for larger systems. Any help will be appreciated, moritz -- You received this message because you are subscribed to the Google Groups "sage-support" group. To post to this group, send email to sage-support@googlegroups.com. To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en.
