ISSN:
1572-9125
Keywords:
65F10
;
15A06
;
65F90
;
65K10
;
Conjugate gradient method
;
preconditioning
;
incomplete factorization
;
polynomial preconditioner
;
matrix-free method
;
Fourier analysis
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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 [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01955867
Permalink