0
$\begingroup$

Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$).

There is a large amount of algorithms for symmetric problems (conjugate gradient) and square non symmetric ones (BICGstab). But I have difficulties to find a method for both at ones.

I recently saw this artivle http://dl.acm.org/citation.cfm?id=355989 where the problem is restated as $$\begin{pmatrix}I & A \\ A^T & -\lambda I \end{pmatrix} \begin{pmatrix}r \\x \end{pmatrix}=\begin{pmatrix}b\\0\end{pmatrix}$$ with a small Tikhonov regularization weight $\lambda$ and $r$ as the residuum.

Does anyone know a better approach for this? I would like to avoid storing the data in $A$ twice.

Thank you very much!

$\endgroup$

1 Answer 1

1
$\begingroup$

A widely used iterative method for large scale linear least squares problems that allows for regularization if you want/need it is the LSQR algorithm of Paige and Saunders. See http://www.stanford.edu/group/SOL/software/lsqr/

$\endgroup$
2
  • $\begingroup$ I probably should have mentioned the authors of the link I posted. Its also from Paige and Saunders. :) However, thank you very much for the link! It is at least a great confirmation of that I did not found something too exotic and that this is a widely used approach. $\endgroup$
    – mojovski
    May 18, 2014 at 8:40
  • $\begingroup$ Note that you don't actually have to store multiple copies of $A$ and $A^{T}$. All that LSQR requires is that you be able to compute the matrix vector products $Ax$ and $A^{T}y$. One copy of the $A$ matrix is sufficient for this. $\endgroup$ May 18, 2014 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.