On Tue, Feb 17, 2009 at 10:36 AM, Johan Oudinet <[email protected]> wrote: > > Hi Michael, > > On Tue, Feb 17, 2009 at 6:49 PM, mabshoff > <[email protected]> wrote: >> >> >> >> On Feb 17, 8:59 am, Johan Oudinet <[email protected]> wrote: >>> Hi, >> >> Hi Johan, >> >>> When I using the following simple script to get a square dxd >>> inversible matrix (T) from a dxr matrix (T0), I got a memory overflow: >>> ####################### >>> T=T0;rt=r;d=A.ncols();i=0 >>> while rt != d: >>> while rt == rank(T.augment(matrix(d,1,{(i,0):1}))): >>> i+=1 >>> T=T.augment(matrix(d,1,{(i,0):1})) >>> rt+=1 >>> ####################### >>> >>> Since the matrix A is a dxd - with d equals to 1183 - that easily fits >>> into the memory (4GB), it seems strange to me that this script needs >>> more and more memory until reach a memory overflow. Maybe there is a >>> memory leak in the function rank or augment? Or, more likely, I did >>> something wrong when writing this script (since I'm a beginner in both >>> Sage and Python)? >>> >>> The entire script (with the 1183x1183 matrix) is available >>> here:http://www.lri.fr/~oudinet/pub/script.sage >> >> What Sage release are you running? It sounds very much like this could >> be a memory leak. > > I've just downloaded the Linux binaries from Sage website (the > ubuntu-64bit-intel-xeon version) > > Sage Version 3.2.3, Release Date: 2009-01-05 > > >> >> The matrix is sparse and pre Sage 3.3 rank was computed using pari > > How can I get Sage 3.3? From the Sage website, I can only find the > 3.2.3 version. > >> which tends to blow up since it uses *a lot* of memory. We now switch >> back to computing the rank of such a matrix by using the much faster >> dense representation, but John Palmieri as the author of that code >> should fill you in on the details there. > > 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). 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 wst...@sage:~/comp/oudinet$ sage ---------------------------------------------------------------------- | Sage Version 3.2.3, Release Date: 2009-01-05 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- sage: load script.sage sage: A,B,k = go() k=1, rank_Ap=1039, rank_ApA=921 k=2, rank_Ap=921, rank_ApA=831, rank_Ap-rank_ApA=90, memory=767.54296875 k=3, rank_Ap=831, rank_ApA=773, rank_Ap-rank_ApA=58, memory=767.5390625 k=4, rank_Ap=773, rank_ApA=738, rank_Ap-rank_ApA=35, memory=767.5390625 k=5, rank_Ap=738, rank_ApA=726, rank_Ap-rank_ApA=12, memory=767.5390625 k=6, rank_Ap=726, rank_ApA=721, rank_Ap-rank_ApA=5, memory=767.5390625 k=7, rank_Ap=721, rank_ApA=720, rank_Ap-rank_ApA=1, memory=767.5390625 k=8, rank_Ap=720, rank_ApA=720, rank_Ap-rank_ApA=0, memory=767.5390625 rt = 720, d = 1183, mem=737.421875 got rt = r0 (=720) rt = 721, d = 1183, mem=756.9453125 rt = 721, r0 = 722, i = 1, mem=763.4765625 got rt = r0 (=721) rt = 722, d = 1183, mem=763.4765625 rt = 722, r0 = 723, i = 2, mem=770.0234375 got rt = r0 (=722) rt = 723, d = 1183, mem=770.0234375 rt = 723, r0 = 724, i = 3, mem=770.0234375 got rt = r0 (=723) William --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
