Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 84
PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping, G. Montero and R. Montenegro
Paper 86

Incomplete Factorization for Preconditioning Shifted Linear Systems

H. Sarmiento, A. Suárez and G. Montero

University Institute of Intelligent Systems and Numerical Applications in Engineering (IUSIANI), University of Las Palmas de Gran Canaria, Spain

Full Bibliographic Reference for this paper
, "Incomplete Factorization for Preconditioning Shifted Linear Systems", in B.H.V. Topping, G. Montero, R. Montenegro, (Editors), "Proceedings of the Fifth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 86, 2006. doi:10.4203/ccp.84.86
Keywords: incomplete Cholesky factorization, shifted linear systems, preconditioning, conjugate gradient, iterative methods, wind modelling.

Summary
The resolution of several problems of science and engineering, such as parabolic partial differential equations, mass consistent models for wind field adjustment [1,2], with any discretization technique, yields linear systems of equations of the form,

(72)

where M and N are constant for a given discretization. In these problems, the system (72) must be solved for different values of .
Iterative solvers based on Krylov subspaces are the most efficient methods for such large and sparse linear systems [3]. In our case, since M and N are symmetric positive definite matrices, the Conjugate Gradient (CG) provides the best results. In addition, the use of suitable preconditioning techniques [4] allows a faster convergence of the CG.

For preconditioning these systems, we can build a different preconditioner for each value of . In general, this means good convergence behaviour is obtained but at a high computational cost related to each preconditioner. On the contrary, we can use a unique preconditioner, the first of the above list, for solving all the linear systems. However, this second strategy may lead to convergences as slow as the value of is far from the initial value chosen for building the preconditioner.

In this work, an intermediate procedure is proposed. It consists of a preconditioner based on an incomplete Cholesky factorization that may be updated for each new system at a low computational cost. Thus, it provides better convergence than the latter strategy and is cheaper that the former. In a similar way, Meurant [5] proposes this preconditioner for the special case , with D being a diagonal matrix. In addition, Benzi [6] develops a preconditioner, based on a factorized approximate inverse [7], for shifted linear systems of the form , with I being the unit matrix. In a recent work, Montero et al. [8] developed a generalization of this Benzi's algorithm for equation (72). All of these preconditioners may be updated as a function of .

Several numerical experiments are presented in order to show the efficiency of the proposed preconditioner.

References
1
G. Montero, R. Montenegro, J.M. Escobar, `A 3-D diagnostic model for wind field adjustment', J. Wind Eng. Ind. Aer.,74-76, 249-261, 1998. doi:10.1016/S0167-6105(98)00022-1
2
G. Montero, E. Rodríguez, R. Montenegro, J.M. Escobar, J.M. González- Yuste, `Genetic algorithms for an improved parameter estimation with local refinement of tetrahedral meshes in a wind model', Adv. Engng. Soft., 36, 3-10, 2005. doi:10.1016/j.advengsoft.2004.03.011
3
Y.Saad, `Iterative methods for sparse linear systems', PWE Publishing Company. Boston, 1996.
4
M. Benzi, `Preconditioning techniques for large linear systems: a survey', J. Comput Physics, 182, 418-477, 2002. doi:10.1006/jcph.2002.7176
5
G. Meurant, `On the incomplete Cholesky decomposition of a class of perturbed matrices', SIAM J. Sci. Comput., 23(2), 419-429, 2001. doi:10.1137/S1064827500371244
6
M. Benzi and D. Bertaccini, `Approximate inverse preconditioning for shifted linear systems', BIT Num. Math., 43, 231-244, 2003. doi:10.1023/A:1026089811044
7
M. Benzi, J.K. Cullum and M. T·ma,`Robust approximate inverse preconditioning for the conjugate gradient method', SIAM J. Sci. Comput., 22, 1318-1332, 2000. doi:10.1137/S1064827599356900
8
G. Montero, A. Suárez, E. Rodríguez, E. Flórez, M.D. García, `Preconditioning shifted linear systems arising in a wind model', in B.H.V. Topping ed., Proceedings of the Tenth International Conference on Civil, Structural and Environmental Engineering Computing, Roma, 2005. doi:10.4203/ccp.81.87

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)