Geodesic
Renumbering strategies based on multi-level techniques combined with ILU-decompositions
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 37 (1997) no. 11, pp. 1294-1300 
E. F. F. Botta; A. van der Ploeg. Renumbering strategies based on multi-level techniques combined with ILU-decompositions. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 37 (1997) no. 11, pp. 1294-1300. http://geodesic.mathdoc.fr/item/ZVMMF_1997_37_11_a1/
@article{ZVMMF_1997_37_11_a1,
     author = {E. F. F. Botta and A. van der Ploeg},
     title = {Renumbering strategies based on multi-level techniques combined with {ILU-decompositions}},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1294--1300},
     year = {1997},
     volume = {37},
     number = {11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_1997_37_11_a1/}
}
TY  - JOUR
AU  - E. F. F. Botta
AU  - A. van der Ploeg
TI  - Renumbering strategies based on multi-level techniques combined with ILU-decompositions
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 1997
SP  - 1294
EP  - 1300
VL  - 37
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_1997_37_11_a1/
LA  - en
ID  - ZVMMF_1997_37_11_a1
ER  - 
%0 Journal Article
%A E. F. F. Botta
%A A. van der Ploeg
%T Renumbering strategies based on multi-level techniques combined with ILU-decompositions
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 1997
%P 1294-1300
%V 37
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_1997_37_11_a1/
%G en
%F ZVMMF_1997_37_11_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we present an incomplete factorization technique which uses a renumbering of the unknowns, based on a sequence of grids as in multi-grid. For many problems discretised on structured grids, we obtain almost grid-independent convergence when this factorization is combined with some conjugate gradient-like method. Also, a similar preconditioning technique is described which can be used for matrices with arbitrary sparsity patterns as those arising from finite element methods on unstructured grids. During the factorization we use a reordering to guarantee that the diagonal blocks to be inverted remain strongly diagonally dominant. This makes it possible to approximate the needed inverses by only a diagonal matrix, leading to more potential parallelism. The method is demonstrated for a number of test problems and compared to some standard methods.

[1] Axelsson O., Eijkhout V., “The nested recursive two-level factorization method for nine-point difference matrices”, SIAM J. Sci. Statist. Comput., 12 (1991), 1373–1400 | DOI | MR | Zbl

[2] Botta E. F. F., Wubs F. W., “The covergence behaviour of iterative methods on severely stretched grids”, Intemat. J. Numer. Methods in Engng., 36 (1993), 3333–3350 | DOI | MR | Zbl

[3] Brand Cl. W., “An incomplete-factorization preconditioning using red-black ordering”, Numer. Math., 61 (1992), 433–454 | DOI | MR | Zbl

[4] Eisenstat S. C., “Efficient implementation of a class of preconditioned conjugate gradient methods”, SIAM J. Sci. Statist. Comput., 2 (1981), 1–4 | DOI | MR | Zbl

[5] Gustafsson I., “A class of 1: st order factorization methods”, BIT, 18 (1978), 142–156 | DOI | MR | Zbl

[6] Reusken A., Multigrid with matrix-dependent transfer operators for convection-diffusion problems, Techn. Rept RANA 93-10, Dept. Math. and Comput. Sci., Eindhoven Univ. Technol., 1993 | MR

[7] Saad Y., ILUM: A multi-elimination ILU preconditioner for general sparse matrices, Techn. Rept TR 94-57, Univ. Minnesota Comput. Sci. Dept., dec, 1994

[8] van der Ploeg A., “Preconditioning techniques for non-symmetric matrices with application to temperature calculation of cooled concrete”, Intemat. J. Numer. Methods in Engng., 35:6 (1992), 1311–1328 | DOI | MR

[9] van der Ploeg A., Preconditioning for sparse matrices with applications, PhD thesis, Univ. Groningen, 1994

[10] van der Sluis A., van der Vorst H. A., “The rate of convergence of conjugate gradients”, Numer. Math., 48 (1986), 543–560 | DOI | MR | Zbl

[11] van der Vorst H. A., “Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems”, SIAM J. Sci. Statist. Comput., 13:2 (1992), 631–644 | DOI | MR | Zbl