A numerical study of optimized sparse preconditioners
- A. M. BruasetAffiliated withSINTEF
- , A. TveitoAffiliated withSINTEF
Rent the article at a discountRent now
* Final gross prices may vary according to local VAT.Get Access
Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.
Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson , and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul , have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n 1/4) andO(n 1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.
By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.
AMS subject classification65F10 15A06 65F90 65K10
Key wordsConjugate gradient method preconditioning incomplete factorization polynomial preconditioner matrix-free method Fourier analysis
- A numerical study of optimized sparse preconditioners
BIT Numerical Mathematics
Volume 34, Issue 2 , pp 177-204
- Cover Date
- Print ISSN
- Online ISSN
- Kluwer Academic Publishers
- Additional Links
- Conjugate gradient method
- incomplete factorization
- polynomial preconditioner
- matrix-free method
- Fourier analysis
- Industry Sectors