Citation
Grinspun, Eitan (2003) The basis refinement method. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd05312003133558
Abstract
Finite element solvers are critical in computer graphics, engineering, medical and biological application areas. For large problems, the use of adaptive refinement methods can tame otherwise intractable computational costs. Current formulations of adaptive finite element mesh refinement seem straightforward, but their implementations prove to be a formidable task. We offer an alternative point of departure which yields equivalent adapted approximation spaces wherever the traditional mesh refinement is applicable, but proves to be significantly simpler to implement. At the same time it is much more powerful in that it is general (no special tricks are required for different types of finite elements), and applicable to novel discretizations where traditional mesh refinement concepts are not of much help, for instance on subdivision surfaces.
For classical finiteelements, adaptive refinement is typically carried out by splitting mesh elements in isolation. While socalled mesh refinement is wellunderstood, it is considered cumbersome to implement for unstructured threedimensional meshes, among other settings, in particular because mesh compatibility must be explicitly maintained. Furthermore, elementsplitting does not apply to problems that benefit from higherorder Bspline discretizations and their more general counterparts, socalled subdivision elements. We introduce a simple, general method for adaptive refinement which applies uniformly in all these settings and others. The basic principle of our approach is to refine basis functions, not elements. Our method is naturally compatible: unlike mesh refinement, basis refinement never creates incompatible meshes. Our contributions are (a) a minimal mathematical framework, with (b) associated algorithms for basis refinement; furthermore, we (c) describe the mapping of popular methods (finiteelements, wavelets, splines and subdivision) onto this framework, and (d) demonstrate working implementations of basis refinement with applications in graphics, engineering, and medicine.
Our approach is based on compactly supported refinable functions. We refine by augmenting the basis with narrowlysupported functions, not by splitting mesh elements in isolation. This removes a number of implementation headaches associated with elementsplitting and is a general technique independent of domain dimension, element type (eg, triangle, quad, tetrahedron, hexahedron), and basis function order (piecewise linear, quadratic, cubic, etc.). The (un)refinement algorithms are simple and require little in terms of data structure support. Many popular discretizations, including classical finiteelements, wavelets and multiwavelets, splines and subdivision schemes may be viewed as refinable function spaces, thus they are encompassed by our approach.
Our first contribution is the specification of a minimal mathematical framework, at its heart a sequence of nested approximation spaces. By construction, the bases for these spaces consist of refinable functions. From an approximation theory point of view this is a rather trivial statement; however it has a number of very important and highly practical consequences. Our adaptive solver framework requires only that the basis functions used be refinable. It makes no assumptions as to (a) the dimension of the domain; (b) the tesselation of the domain, i.e., the domain elements be they triangles, quadrilaterals, tetrahedra, hexahedra, or more general domains; (c) the approximation smoothness or accuracy; and (d) the support diameter of the basis functions. The specification of the nested spaces structure is sufficiently weak to accomodate many practical settings, while strong enough to satisfy the necessary conditions of our theorems and algorithms.
Our second contribution is to show that basis refinement can be implemented by a small set of simple algorithms. Our method requires efficient data structures and algorithms to (a) keep track of interactions between basis functions (i.e., to find the nonzero entries in the stiffness matrix), and (b) manage a tesselation of the domain suitable for evaluation of the associated integrals (i.e., to evaluate the entries of the stiffness matrix). We provide a specification for these requirements, develop the relevant theorems and proofs, and invoke these theorems to produce concrete, provablycorrect pseudocode. The resulting algorithms, while capturing the full generality (in dimension, tesselation, smoothness, etc.) of our method, are surprisingly simple.
Our third contribution is the mapping of finiteelements, wavelets and multiwavelets, splines and subdivision schemes onto our nested spaces framework. No single discretization fits all applications. In our survey of classical and recentlypopularized discretizations we demonstrate that our unifying algorithms for basis refinement encompass a very broad range of problems.
Our fourth contribution is a set of concrete, compelling examples based on our implementation of basis refinement. Adaptive basis refinement may be profitably applied in solving partial differential equations (PDEs) useful in many application domains, including simulation, animation, modeling, rendering, surgery, biomechanics, and computer vision. Our examples span thin shells (fourth order elliptic PDE using a Loop subdivision discretization), volume deformation and stress analysis using linear elasticity (second order PDE using lineartetrahedral and trilinearhexahedral finite elements respectively) and a subproblem of electrocardiography (the generalized Laplace equation using linear tetrahedral finite elements).
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  adaptive computation; adaptivity; animation; basis functions; compatibility; computer graphics; conforming elements; efficiency; finite elements; Loop; medical simulations; numerical solvers; performance; refinement; simulation; splines; subdivision; thin shells 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Computer Science 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  16 May 2003 
NonCaltech Author Email:  eitan (AT) cs.caltech.edu 
Record Number:  CaltechETD:etd05312003133558 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd05312003133558 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  2324 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  04 Jun 2003 
Last Modified:  26 Dec 2012 02:50 
Thesis Files

PDF (thesis.pdf)
 Final Version
See Usage Policy. 10Mb  

PDF (vitae.pdf)
 Final Version
See Usage Policy. 44Kb 
Repository Staff Only: item control page