On Wed, Feb 18, 2009 at 1:21 AM, William Stein <wst...@gmail.com> wrote: > > On Tue, Feb 17, 2009 at 4:13 PM, Johan Oudinet <johan.oudi...@gmail.com> > wrote: >> >> On Tue, Feb 17, 2009 at 7:56 PM, Jason Grout >> <jason-s...@creativetrax.com> wrote: >>> >>> mabshoff wrote: >>>> >>>> >>>> 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 :) >> >> Since I'm just adding sparse vectors, I don't think the sparse >> structure is destroyed here. > > You do this: > > A = Ap * A > > which is matrix multiplication over QQ. That quickly leads to dense > matrices with huge entries, which could simply use a lot of RAM.
Yes, but for this matrix, the memory problem only occurs later, when I have a dxr matrix (T0) and try to get a square invertible matrix (T). And in the loop, there is only addition of sparse vectors, no matrix multiplication. > >> But, as the computation works with a ring with finite precision >> (GF(997)), the problem should be on the coefficient explosion (when >> computing the rank) and/or a memory leak in the rank function applied >> to a sparse matrix over Rational field. >> >>>> >>>>>> 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? >> >> Well, in terms of directed graphs, I have a graph where its vertices >> and edges are related to a recurrence relation as follows: >> V(0) = 1 (or could be 0 in a generalized version of my problem) >> and for each n > 0: >> V(n+1) = \sum_{over the successors, V^\prime, of V} V^\prime(n) >> >> And I want to build a graph that its edges are labeled by rational >> numbers and that represents the inverse of the previous recurrence >> relation: >> V(N) = CN (a finite number) >> V(0) = 1, V(1) = C1, ..., V(k) = Ck >> and for each n st k < n < N: >> V(n) = \sum_{V - e -> V^\prime} e * V^\prime(n+1) >> >> But I have no idea how to build this graph directly from the first >> graph, that's why I prefer formulating the problem as a linear algebra >> problem. >> -- Johan --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---