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? > > 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. Thanks again! -- Johan --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
