[SciPy-User] scipy.sparse.linalg.bicg for Non Symmetric Matrix.

Dominique Orban dominique.orban@gmail....
Sat Dec 11 12:44:33 CST 2010


On Sat, Dec 11, 2010 at 1:00 PM, <scipy-user-request@scipy.org> wrote:

> ---------- Forwarded message ----------
> From: "Raul Acuña" <raultron@gmail.com>
> To: SciPy Users List <scipy-user@scipy.org>
> Date: Fri, 10 Dec 2010 22:10:31 -0430
> Subject: Re: [SciPy-User] scipy.sparse.linalg.bicg for Non Symmetric
> Matrix.
> Hi Dominique,
>
> Thank you for your reply it was very helpful. I definitely have an
> over-determined system, I need to find the solution in the least amount of
> time possible, i've used the SVD method and now I'm experimenting with the
> iterative methods, someone told me that they are faster.
>
> I used the Conjugate Gradient function from SciPy using a trick to convert
> the original system: Ax = b    to a system with a square matrix:
>  dot(A.T,A)x = dot(A.T,b). It is working and it finds a good solution faster
> than the SVD method. However I dont know if this is the ideal method.
>
> Now, looking at your reply, and to your advice of using MINRES. I read that
> this method guaranteed convergence, but in terms of speed is MINRES a
> better method?. Also, sorry about my ignorance but i didnt understand this:
>
> [  I   A ] [ r ] = [ b ]
> [ A.T  0 ] [ x ]   [ 0 ]
>
>
> What is " r " in that system?. I want to try this method with my system
> using the function from scipy and also try the one in PyKrylov.
>
>
> Thanks again,
>
> best regards,
>
> Raúl
>

Hi Raúl,

Sorry, perhaps I'm using notation that may not be clear to everyone. The
notation

[  I   A ] [ r ] = [ b ]
[ A.T  0 ] [ x ]   [ 0 ]

means that you're solving a linear system with a coefficient matrix defined
by blocks (in Matlab notation, it would be something like [I, A ; A', 0]).
If your A is m-by-n, this matrix is (m+n)-by(m+n). It is quite a bit larger
but it is very sparse. The right-hand side is a vector of length m+n with
your vector b in its first m components, and zero elsewhere. Similarly, the
solution will be composed of two parts. The first segment of length m, which
I call r, is the residual vector because you can deduce from the system that
r = b - A*x. The second segment, x, will be the solution you are looking
for.

In your case, you will also want to try LSQR (available in NLPy). On paper,
it is equivalent to applying CG to the square symmetric and positive
semi-definite system dot(A.T,A)x = dot(A.T,b) but it should be more stable
(and it never forms the matrix dot(A.T,A)). It may turn out to be more
efficient than MINRES.

Keep in mind that iterative methods are appropriate for large systems but
they often require a good preconditioner to be effective. For an excellent
account of all this, you may want to look at Yousef Saad's book "Iterative
Methods for Sparse Linear Systems."

Good luck,

-- 
Dominique
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20101211/1b6eb0b2/attachment.html 


More information about the SciPy-User mailing list