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

Pauli Virtanen pav+sp@iki...
Fri Oct 30 04:50:59 CDT 2009

Fri, 30 Oct 2009 04:43:23 -0400, David Warde-Farley wrote:
> On 30-Oct-09, at 4:25 AM, josef.pktd@gmail.com wrote:
>> 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.
> You may be right but the factorized matrices may be an awful lot denser
> which could impact her memory requirements.
> You may have some luck with lgmres and/or bicg, as far as I know neither
> imposes conditions on positive definiteness.

I remember there's also a block-version of LGMRES that's expected to be 
somehow more efficient with multiple right-hand sides. The implementation 
in scipy is for the plain version, however, and IIRC handles only one rhs 
at a time.

I guess you can already do something similar:

	outer_v = []
	r = zeros_like(B)
	for j, b in enumerate(B.T):
	    r[j] = scipy.sparse.linalg.lgmres(A, b, inner_m=6, tol=1e-6,
	                                      inner_m=10, outer_k=6,

Ie. store part of the old solution subspace, to accelerate solution of 
the next linear systems. This might (I'm not really sure) help if the 
right-hand side vectors are in some sense "similar" to each other.

In addition to scipy.sparse.linalg.lgmres, you can also try plain GMRES 
(scipy.sparse.linalg.gmres) -- if it converges, it might be faster, since 
the linear algebra part of current LGMRES implementation in Scipy is not 
fully optimized and may become slow if you choose to use huge inner 

Pauli Virtanen

More information about the SciPy-User mailing list