Keywords: incomplete factorization, approximate inverses, shifted linear systems, preconditioning, conjugate gradient, ordering.

The application of discretization techniques to problems defined by partial differential equations which model physical phenomena, sometimes leads to linear systems of equations of which the matrix is given as a function of a parameter,

This is especially true in the numerical simulation of wind fields with mass consistent models [1]. Here we consider that M and N are constant for each level of discretization, positive definite and symmetric. It is well known that the preconditioned conjugate gradient algorithm (PCG) provides the best convergence results in the resolution of these type of linear systems. Each value of yields a different linear systems. So we could either construct a different preconditioner for each one of them and improve the convergence of the PCG at the expense of a high computational cost related to the construction of each preconditioner, or use a single preconditioner constructed with a given value of for all the systems. In this latter case the convergence will get worse as the value of the parameter moves away from the initial value.

Benzi [2] and Meurant [3] propose an intermediate solution by using two type of preconditioner, respectively, which are constructed once at first and updated for each at a low computational cost. These strategies also lead to an intermediate rate of convergence between the above extreme options. Benzi develops the factorised approximate inverses using the SAINV algorithm [4] for the special case of , with I being the unit matrix. However Meurant considers with D being a diagonal matrix, constructing the preconditioner from an incomplete Cholesky factorisation of M. In this work, we generalize both algorithms to the case of , with M and N SPD matrices.

On the other hand, many authors have shown the effect of ordering on the convergence of preconditioned Krylov subspace algorithms, and in particular on the convergence of the PCG for symmetric problems. We propose the study of this effect when we are solving systems of the matrix using the preconditioners proposed in [5,6] that are based on the works of Benzi and Meurant. Reordering techniques try to avoid the fill-in, as well as reducing the profile of the matrix. The former preconditioners are built considering only a small number of upper diagonals in the matrix N and in the upper triangular matrix resulting in the SAINV factorisation of , and thus the approximation will be better as the profile is reduced. In addition, the latter preconditioners will be improved if the fill-in effect is lower after reordering.

Several numerical experiments are presented in order to show the reduction of computational cost and the number of iterations of the preconditioned conjugate gradient method when some standard ordering schemes are applied. Here we apply the reverse Cuthill-Mckee [7], minimum neighbouring [8] and multicoloring [9] reordering algorithms. In order to start these algorithms and find the pseudo-peripheral node, we use George's algorithm [8].

1

G. Montero, E. Rodríguez, R. Montenegro, J.M. Escobar, J.M. González- Yuste, "Genetic algorithms for an improved parameter estimation with local refinenent of tetrahedral meshes in a wind model", Adv. Engng. Soft., 36, 3-10, 2005. doi:10.1016/j.advengsoft.2004.03.011

2

M. Benzi and D. Bertaccini, "Approximate inverse preconditioning for shifted linear systems", BIT Num. Math., 43, 231-244, 2003. doi:10.1023/A:1026089811044

3

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

4

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

5

G. Montero, A. Suárez, E. Flórez and M.D. García, "Preconditioning shifter linear sistems arising in a win model", in proceedings of The Tenth Intern. Conf. on Civil, Structural and Environmental Engineering Computing, Roma, 2005. doi:10.4203/ccp.81.87

6

H. Sarmiento, A. Suárez and G. Montero"Incomplete Factorization for Preconditioning Shifted Linear Systems", submitted to The Fifth International Conference on Engineering Computational Techonology, Las Palmas G.C., 2006. doi:10.4203/ccp.84.86

7

A. George, "Computer Implementation of the Finite Element Method", Report Stan CS-71-208, 1971.

8

A. George and J.W. Liu, "The Evolution of the Minimum Degree Ordering Algorithms", SIAM Rev., 31, 1-19, 1989. doi:10.1137/1031001

9

Y. Saad, "Iterative methods for sparse linear systems", PWE Publishing Company, Boston, 1996.

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)