0

If I were to hand you a general unstructured matrix A and a right hand side b, what would be your preferred iterative solver for solving Ax=b? Why?

Matt
  • 402

2 Answers2

0

Are you looking for a commercial feasibility solver or just the algorithm? also there is a question of what you know about $A$?

If you know $A$ is full rank, or a feasible solurion exists, then use the Gauss-Jordan Algorithm

Otherwise, if you are looking for an approximate solution, then leas-squares solution will help: $x=(A^TA)^\dagger A^T b$, where $(A^TA)^\dagger$ is the pseud0-inverse of $(A^TA)$b (meaning $(A^TA)^\dagger(A^TA)\approx I$, which means if $(A^TA)^\dagger$ is not invertible then either use Moor-penrose inverse or te Tikhonov regularization $(A^TA)^\dagger=((A^TA)+\epsilon I)^{-1}$ for some small enough $\epsilon$).

Note that if $A$ is a full-rank invertible matrix then the solution of least-squares and Gauss-Jordan elimination will be the same, except the second one is more expensive.

If you know some thing about $A$ (like sparsity), then you can exploit that information as well.

If there are more than one solution, then you can use the $x=B^T\lambda+x_0$, as the solution, where $x_0$ is one specific solution and $B$ is a matrix whose columns are built by bases vectors of the null-space of $A$, and $\lambda$ is an arbitrary vector.

Community
  • 1
Alt
  • 2,592
  • Good point. suppose the matrix is fairly large (1000x1000) at least, and is known to have a unique solution. is there a krylov method that is well suited to unstructured matrices? (Not necessarily symmetric or even having complex entries). – Matt Feb 22 '14 at 21:53
  • @Matt It depends. If you have a good preconditioner, you can pick GMRES, which is optimal but can be costly if you need to perform a lot of iterations and in such a case you need to restart it. Or you can try, e.g., BiCGStab, which is not optimal, but is quite cheap: http://en.wikipedia.org/wiki/Generalized_minimal_residual_method http://en.wikipedia.org/wiki/Biconjugate_gradient_stabilized_method – Algebraic Pavel Feb 24 '14 at 09:42
  • @Matt Anyway, a $1000\times 1000$ matrix is at this time not really large for direct solvers (unless you want to solve the problems on some ridiculous architecture) so you could even consider Gaussian elimination, in particular, if your matrix is sparse. – Algebraic Pavel Feb 24 '14 at 09:44
0

This is rather vague. If the size of $A$ is not large, say less than $100 \times 100$ then Gaussian elimination is the method of choice.

From a numerical point of view when $A$ is large, and $A$ has some structure that makes multiplying by $A$ simple, then I usually do the following

  1. Find a $B$ so that $A B \approx I$ and multiplying by $B$ is simple.
  2. Start with $r_o = B b$ successively evaluate $r_{n+1} = r_n + B (b-A r_n)$

Proof that this works.

Suppose $x$ is the solution, i.e. $b = A x$. Then $$ r_{n+1}-x = r_n - x + B (A x - A r_n) = (I-BA) (r_n - x) $$ Now if $$\left|| I - BA\right|| = \rho < 1$$ then $$ \left|| r_{n+1}-x \right|| \le \rho \left|| r_{n}-x \right|| \le \rho ^n \left|| r_0-x \right||$$

Thus if $\rho << 1$ this process ends very rapidly.

user44197
  • 9,730