On Sat, Dec 11, 2010 at 1:00 PM,  <span dir="ltr">&lt;<a href="mailto:scipy-user-request@scipy.org">scipy-user-request@scipy.org</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div id=":116">---------- Forwarded message ----------<br>From: &quot;Raul Acuña&quot; &lt;<a href="mailto:raultron@gmail.com">raultron@gmail.com</a>&gt;<br>To: SciPy Users List &lt;<a href="mailto:scipy-user@scipy.org">scipy-user@scipy.org</a>&gt;<br>

Date: Fri, 10 Dec 2010 22:10:31 -0430<br>Subject: Re: [SciPy-User] scipy.sparse.linalg.bicg for Non Symmetric Matrix.<br>Hi Dominique,<div><br></div><div>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&#39;ve used the SVD method and now I&#39;m experimenting with the iterative methods, someone told me that they are faster. </div>



<div><br></div><div>I used the Conjugate Gradient function from <span style="border-collapse:collapse;font-family:arial, sans-serif;font-size:13px">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.</span></div>



<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><br></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse">Now, looking at your reply, and to your advice of using MINRES. I read that this method guaranteed convergence, but</span></font><span style="border-collapse:collapse;font-family:arial, sans-serif"> in terms of speed is MINRES a better method?. Also, sorry about my ignorance but i didnt understand this:</span></div>



<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><br></span></font></div><div><span style="border-collapse:collapse"><span style="font-size:13px"><div>

<font face="&#39;courier new&#39;, monospace">[  I   A ] [ r ] = [ b ]<br>[ A.T  0 ] [ x ]   [ 0 ]</font></div></span></span><div><br></div><div><br></div><div>What is &quot; r &quot; in that system?. I want to try this method with my system using the function from scipy and also try the one in PyKrylov.</div>



<div><br></div><div><br></div><div>Thanks again,</div><div><br></div><div>best regards,</div></div><div><br></div><div>Raúl</div></div></blockquote></div><br>Hi Raúl,<div><br></div><div>Sorry, perhaps I&#39;m using notation that may not be clear to everyone. The notation</div>

<div><br></div><div><meta charset="utf-8"><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace; font-size: 13px; border-collapse: collapse; ">[  I   A ] [ r ] = [ b ]<br>[ A.T  0 ] [ x ]   [ 0 ]</span><br>

<div><br></div><div>means that you&#39;re solving a linear system with a coefficient matrix defined by blocks (in Matlab notation, it would be something like [I, A ; A&#39;, 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.</div>

<div><br></div><div>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 <meta charset="utf-8"><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">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.</span></div>

<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">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&#39;s book &quot;Iterative Methods for Sparse Linear Systems.&quot;<br clear="all">

</span></font><br></div><div>Good luck,</div><div><br>-- <br>Dominique<br>
</div></div>