Computational Technology Resources - CCP

Keywords: reordering, Krylov, preconditioning, conjugate gradient.

Summary

It is well known that the outcome of the finite element method in linear elastic structural problems is a linear system with the system matrix both symmetric and positive definite (SPD) [1,2]. In the present paper, the influence of matrix reordering on convergence of the preconditioned conjugate gradient (PCG) is addressed. The two preconditioners used herein are a variant of the incomplete Cholesky factorization with an user-specified fill-in degree [3]:

the former is a variant of the ILUT preconditioner [4,3] (here denoted as SAADILUT), which is commonly used for nonsymmetric problems and firstly converts matrix from the symmetric sparse row (SSR) to the compressed sparse row (CSR) format;
the latter is an incomplete factorization with a variable fill-in (denoted as SYMILUT) that is implemented so as to take the maximum advantage from the matrix symmetry and not to require the format conversion from SSR to CSR.

Within the two implementations the fill-in degree has a different meaning: in SAADILUT lfil₁ denotes the maximum allowable number of nonzero elements for each row of the incomplete factors excluding the diagonal elements; in SYMILUT lfil₂ represents the maximum allowable number of nonzero elements for each row of the factors excluding all the original nonzero elements.

As mentioned above our focus is on linear systems arising from the spatial discretization of linear elastic civil structures obtained by coupling different elements such as beams, trusses, and shells. The ordering schemes addressed are:

SPARSKIT based on the Cuthill-McKee algorithm [5,3];
METIS based on the multilevel nested dissection algorithm [6].

Both these reordering schemes were originally developed and implemented for matrix factorization. They basically act by reducing the matrix bandwidth, leading to a matrix structure consisting of little "arrow sub-matrices" pointing downward, thus yielding less fill-in in the Gaussian elimination. The best PCG performance is finally compared with a direct solver as is implemented in the MA57 routine of the Harwell Software library [7,8]. Numerical experiments are performed on a realistic cable-stayed bridge recently built in Porto Maghera near Venice. The main results are summarized below:

when far nodes are connected, the native unknowns ordering yields SPD matrices which may not be suitable for the solution by PCG methods due to the poor preconditioner quality;
Choleski-based symmetric preconditioners provide the best overall performance with matrices reordered with METIS;
the direct solver MA57 outperforms the best PCG by a factor 3-4 and is more robust as it does not require the selection of any empirical parameter such as the most appropriate degree of fill-in in the preconditioner calculation.

References

1: Bathe, K. L. (1996). Finite Element Procedures. Pretince-Hall. 1037 pp.
2: Zienkiewicz, O. C. and Taylor, R. L. (2000). The Finite Element Method. 1: The basis, volume 1.
Butterworth and Heneimann, 5th edition. 689 pp.
3: Saad, Y. (2003). Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, PA.
4: Saad Y. (1994). ILUT: A dual threshold incomplete ILU factorization. Num. Lin. Alg. Appl., 1, 387-402. doi:10.1002/nla.1680010405
5: Saad, Y. (1990). SPARSKIT: A basic tool kit for sparse matrix computations. Technical Report 90-20, NASA Ames Research Center, Moffett Field, CA, Moffett Field, CA.
6: Karypis, G. and Kumar, V. (1998). METIS. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4.0. University of Minnesota, Department of computer science / Army HPC research center, Minneapolis, MN 55455.
7: HSL Archive - a catalogue of subroutines. (2004). Aea Technology, Engineering Software, CCLRC. http://www.cse.clrc.ac.uk/nag/hsl.
8: Dongarra, J. J., Duff, I. S., Sorensen, D. C. and van der Vorst H. A. (1998). Numerical linear algebra for high-performance computers. SIAM, Philadelphia, PA.

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 £140 +P&P)

	Computational & Technology Resources an online resource for computational, engineering & technology publications
	not logged in - login
