A Caltech Library Service

An odyssey into local refinement and multilevel preconditioning III: Implementation and numerical experiments

Aksoylu, Burak and Bond, Stephen and Holst, Michael (2003) An odyssey into local refinement and multilevel preconditioning III: Implementation and numerical experiments. SIAM Journal on Scientific Computing, 25 (2). pp. 478-498. ISSN 1064-8275.

See Usage Policy.


Use this Persistent URL to link to this item:


In this paper, we examine a number of additive and multiplicative multilevel iterative methods and preconditioners in the setting of two-dimensional local mesh refinement. While standard multilevel methods are effective for uniform refinement-based discretizations of elliptic equations, they tend to be less effective for algebraic systems, which arise from discretizations on locally refined meshes, losing their optimal behavior in both storage and computational complexity. Our primary focus here is on Bramble, Pasciak, and Xu (BPX)-style additive and multiplicative multilevel preconditioners, and on various stabilizations of the additive and multiplicative hierarchical basis (HB) method, and their use in the local mesh refinement setting. In parts I and II of this trilogy, it was shown that both BPX and wavelet stabilizations of HB have uniformly bounded condition numbers on several classes of locally refined two- and three-dimensional meshes based on fairly standard (and easily implementable) red and red-green mesh refinement algorithms. In this third part of the trilogy, we describe in detail the implementation of these types of algorithms, including detailed discussions of the data structures and traversal algorithms we employ for obtaining optimal storage and computational complexity in our implementations. We show how each of the algorithms can be implemented using standard data types, available in languages such as C and FORTRAN, so that the resulting algorithms have optimal (linear) storage requirements, and so that the resulting multilevel method or preconditioner can be applied with optimal (linear) computational costs. We have successfully used these data structure ideas for both MATLAB and C implementations using the FEtk, an open source finite element software package. We finish the paper with a sequence of numerical experiments illustrating the effectiveness of a number of BPX and stabilized HB variants for several examples requiring local refinement.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2003 Society for Industrial and Applied Mathematics. Received by the editors May 15, 2002; accepted for publication (in revised form) February 26, 2003; published electronically November 11, 2003. The first author was supported in part by the Burroughs Wellcome Fund through the LJIS predoctoral training program at the University of California at San Diego, in part by NSF grants ACI-9721349 and DMS-9872890, and in part by DOE grant W-7405-ENG-48/B341492. Other support was provided by Intel, Microsoft, Alias|Wavefront, Pixar, and the Packard Foundation. The second author was supported in part by the Howard Hughes Medical Institute, and in part by NSF and NIH grants to J. A. McCammon. The third author was supported in part by NSF CAREER Award 9875856 and in part by a UCSD Hellman Fellowship.
Subject Keywords:finite element methods, local mesh refinement, multilevel preconditioning, BPX, red and red-green refinement, 2D and 3D, data structures
Issue or Number:2
Record Number:CaltechAUTHORS:AKSsiamjsc03
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:550
Deposited By: Tony Diaz
Deposited On:18 Aug 2005
Last Modified:02 Oct 2019 22:34

Repository Staff Only: item control page