Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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".

share|improve this answer
    
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? –  Nick Alger Feb 23 at 17:30
    
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. –  Jed Brown Feb 23 at 19:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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