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

[Raul Acuña]

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

On Fri, Dec 10, 2010 at 9:05 PM, Dominique Orban
<dominique.orban at gmail.com>wrote:

> > ---------- Forwarded message ----------
> > From: "Raul Acuña" <raultron at gmail.com>
> > To: scipy-user at scipy.org
> > Date: Thu, 9 Dec 2010 21:19:54 -0430
> > Subject: Re: [SciPy-User] scipy.sparse.linalg.bicg for Non Symmetric
> Matrix.
> > I made a typing error in the previous post, the first code segment is
> this one instead:
>  > Asym = matrix(dot(A.T,A))
> > bsym = matrix(dot(A.T,b))
> > sol = cg(Asym,bsym,tol = 1e-10,maxiter=30)
> >
> > On Thu, Dec 9, 2010 at 9:12 PM, Raul Acuña <raultron at gmail.com> wrote:
> >>
> >> Hi,
> >> Am using the iterative methods of scipy.sparse.linalg for solving a
> linear system of equations Ax = b. My matrix A is non symmetric. I've been
> using the scipy.sparse.linalg.cg() function multiplying both matrix "A"
> and "b" with the transpose of A so the matrix will become symmetric:
> >> Asym = matrix(dot(A.T,A))
> >> bsym = matrix(dot(A.T,b))
> >> sol = cg(A,b,tol = 1e-10,maxiter=30)
> >> Also i've been reading about the biconjugate gradient method, and if i
> am not mistaken the literature says that this method works on
> non-symmetric matrix, but when i try to use  scipy.sparse.linalg.bicg() it
> wont work:
>  >> sol = bicg(A,b,tol = 1e-10,maxiter=30)
> >>    File
> "C:\Python26\lib\site-packages\scipy\sparse\linalg\isolve\iterative.py",
> line 74, in bicg
> >>           A,M,x,b,postprocess = make_system(A,M,x0,b,xtype)
> >>    File
> "C:\Python26\lib\site-packages\scipy\sparse\linalg\isolve\utils.py", line
> 65, in make_system
> >>           raise ValueError('expected square matrix (shape=%s)' % shape)
> >>           NameError: global name 'shape' is not defined
> >> Any help will be greatly appreciated, am comparing this methods for my
> data with an important emphasis on speed for my master thesis, so any
> discrepancy with the theory would be a great problem for me.
> >> Thanks in advance,
> >>
> >> Raúl Acuña.
>
> Hi Raúl,
>
> You can't use Bi-CG or Bi-CGSTAB to solve non-square systems directly. Your
> system is either under- or over-determined. What you may be meaning to solve
> here is a related linear least-squares problem. If A has more rows than
> columns, you have an over-determined system (more equations than unknowns)
> and a relevant problem is to
>
>    minimize 1/2 * ||Ax - b||^2.
>
> Conversely, if A has more columns than rows, you have an under-determined
> system (more unknowns than conditions imposed on them) and you may want to
>
>   minimize 1/2 * ||x||^2  subject to  Ax=b
>
> i.e., find the least-norm solution among the infinitely many possibilities.
> In both cases, you can use MINRES, available in SciPy I think, or else in
> PyKrylov (https://github.com/dpo/pykrylov) and in NLPy (http://nlpy.sf.net)
> by solving the larger system
>
> [  I   A ] [ r ] = [ b ]
> [ A.T  0 ] [ x ]   [ 0 ]
>
>
> (for the first problem) or
>
> [ I  A.T ] [ x ] = [ 0 ]
> [ A   0  ] [ r ]   [ b ]
>
>
> (for the second problem). Though the coefficient matrix above is symmetric,
> it is indefinite, so you can't use CG! To use MINRES, you just need to write
> a function which computes the product of a vector with the coefficient
> matrix.
>
> In the first case, you can also use LSQR (available in NLPy and also
> probably in SciPy). In this case, you'll just need to be able to do A*x and
> A.T*y.
>
> --
> Dominique
>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>


-- 
Ing. Raúl Acuña

Profesor @Universidad Simón Bolívar
Grupo de Mecatrónica
Departamento de Electrónica y Circuitos
Tel. +58-212-4121983 / Cel +58-412-5840317
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20101210/0f722465/attachment.html>