The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Étant donné un système linéaire clairsemé, A x = b, on peut résoudre le système équivalent BOUILLIET y = P b, x = PT y, Où P est une matrice de permutation. On sait que, par exemple, lorsque P est la permutation d'ordre RCMK (Reverse Cuthill-Mckee), le taux de convergence de la méthode du sous-espace de Krylov combinée au préconditionneur de type ILU est souvent amélioré, surtout si la matrice A est fortement asymétrique. Dans cet article, nous proposons une heuristique de réorganisation pour accélérer la solution de grands systèmes linéaires clairsemés par les méthodes du sous-espace de Krylov avec le préconditionneur ILUT. C'est le LRB (Ligne Rouge/Noir) commande basée sur la commande bien connue Rouge-Noir à 2 points. Nous montrons que pour certaines PDE (équations aux dérivées partielles) de type modèle, les matrices de discrétisation ordonnées LRB FDM (Finite Difference Method)/FEM (Finite Element Method) nécessitent beaucoup moins de remplissages dans les factorisations ILUT que celles de l'ordre naturel et la commande RCMK et produit donc un préconditionneur plus précis, si un niveau élevé de remplissage est utilisé. Cela implique que l'ordre LRB pourrait surpasser les deux autres ordres combinés avec la méthode du sous-espace de Krylov préconditionné ILUT si le niveau de remplissage est suffisamment élevé. Nous comparons les performances de notre heuristique avec celles du tri RCMK (Reverse Cuthill-McKee). Nos matrices de tests sont obtenues à partir de diverses discrétisations standards d'EDP de type modèle bidimensionnelles et tridimensionnelles sur des grilles structurées par le FDM ou le FEM. Nous affirmons que pour les matrices résultantes, les performances de notre stratégie de réordonnancement pour la méthode du sous-espace de Krylov combinée avec le préconditionneur ILUT sont supérieures à celles de l'ordonnancement RCMK, lorsque le nombre approprié de remplissages a été utilisé pour l'ILUT. De plus, alors que l’on sait que l’ordre RCMK a peu d’avantages par rapport à l’ordre naturel dans le cas de matrices symétriques, l’ordre LRB peut encore améliorer le taux de convergence, même si les matrices sont symétriques.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Sangback MA, "A Reordering Heuristic for Accelerating the Convergence of the Solution of Some Large Sparse PDE Matrices on Structured Grids by the Krylov Subspace Methods with the ILUT Preconditioner" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 5, pp. 1322-1330, May 2009, doi: 10.1587/transfun.E92.A.1322.
Abstract: Given a sparse linear system, A x = b, we can solve the equivalent system P A PT y = P b, x = PT y, where P is a permutation matrix. It has been known that, for example, when P is the RCMK (Reverse Cuthill-Mckee) ordering permutation, the convergence rate of the Krylov subspace method combined with the ILU-type preconditioner is often enhanced, especially if the matrix A is highly nonsymmetric. In this paper we offer a reordering heuristic for accelerating the solution of large sparse linear systems by the Krylov subspace methods with the ILUT preconditioner. It is the LRB (Line Red/Black) ordering based on the well-known 2-point Red-Black ordering. We show that for some model-like PDE (partial differential equation)s the LRB ordered FDM (Finite Difference Method)/FEM (Finite Element Method) discretization matrices require much less fill-ins in the ILUT factorizations than those of the Natural ordering and the RCMK ordering and hence, produces a more accurate preconditioner, if a high level of fill-in is used. It implies that the LRB ordering could outperform the other two orderings combined with the ILUT preconditioned Krylov subspace method if the level of fill-in is high enough. We compare the performance of our heuristic with that of the RCMK (Reverse Cuthill-McKee) ordering. Our test matrices are obtained from various standard discretizations of two-dimensional and three-dimensional model-like PDEs on structured grids by the FDM or the FEM. We claim that for the resulting matrices the performance of our reordering strategy for the Krylov subspace method combined with the ILUT preconditioner is superior to that of RCMK ordering, when the proper number of fill-in was used for the ILUT. Also, while the RCMK ordering is known to have little advantage over the Natural ordering in the case of symmetric matrices, the LRB ordering still can improve the convergence rate, even if the matrices are symmetric.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1322/_p
Copier
@ARTICLE{e92-a_5_1322,
author={Sangback MA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Reordering Heuristic for Accelerating the Convergence of the Solution of Some Large Sparse PDE Matrices on Structured Grids by the Krylov Subspace Methods with the ILUT Preconditioner},
year={2009},
volume={E92-A},
number={5},
pages={1322-1330},
abstract={Given a sparse linear system, A x = b, we can solve the equivalent system P A PT y = P b, x = PT y, where P is a permutation matrix. It has been known that, for example, when P is the RCMK (Reverse Cuthill-Mckee) ordering permutation, the convergence rate of the Krylov subspace method combined with the ILU-type preconditioner is often enhanced, especially if the matrix A is highly nonsymmetric. In this paper we offer a reordering heuristic for accelerating the solution of large sparse linear systems by the Krylov subspace methods with the ILUT preconditioner. It is the LRB (Line Red/Black) ordering based on the well-known 2-point Red-Black ordering. We show that for some model-like PDE (partial differential equation)s the LRB ordered FDM (Finite Difference Method)/FEM (Finite Element Method) discretization matrices require much less fill-ins in the ILUT factorizations than those of the Natural ordering and the RCMK ordering and hence, produces a more accurate preconditioner, if a high level of fill-in is used. It implies that the LRB ordering could outperform the other two orderings combined with the ILUT preconditioned Krylov subspace method if the level of fill-in is high enough. We compare the performance of our heuristic with that of the RCMK (Reverse Cuthill-McKee) ordering. Our test matrices are obtained from various standard discretizations of two-dimensional and three-dimensional model-like PDEs on structured grids by the FDM or the FEM. We claim that for the resulting matrices the performance of our reordering strategy for the Krylov subspace method combined with the ILUT preconditioner is superior to that of RCMK ordering, when the proper number of fill-in was used for the ILUT. Also, while the RCMK ordering is known to have little advantage over the Natural ordering in the case of symmetric matrices, the LRB ordering still can improve the convergence rate, even if the matrices are symmetric.},
keywords={},
doi={10.1587/transfun.E92.A.1322},
ISSN={1745-1337},
month={May},}
Copier
TY - JOUR
TI - A Reordering Heuristic for Accelerating the Convergence of the Solution of Some Large Sparse PDE Matrices on Structured Grids by the Krylov Subspace Methods with the ILUT Preconditioner
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1322
EP - 1330
AU - Sangback MA
PY - 2009
DO - 10.1587/transfun.E92.A.1322
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2009
AB - Given a sparse linear system, A x = b, we can solve the equivalent system P A PT y = P b, x = PT y, where P is a permutation matrix. It has been known that, for example, when P is the RCMK (Reverse Cuthill-Mckee) ordering permutation, the convergence rate of the Krylov subspace method combined with the ILU-type preconditioner is often enhanced, especially if the matrix A is highly nonsymmetric. In this paper we offer a reordering heuristic for accelerating the solution of large sparse linear systems by the Krylov subspace methods with the ILUT preconditioner. It is the LRB (Line Red/Black) ordering based on the well-known 2-point Red-Black ordering. We show that for some model-like PDE (partial differential equation)s the LRB ordered FDM (Finite Difference Method)/FEM (Finite Element Method) discretization matrices require much less fill-ins in the ILUT factorizations than those of the Natural ordering and the RCMK ordering and hence, produces a more accurate preconditioner, if a high level of fill-in is used. It implies that the LRB ordering could outperform the other two orderings combined with the ILUT preconditioned Krylov subspace method if the level of fill-in is high enough. We compare the performance of our heuristic with that of the RCMK (Reverse Cuthill-McKee) ordering. Our test matrices are obtained from various standard discretizations of two-dimensional and three-dimensional model-like PDEs on structured grids by the FDM or the FEM. We claim that for the resulting matrices the performance of our reordering strategy for the Krylov subspace method combined with the ILUT preconditioner is superior to that of RCMK ordering, when the proper number of fill-in was used for the ILUT. Also, while the RCMK ordering is known to have little advantage over the Natural ordering in the case of symmetric matrices, the LRB ordering still can improve the convergence rate, even if the matrices are symmetric.
ER -