Steepest descent and conjugate gradient methods with variable preconditioning

Details Steepest descent and conjugate gradient methods with variable preconditioning Steepest descent and conjugate gradient methods with variable preconditioning

2006-05-30

arxiv.org/abs/math/0605767v3

SIAM Journal on Matrix Analysis and Applications, Volume 29 Issue 4, pp. 1267-1280, 2007.

Mathematics

Numerical Analysis

14 pages, 3 figures. Submitted to SIMAX

Scientific paper

10.1137/060675290

We analyze the conjugate gradient (CG) method with variable preconditioning for solving a linear system with a real symmetric positive definite (SPD) matrix of coefficients $A$. We assume that the preconditioner is SPD on each step, and that the condition number of the preconditioned system matrix is bounded above by a constant independent of the step number. We show that the CG method with variable preconditioning under this assumption may not give improvement, compared to the steepest descent (SD) method. We describe the basic theory of CG methods with variable preconditioning with the emphasis on ``worst case' scenarios, and provide complete proofs of all facts not available in the literature. We give a new elegant geometric proof of the SD convergence rate bound. Our numerical experiments, comparing the preconditioned SD and CG methods, not only support and illustrate our theoretical findings, but also reveal two surprising and potentially practically important effects. First, we analyze variable preconditioning in the form of inner-outer iterations. In previous such tests, the unpreconditioned CG inner iterations are applied to an artificial system with some fixed preconditioner as a matrix of coefficients. We test a different scenario, where the unpreconditioned CG inner iterations solve linear systems with the original system matrix $A$. We demonstrate that the CG-SD inner-outer iterations perform as well as the CG-CG inner-outer iterations in these tests. Second, we show that variable preconditioning may surprisingly accelerate the SD and thus the CG convergence. Specifically, we compare the CG methods using a two-grid preconditioning with fixed and randomly chosen coarse grids, and observe that the fixed preconditioner method is twice as slow as the method with random preconditioning.

Affiliated with

Also associated with

No associations

Rating

Steepest descent and conjugate gradient methods with variable preconditioning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Steepest descent and conjugate gradient methods with variable preconditioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Steepest descent and conjugate gradient methods with variable preconditioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467461