[petsc-dev] Bordered systems and low-rank corrections

[Jed Brown]

On Sat, Nov 5, 2011 at 15:23, Mark F. Adams <mark.adams at columbia.edu> wrote:

> Uzawa is a great algorithm, very popular, dead simple (two lines),
> embarrassingly robust and fast.
>

It's only fast if the Schur complement is well-conditioned. This is true
for some popular problems, but I'm less gushing over the algorithm. Bramble
et al use the notation

[A  B'] X = F
[B   0] Y = G

Uzawa is algebraically equivalent to using the factorization

[1        0] [A  B']
[BA^{-1}  1] [0   S]

where S = B A^{-1} B' is the Schur complement, and using Richardson
iteration (possibly preconditioned) to solve completely with S. This should
make it clear why Uzawa only converges quickly if S is well-conditioned (or
you have a very good preconditioner). Of course, we observe that Richardson
rarely beats a Krylov method for other problems, so it makes sense to use a
Krylov method when solving with S. This is sometimes called "accelerated
Uzawa", or just Schur Complement Reduction.

An alternative is to apply A^{-1} inexactly, perhaps only apply a
preconditioner for S (instead of doing inner iterations) and run a Krylov
method in the full space. If you do this, the lower-triangular part of the
factorization can usually be dropped because it does not affect the
eigenvalues (all eigenvalues are 1, with minimal polynomial of degree 2).
This is the philosophy of the "block preconditioners" crowd. It often wins
over SCR when the fields are well-scaled, but SCR is more robust to
radically different scales for the primal and dual variables.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111105/efde78db/attachment.html>