5
$\begingroup$

Suppose I have a linear system

$$ \left\lbrack \begin{array}{cc} M_1& S\\ S^{\mathrm{T}}& M_2 \end{array} \right\rbrack \left\lbrack \begin{array}{c} X\\ Y\end{array} \right\rbrack= \left\lbrack \begin{array}{c} F\\G\end{array}\right\rbrack, $$ where $M_1\in \mathrm{R}^{n\times n}$ is symmetric positive definite, $M_2\in \mathrm{R}^{m\times m}$ is symmetric positive semi-definite. $S$ is a full-rank matrix of compatible size. $X,Y,F,G$ are all vectors of appropriate size.

What factors are relevant in deciding between using GMRES on the big system and using a Schurr complement technique?

Factors that I would guess are relevant are how expensive $M_1$ is to invert, the condition number of $S$, and whether $M_2$ is the zero matrix.

Any links to the literature are appreciated.

Edit

I am asking this question because I need to solve the following system.

$$ \left\lbrack \begin{array}{cccc} M_1& S &0 &\Gamma^{\mathrm{T}} \\ -S^{\mathrm{T}}& 0 &\Xi^{\mathrm{T}}& 0\\ 0 & \Xi & 0 &0 \\ \Gamma&0&0&0 \end{array} \right\rbrack \left\lbrack \begin{array}{c} x_1\\x_2\\x_3\\x_4 \end{array} \right\rbrack= \left\lbrack \begin{array}{c} f_1\\f_2\\f_3\\f_4 \end{array} \right\rbrack $$

Right now, I solve this system using the Schurr complement method but it requires three iterative CG solves. I am wondering if it would be better to just "brute force it" and use GMRES.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Since the system is symmetric, you may want to consider MINRES instead of GMRES. It generates roughly similar iterates but keeps around less previous iterates and therefore uses much less memory. $\endgroup$
    – Nick Alger
    Oct 7, 2015 at 16:52
  • $\begingroup$ Correct me if I am wrong but I was under the impression the GMRES is somehow more stable that MINRES. Is that not true? $\endgroup$
    – fred
    Oct 7, 2015 at 17:19
  • $\begingroup$ Some people think so, but it seems to be a highly debatable point. In my personal experience (with difficult saddle point systems), MINRES works great. $\endgroup$
    – Nick Alger
    Oct 7, 2015 at 19:52
  • $\begingroup$ The reason why people use GMRes is because it allows for the use of non-symmetric preconditioners (which are generally better) whereas MinRes requires symmetric preconditioners (which are generally worse). $\endgroup$
    – Wolfgang Bangerth
    Oct 8, 2015 at 2:52

1 Answer 1

Reset to default
3
$\begingroup$

You can often manipulate systems like this using a block LU factorization; the factors you mentioned then come into play. Preconditioners can then be designed by taking advantage of the block diagonal structure revealed by the factorization, with the blocks being $M_1$ and the Schur complement $M_2-S^TM_1^{-1}S$.

An advantage of this approach is that you can also utilize approximate matrix-free inverses for $M_1$ and the Schur complement, which is useful if your matrices are just too big to form and manipulate. For example, for finite element discretizations of incompressible flow, $M_1^{-1}$ can be replaced by a few multigrid iterations. Preconditioners for the Schur complement can also be approximated using matrix-free methods.

Some care should be taken in constructing these preconditioners (for example, Wathen shows cases where substituting a matrix inverse with an iterative method fails because it induces a nonlinear operator instead of a linear one).

Edit: as Wolfgang Bangerth pointed out, this issue can also be solved by employing a flexible CG or GMRES outer iteration.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The solution to the problem by Wathen is to use F-GMRES instead of GMRES. $\endgroup$
    – Wolfgang Bangerth
    Oct 8, 2015 at 2:53
  • $\begingroup$ Agreed, added to the above. $\endgroup$
    – Jesse Chan
    Oct 8, 2015 at 13:18

Your Answer

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

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