
CivilComp Proceedings ISSN 17593433
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
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", CivilComp 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 userspecified
fillin 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 fillin
(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 fillin degree has a different meaning:
in SAADILUT lfil_{1} denotes the maximum allowable number of nonzero
elements for each row of the incomplete factors excluding
the diagonal elements; in SYMILUT lfil_{2} 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 CuthillMcKee
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 submatrices"
pointing downward, thus yielding less fillin 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 cablestayed
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;
 Choleskibased symmetric preconditioners provide the best overall
performance with matrices reordered with METIS;
 the direct solver MA57 outperforms the best PCG by a factor 34
and is more robust as it does not require the selection of any
empirical parameter such as the most appropriate degree of fillin
in the preconditioner calculation.
References
 1
 Bathe, K. L. (1996). Finite Element Procedures. PretinceHall. 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, 387402. doi:10.1002/nla.1680010405
 5
 Saad, Y. (1990). SPARSKIT: A basic tool kit for sparse matrix computations. Technical Report 9020, 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 fillreducing 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 highperformance computers. SIAM, Philadelphia, PA.
purchase the fulltext 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
