On Feb 17, 10:36 am, Johan Oudinet <johan.oudi...@gmail.com> 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. :)
> Best regards,
>
> --
> Johan
Cheers,
Michael
--~--~---------~--~----~------------~-------~--~----~
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
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
