# [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,
outer_v=outer_v)

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
subspaces.

--
Pauli Virtanen

```