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?
>
>> 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!
How can you know the number of iterations in a Sage script? Is there a
debug mode, or something like that?
>
> 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 ;-)
Best regards,
--
Johan
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
