Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 11, 2003 | Published
Journal Article Open

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

Abstract

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.

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. The authors thank R. Bank and P. Vassilevski for many enlightening discussion

Attached Files

Published - AKSsiamjsc03.pdf

Files

AKSsiamjsc03.pdf
Files (265.8 kB)
Name Size Download all
md5:3a6a63d88a39a586dec3946b7cec4bf5
265.8 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 13, 2023