mabshoff wrote: > > > On Feb 17, 10:36 am, Johan Oudinet <[email protected]> wrote: >> Hi Michael, > > Hi Johan, > > <SNIP> > >> 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 >> > > Ok. > >>> 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. > > Sage 3.3 isn't released yet, but there is another release candidate > tonight, i.e. 3.3.rc2. Sage 3.3 it self should be out in the next 2, 3 > days, but it has been slower than we had planned. > >>> 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? > > Well, you do multiplies AFAIK and that should destroy the sparse > structure rather quickly assuming your matrix doesn't have a special > structure. So, any ideas if the sparse structure is preserved? > >> >>>> I'd appreciate any help. >>> I am running the computation right now on a box with 128 GB, so we >>> will see how far I get :) Right now we are in the 30th iteration of >> Wow! 128GB, it's very nice for doing such computations! > > Well, I didn't pay for it :) > >> How can you know the number of iterations in a Sage script? Is there a >> debug mode, or something like that? > > I just added a print statement in the loops. If this all ended I > didn't really want to see "True" or "False" at the end :) > > After about 60 minutes and maybe 80 iterations in rt I killed it > consuming about 40GB of RAM. So something is going wrong. Two > thoughts: > > * you are hitting a yet diagnosed memory leak - I will check that > * since your matrix coefficients are rational they just explode - not > much we can do about that. Using a ring with finite precision, i.e. > RealField() might avoid that. > * your sparse structure gets destroyed and you end up with dense > matrices anyway, ergo bye bye free RAM > > Obviously it can be all three :) > >>> 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 >>> and we are already consuming about 2.5GB RAM. There are some known >>> problem with LA in Sage that are leaky, but I suspect those are >>> reference count issues in Cython. Cython 0.11 out soon should help >>> there with the new reference count nanny. >> Well, my goal is to find a matrix B and a number n such that for every >> number k>n, B*A^(k+1) == A^k with respect to A is a dxd sparse matrix >> over Rational field (actually A is an adjacency matrix of a finite >> directed graph). >> The algorithm I implemented works (at least for small matrix and where >> rank(A^k) > 0), but it's not really optimized (I'm far from being an >> expert in linear algebra)! >> I'm interesting in a faster algorithm for both numerical and exact >> solutions. So, if someone knows a better solution (for example, a >> classical algorithm in linear algebra that solves this problem), I'll >> be glad to have some references ;-) > > Ok, I am not the guy who knows the literature well, so someone else > needs to answer this. But there are plenty of people from graph theory > around here. :)
If you're willing, could you rephrase the problem in terms of directed graphs, if that is a natural way to look at it? Jasn --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
