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

Dominique Orban dominique.orban@gmail....
Fri Dec 10 19:35:23 CST 2010


> ---------- Forwarded message ----------
> From: "Raul Acuña" <raultron@gmail.com>
> To: scipy-user@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@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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20101210/852ae94f/attachment.html 


More information about the SciPy-User mailing list