[SciPy-User] solving large sparse linear system with Laplacian matrix

[josef.pktd at gmail.com]

On Fri, Oct 30, 2009 at 11:36 AM, Emmanuelle Gouillart
<emmanuelle.gouillart at normalesup.org> wrote:
>
>        Hello,
>
>        thank you very much for all your answers!
>
>        Josef, the scipy.sparse.linalg.factorized(A) tip works like a
> charm for solving efficiently for all right hand sides -- and the memory
> requirement is comparable to scipy.sparse.linalg.spsolve, so I guess the
> factorized matrices are not very dense... I can solve my system with
> N=10^6 in a few tens of seconds, which is really cool!

If this works, you could also try

scipy.sparse.linalg.splu

Based on the description, it works for square matrices, so maybe it is more
optimized for your case than factorized.

There is also umfpack, but since I don't have it, I don't know what's in there.

Josef

>
>        For more speed and memory improvements, it will take me some time
> to benchmark all the proposed solutions, so I shall report later on the
> solution that works best for me. Joachim Dahl mentioned off-list that the
> cvxopt package wraps Lapack's gbsv routine for banded matrices, which
> might also be an option (and it also wraps other functions mentioned by
> David such as ptsv). I will first try scipy's solutions such as lgmres
> and bicg.
>
>        Thanks a lot for your help, (and more later)
>
>        Emmanuelle
>
>> I don't know about memory consumption but I think
>> scipy.sparse.linalg.factorized(A)
>> should be more efficient if you need to solve for several right hand sides.
>
>> Josef
>
>
>> > For those curious about the background, I'm trying to implement Grady's
>> > random walker algorithm [1] to segment large 3-D X-ray tomography images.
>> > N=l**3 is the number of voxels in the cubic image, and M is the number of
>> > regions which I would like to segment. I don't require a very good
>> > precision on the elements of the solution X.
>
>> > Thanks in advance,
>
>> > Emmanuelle
>
>> > [1] L. Grady, "Random walks for image segmentation", IEEE Trans. on
>> > pattern analysis and machine intelligence, Vol. 28, p. 1768, 2006.
>
>> > _______________________________________________
>> > SciPy-User mailing list
>> > SciPy-User at scipy.org
>> > http://mail.scipy.org/mailman/listinfo/scipy-user
>
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>