0
$\begingroup$

As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU.

Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is fairly popular for solving unstructured systems. I am trying to implement GMRES and QMR as a substitute.

EDIT: To limit scope of the question

My questions is:

  • Has anyone published a comparison between GMRES and QMR? If not, has anyone published a good survey on the convergence of any of the two? Any resources towards this?
Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ There is nothing useful to say without knowing spectral information about the matrix. If you don't have a preconditioner and the matrices don't have any exploitable spectral structure, then just use LU. Also note that there are many more Krylov methods than just GMRES and QMR. $\endgroup$
    – Jed Brown
    Commented Mar 23, 2012 at 12:43
  • $\begingroup$ @JedBrown, Thats what I want to know. In which spectral condition would GMRES or QMR be better than the other. Which other Krylov subspace methods exist for unstructured matrices? CGNE is another but that is just "conveting" an unstructured matrix to symmetric. $\endgroup$
    – Inquest
    Commented Mar 23, 2012 at 12:47
  • $\begingroup$ Let's flip this thing around. Why don't you tell us what spectral properties or other structure your problem has (e.g. coming from a class of integral operators) instead of asking us to summarize the content of thousands of papers and books in hope that something might be relevant to you. $\endgroup$
    – Jed Brown
    Commented Mar 23, 2012 at 15:58
  • $\begingroup$ Actually, my intention is to design algorithms and test them in places where they might fail. To narrow it down even further, I'm interested in convergence analysis of GMRES and QMR. $\endgroup$
    – Inquest
    Commented Mar 23, 2012 at 16:04
  • $\begingroup$ I suggest looking at the references in this answer. It is very easy to write matrices for which all but one type of iterative method fails (needs $\mathcal O(n)$ iterations to converge while the other converges fast, e.g. in $1$ iteration). $\endgroup$
    – Jed Brown
    Commented Mar 24, 2012 at 17:09

1 Answer 1

Reset to default
3
$\begingroup$

There are many more ways to solve unstructured dense system of equations (to vary a well-known title, probably at least 19 different ways).

In particular, CGS and BiCGStab are interesting iterative ones, and QR is a very important direct one - numerically more stable than LU with column pivoting.

Comparisons are moot, as advantagens and disatvantages depend on the accuracy wanted, the level of robustness required, and (in randomized tests) the distribution of the matrix entries assumed. It also depends on the implementation (LU comes in different pivoting variants), whether the matrices are appropriately scaled, etc..

Vanilla GMRES is trivially convergent, as after $n$ steps, it minimizes over the full space. (If you limit memory, then you have lots of different GMRES's, and comparisons are even more questionable.)

For superlinear convergence under certain conditions, see http://ta.twi.tudelft.nl/nw/users/vuik/papers/vdV93V.pdf

The defining paper ''QMR: a quasi-minimal residual method for non-Hermitian linear systems'' on QMR gives in Section 6 a convergence analysis, again under certain conditions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "..to vary a well-known title, probably at least 19 different ways..". Can you tell me which source this is? $\endgroup$
    – Inquest
    Commented Mar 30, 2012 at 13:54
  • $\begingroup$ This was an allusion to papers such as: C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Review (2003), 3-49. - To see more examples, search for the phrase ''Nineteen ways'' in scholar.google.com . _ I haven't seen the phrase applied to dense linear systems, though. $\endgroup$
    – Arnold Neumaier
    Commented Mar 30, 2012 at 14:12

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.