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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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/

Improve this answer
$\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
    Commented 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$
    – Brian Borchers
    Commented May 18, 2014 at 14:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .