On Tue, Feb 17, 2009 at 4:13 PM, Johan Oudinet <[email protected]> wrote:
>
> On Tue, Feb 17, 2009 at 7:56 PM, Jason Grout
> <[email protected]> wrote:
>>
>> 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 :)
>
> 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.
> 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
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
