15
$\begingroup$

Question:

Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$: $$A \approx B^TB$$ and $$A \approx C^TC,$$ where the inverses of the factors $B, B^T, C, C^T$ are easy to apply.

When is it possible to use information from both $B$ and $C$ to build a better preconditioner than either $B$ or $C$ alone?

$\endgroup$
13
$\begingroup$

You can use additive

$$ P_a^{-1} x = (B^T B)^{-1} x + (C^T C)^{-1} x, $$

multiplicative

$$ P_m^{-1} x = (B^T B)^{-1} x + (C^T C)^{-1} \Big(x - A (B^T B)^{-1} x \Big), $$

or symmetric multiplicative. Methods of this class are available in PETSc using PCCOMPOSITE in PETSc. For example,

petsc/src/ksp/ksp/examples/tutorials$ ./ex2 -m 100 -n 100 -ksp_monitor \ -pc_type composite -pc_composite_type multiplicative \ -pc_composite_pcs ilu,gamg 0 KSP Residual norm 7.088415699389e+01 1 KSP Residual norm 1.271768323411e+01 2 KSP Residual norm 1.529853612054e+00 3 KSP Residual norm 1.214841683459e-01 4 KSP Residual norm 8.341606406485e-03 5 KSP Residual norm 6.471990946051e-04 6 KSP Residual norm 8.082672366030e-05 7 KSP Residual norm 6.111138513482e-06 Norm of error 6.93786e-06 iterations 7

The users manual has a section on "Combining Preconditioners".

$\endgroup$
  • $\begingroup$ Excellent, thank you! Are you aware of any theory or papers that discuss the conditions under which these combinations would be effective or innefective, or is it just pretty much trial and error? $\endgroup$ – Nick Alger Feb 23 '14 at 17:30
  • $\begingroup$ As with all preconditioning, the analysis is in terms of the spectrum of a preconditioned operator, often expressed via a generalized eigenvalue problem. Intuitively, if each preconditioner target different processes or different parts of the spectrum, the intent of combination is to correct both parts. Most successful approaches of this class are based on subspace correction, which includes multigrid, domain decomposition, and field splitting (literature for each). PETSc has more specialized preconditioners to expose parallelism or to reuse intermediate results in these cases. $\endgroup$ – Jed Brown Feb 23 '14 at 19:42
1
$\begingroup$

In addition to Jed's excellent answer, a method I've found recently is to switch between the preconditioners every other step in flexible GMRES (FGMRES), as is done, for example, in

Tezduyar, T. E., et al. "A new mixed preconditioning method for finite element computations." Computer Methods in Applied Mechanics and Engineering 99.1 (1992): 27-42. http://repository.ias.ac.in/24680/1/320.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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