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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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".

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 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

Improve this answer
$\endgroup$

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.