On Tue, Feb 17, 2009 at 3:30 PM, Johan Oudinet <[email protected]> wrote: > > On Tue, Feb 17, 2009 at 10:08 PM, William Stein <[email protected]> wrote: >> >> On Tue, Feb 17, 2009 at 10:36 AM, Johan Oudinet <[email protected]> >> wrote: >>> >>> On Tue, Feb 17, 2009 at 6:49 PM, mabshoff >>> <[email protected]> wrote: >>>> >>>> On Feb 17, 8:59 am, Johan Oudinet <[email protected]> wrote: >>> >>> Actually, I plan to using this code for larger matrices (up to 10^4), >>> so I don't think I could use a dense representation, do you? >> >> If you actually want to do this problem (esp. up to 10^4), you should >> actually use a dense matrices modulo a fixed prime <= 40000. You >> might also need access to our 128GB RAM box (we'll see). > > I understand the advantage to compute over a GF, but how can I be sure > the result is still valid over a rational field? > I mean, if I have to compute modulo a fixed prime, I should do the > same computation with several prime numbers and then recompose the > result, shouldn't?
It will be a billion times (or more) faster to figure out what the answer is. Once you morally know what the right answer will be and what sequence of computations to do, later doing it over QQ or modulo many primes will be easier. It's just the right sequence of steps for this problem imho. >> >> There are numerous inefficiencies in your script, e.g., in computing >> the rank of A and Ap*A you're doing exactly the same hard computation >> of one of the ranks twice. If you don't work modulo a prime, the >> coefficients of the products will surely blow up massively, and you'll >> get huge dense matrices with huge coefficients, as you observed. >> >> I've written a script to get you started on the right path: >> >> http://sage.math.washington.edu/home/was/comp/oudinet/ >> >> Note that I had to make a number of changes to your script to make it >> more efficient and have more debugging output so one can see what is >> happening. Running it, I can see it'll likely take a couple hours to >> finish and probably use < 1GB RAM (see below). I'm stopping it, but >> you can run it on your computer. best of luck, William > > Thank you very much for both your improvements and the debugging > output! I also agree with your comment about the stupidity of the > algorithm to extend the matrix to a square invertible matrix and that > it must have a better way to do this... > And your estimations are quite accurate! It took 30 minutes and used > 1GB of RAM. cool! > > Thanks again! You're welcome. Be sure to carefully read my code and check that it is giving what you need. William > -- > Johan > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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 URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