Front Page Browse CCP CSETS CTR IJRT Other Authors Search Purchase Guide FAQ Contact us	Civil-Comp Proceedings ISSN 1759-3433 CCP: 83 PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL STRUCTURES TECHNOLOGY Edited by: B.H.V. Topping, G. Montero and R. Montenegro Paper 175 Reordering for the Iterative Solution of Hybrid Elastic Structures A. Comerlati, G. Gambolati and C. Janna Department of Mathematical Methods and Models for Scientific Applications (DMMMSA), University of Padova, Italy doi:10.4203/ccp.83.175 purchase the full-text of this paper Full Bibliographic Reference for this paper A. Comerlati, G. Gambolati, C. Janna, "Reordering for the Iterative Solution of Hybrid Elastic Structures", in B.H.V. Topping, G. Montero, R. Montenegro, (Editors), "Proceedings of the Eighth International Conference on Computational Structures Technology", Civil-Comp Press, Stirlingshire, UK, Paper 175, 2006. doi:10.4203/ccp.83.175 Keywords: reordering, Krylov, preconditioning, conjugate gradient. Summary It is well known that the outcome of the finite element method in linear elastic structural problems is a linear system with the system matrix both symmetric and positive definite (SPD) [1,2]. In the present paper, the influence of matrix reordering on convergence of the preconditioned conjugate gradient (PCG) is addressed. The two preconditioners used herein are a variant of the incomplete Cholesky factorization with an user-specified fill-in degree [3]: the former is a variant of the ILUT preconditioner [4,3] (here denoted as SAADILUT), which is commonly used for nonsymmetric problems and firstly converts matrix from the symmetric sparse row (SSR) to the compressed sparse row (CSR) format; the latter is an incomplete factorization with a variable fill-in (denoted as SYMILUT) that is implemented so as to take the maximum advantage from the matrix symmetry and not to require the format conversion from SSR to CSR. Within the two implementations the fill-in degree has a different meaning: in SAADILUT lfil₁ denotes the maximum allowable number of nonzero elements for each row of the incomplete factors excluding the diagonal elements; in SYMILUT lfil₂ represents the maximum allowable number of nonzero elements for each row of the factors excluding all the original nonzero elements. As mentioned above our focus is on linear systems arising from the spatial discretization of linear elastic civil structures obtained by coupling different elements such as beams, trusses, and shells. The ordering schemes addressed are: SPARSKIT based on the Cuthill-McKee algorithm [5,3]; METIS based on the multilevel nested dissection algorithm [6]. Both these reordering schemes were originally developed and implemented for matrix factorization. They basically act by reducing the matrix bandwidth, leading to a matrix structure consisting of little "arrow sub-matrices" pointing downward, thus yielding less fill-in in the Gaussian elimination. The best PCG performance is finally compared with a direct solver as is implemented in the MA57 routine of the Harwell Software library [7,8]. Numerical experiments are performed on a realistic cable-stayed bridge recently built in Porto Maghera near Venice. The main results are summarized below: when far nodes are connected, the native unknowns ordering yields SPD matrices which may not be suitable for the solution by PCG methods due to the poor preconditioner quality; Choleski-based symmetric preconditioners provide the best overall performance with matrices reordered with METIS; the direct solver MA57 outperforms the best PCG by a factor 3-4 and is more robust as it does not require the selection of any empirical parameter such as the most appropriate degree of fill-in in the preconditioner calculation. References 1 Bathe, K. L. (1996). Finite Element Procedures. Pretince-Hall. 1037 pp. 2 Zienkiewicz, O. C. and Taylor, R. L. (2000). The Finite Element Method. 1: The basis, volume 1. Butterworth and Heneimann, 5th edition. 689 pp. 3 Saad, Y. (2003). Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, PA. 4 Saad Y. (1994). ILUT: A dual threshold incomplete ILU factorization. Num. Lin. Alg. Appl., 1, 387-402. doi:10.1002/nla.1680010405 5 Saad, Y. (1990). SPARSKIT: A basic tool kit for sparse matrix computations. Technical Report 90-20, NASA Ames Research Center, Moffett Field, CA, Moffett Field, CA. 6 Karypis, G. and Kumar, V. (1998). METIS. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4.0. University of Minnesota, Department of computer science / Army HPC research center, Minneapolis, MN 55455. 7 HSL Archive - a catalogue of subroutines. (2004). Aea Technology, Engineering Software, CCLRC. http://www.cse.clrc.ac.uk/nag/hsl. 8 Dongarra, J. J., Duff, I. S., Sorensen, D. C. and van der Vorst H. A. (1998). Numerical linear algebra for high-performance computers. SIAM, Philadelphia, PA. 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 £140 +P&P)
Back to top	©Civil-Comp Limited 2023 - terms & conditions