Copy

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 P*^{T} y = *P b*, *x* = *P*^{T} 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

Copy

@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 P*^{T} y = *P b*, *x* = *P*^{T} 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},}

Copy

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 P*^{T} y = *P b*, *x* = *P*^{T} 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 -