<div class="gmail_quote">On Sat, Nov 5, 2011 at 15:23, Mark F. Adams <span dir="ltr"><<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div>Uzawa is a great algorithm, very popular, dead simple (two lines), embarrassingly robust and fast.</div></blockquote><div><br></div><div>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</div>
<div><br></div><div><font class="Apple-style-span" face="'courier new', monospace">[A  B'] X = F</font></div><div><font class="Apple-style-span" face="'courier new', monospace">[B   0] Y = G</font></div>
<div><br></div><div>Uzawa is algebraically equivalent to using the factorization</div><div><br></div><div><font class="Apple-style-span" face="'courier new', monospace">[1        0] [A  B']</font></div><div><font class="Apple-style-span" face="'courier new', monospace">[BA^{-1}  1] [0   S]</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="arial, helvetica, sans-serif">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.</font></div>
<div><font class="Apple-style-span" face="arial, helvetica, sans-serif"><br></font></div><div><font class="Apple-style-span" face="arial, helvetica, sans-serif">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.</font></div>
</div>