Modeling, Mesh Generation, and Adaptive Numerical Methods for Partial Differential Equations

This paper provides a basic overview of NURBS and their application to numerical grid generation. Curve/surface smoothing, accelerated grid generation, and the use of NURBS in a practical grid generation system are discussed.

Degeneracy is a serious issue in geometry. In their original form, many geometric algorithms simply assume that there is no degeneracy. As a result, when these methods arc used on data that is degenerate or nearly degenerate, they either fail to complete or else give nonsensical results.

We review three approaches to mesh generation that arc based on analyzing and accounting for the geometric structure of the domain. In the first, approach, due to Armstrong, the domain is partitioned into subdomains based on the medial-axis transform, a tool for analyzing spatial structures. In the second approach, due to Cox, the design history defines a geometric structure of the domain. The design primitives of that structure are meshed separately, and mesh overlap is accounted for by coupling equations. The third approach argues that mesh generation ought to be integrated into the shape design process, by meshing design features separately and resolving overlapping meshes by standard geometric computations.

We consider the problem of refining unstructured quadrilateral and brick element meshes. We present an algorithm which is a generalization of an algorithm developed by Cheng et. al. for structured quadrilateral element meshes. The problem is solved for the two-dimensional case. Concerning three dimensions we present a solution for some special cases and a general solution that introduces tetrahedral and pyramidal transition elements.

Specific issues associated with the automatic generation of finite element meshes for curved geometric domains are considered. A review of the definition of when a triangulation is a valid mesh, a geometric triangulation, for curved geometric domains is given. Consideration is then given to the additional operations necessary to maintain the validity of a mesh when curved finite elements are employed. A procedure to control the mesh gradations based on the curvature of the geometric model faces is also given.

Finite element computations are all the more exact if we start from “good” elements. We are interested in meshes where the elements are tetrahedra and we shall develop utilities allowing us to improve the quality of these meshes.

The swift, improvement of computational capabilities enables us to apply finite element methods to simulate more and more problems arising from various applications. A fundamental question associated with finite element simulations is their accuracy. In other words, before we can make any decisions based on the numerical solutions, we must be sure that they are acceptable in the sense that their errors are within the given tolerances. Various estimators have been developed to assess the accuracy of finite element solutions, and they can be classified basically into two types: a priori error estimates and a posteriori error estimates. While a priori error estimates can give us asymptotic convergence rates of numerical solutions in terms of the grid size before the computations, they depend on certain Sobolev norms of the true solutions which are not known, in general. Therefore, it is difficult, if not impossible, to use a priori estimates directly to decide whether a numerical solution is acceptable or a finer partition (and so a new numerical solution) is needed. In contrast, a posteriori error estimates depends only on the numerical solutions, and they usually give computable quantities about the accuracy of the numerical solutions.

Parabolic equations govern many transient engineering problems. Space integration using finite element or finite difference methods changes the parabolic partial differential equation into an ordinary differential equation. Time integration schemes are needed to solve the later equation. In order to accurately perform the later integration a proper time step must be provided. Time step estimates based on a stability criteria have been prescribed in the literature. The following paper presents time step estimates that satisfy stability as well as accuracy criteria. These estimates were correlated to the Froude and Courant Numbers. The later criteria were found to be overly conservative for some integration schemes. Suggestions as to which time integration scheme is the best to use are also presented.

Domain decomposition methods can perform poorly on advection-diffusion equations if diffusion is dominated by advection. Indeed, the hyperpolic part of the equations could affect the behavior of iterative schemes among subdomains slowing down dramatically their rate of convergence. Taking into account the direction of the characteristic lines we introduce suitable adaptive algorithms which are stable with respect to the magnitude of the convective field in the equations and very effective on linear boundary value problems.

We consider mixed finite element methods for the approximation of linear and quasilinear second-order elliptic problems. A class of postprocessing methods for improving mixed finite element solutions is analyzed. In particular, error estimates in L ^p , 1 ≤ p ≤ ∞, are given. These postprocessing methods are applicable to all the existing mixed methods, and can be easily implemented. Furthermore, they are local and thus fully parallelizable.

The 3D Navier-Stokes equations are solved via the Characteristic-Galerkin method extended to free boundary problems. A temporal discretization procedure is proposed for the case where a preferential direction to move mesh point exists, as in thin domains. Using a single layer of finite element, the numerical results cover the so-called shallow water 2D approximation, showing the same wave propagation speed.

We describe and examine the performance of adaptive methods for solving hyperbolic systems of conservation laws on massively parallel computers. The differential system is approximated by a discontinuous Galerkin finite element method with a hierarchical Legendre piecewise polynomial basis for the spatial discretization. Fluxes at element boundaries are computed by solving an approximate Riemann problem; a projection limiter is applied to keep the average solution monotone; time discretization is performed by Runge-Kutta integration; and a p-refinement-based error estimate is used as an enrichment indicator. Adaptive order (p-) and mesh (h-) refinement algorithms are presented and demonstrated. Using an element-based dynamic load balancing algorithm called tiling and adaptive p-refinement, parallel efficiencies of over 60% are achieved on a 1024-processor nCUBE/2 hypercube. We also demonstrate a fast, tree-based parallel partitioning strategy for three-dimensional octree-structured meshes. This method produces partition quality comparable to recursive spectral bisection at a greatly reduced cost.

A multi-grid method for a periodic heterogeneous medium in 1 − D is presented. Based on the homogenization theory special intergrid connection operators have been developed to imitate a low frequency response of the differential equations with oscillatory coefficients. The proposed multi-grid method has been proved to have a fast rate of convergence governed by the ratio q / (4−q) where 0 > q ≤ 1 depends on the microstructure. This estimate reveals that the rate of convergence increases as q → 0, which corresponds to the increasing material heterogeneity.

An automatic and knowledge-based finite element mesh generator (INTELMESH), which makes extensive use of interactive computer graphics techniques, has been developed. INTELMESH is designed for planar domains and axisymmetric 3-D structures of elasticity and heat transfer subjected to mechanical and thermal loading. It intelligently identifies the critical regions/points in the problem domain and utilizes the new concepts of substructuringand wave propagation to choose the proper mesh size for them. INTELMESH generates well-shaped triangular elements by applying triangulation and Laplacian smoothing procedures. The adaptive analysis involves the initial finite element analysis and an efficient a-posteriori error analysis and estimation. Once a problem is defined, the system automatically builds a finite element model and analyzes the problem through an automatic iterative process until the error reaches a desired level. It has been shown that the proposed approach which initiates the process with an a-priori and near optimum mesh of the object, converges to the desired accuracy in less time and at less cost.

A new mesh-adaptive ID collocation technique has been developed to efficiently solve transient advcction-dominated transport problems in porous media that are governed by a hyperbolic/parabolic (singularly perturbed) PDE. After spatial discretization a singularly perturbed ODE is obtained which is solved by a modification of the COLNEW ODE-collocation code. The latter also contains an adaptive mesh procedure that has been enhanced here to resolve linear and nonlinear transport flow problems with steep fronts where regular FD and FE methods often fail. An implicit first-order backward Euler and a third-order Taylor-Donea technique arc employed for the time integration. Numerical simulations on a variety of high Peclet-number transport phenomena as they occur in realistic porous media flow situations are presented. Examples include classical linear advection-diffusion, nonlinear adsorption, two-phase Buckley-Leverett flow without and with capillary forces (Rapoport-Leas equation) and Burgers’ equation for inviscid fluid flow. In most of these examples sharp fronts and/or shocks develop which are resolved in an oscillation-free manner by the present adaptive collocation method. The backward Euler method has some amount of numerical dissipation is observed when the time-steps are too large. The third-order Taylor-Donea technique is less dissipative but is more prone to numerical oscillations. The simulations show that for the efficient solution of nonlinear singularly perturbed PDE’s governing flow transport a careful balance must be struck between the optimal mesh adaptation, the nonlinear iteration method and the time-stepping procedure. More theoretical research is needed with this regard.

Recently, a reliable a posteriori error estimate was developed, mainly based on the element residual method, for a class of steady state incompressible Navier-Stokes equations. In this paper, using this error estimate, a three-step h-p adaptive strategy is developed to solve incompressible flow problems. The goal of developing an h-p adaptive strategy is to obtain accurate approximate solutions while minimizing computational costs. The basic idea of the three-step h-p adaptive strategy is to solve for the system on the three consecutive meshes, i.e. an initial mesh, an intermediate h — adaptive mesh, and a final h-p adaptive mesh. Each new adaptive mesh is obtained by estimating the error on the previous mesh and executing a single h — or p — refinement procedure on the previous mesh according to the results of the adaptive strategy. Numerical results indicate that the proposed three-step adaptive strategy produces accurate solutions while keeping the total computational costs under control.

Important problems in Computational Medicine exist that can benefit from the implementation of adaptive mesh refinement techniques. Biological systems are so inherently complex that only efficient models running on state of the art hardware can begin to simulate reality. To tackle the complex geometries associated with medical applications we present a general purpose mesh generation scheme based upon the Delaunay tessellation algorithm and an iterative point generator. In addition, automatic, two- and three-dimensional adaptive mesh refinement methods are presented that are derived from local and global estimates of the finite element error. Mesh generation and adaptive refinement techniques are utilized to obtain accurate approximations of bioelectric fields within anatomically correct models of the heart and human thorax. Specifically, we explore the simulation of cardiac defibrillation and the general forward and inverse problems in electrocardiography (ECG). Comparisons between uniform and adaptive refinement techniques are made to highlight the computational efficiency and accuracy of adaptive methods in the solution of field problems in computational medicine.

The solution of small-strain elastic-plastic stress analysis problems by the p-version of the finite element method is discussed. The formulation is based on the deformation theory of plasticity and the displacement method. Practical realization of controlling discretization errors for elastic-plastic problems is the main focus of the paper. Numerical examples, whicii include comparisons between the deformation and incremental theories of plasticity under tight control of discretization errors, are presented.

The aim of adaptive methods for time-dependent p.d.e.s is to control the numerical error so that it is less than a user-specified tolerance. This error depends on the spatial discretization method, the spatial mesh, the method of time integration and the timestep. The spatial discretization method and positioning of the spatial mesh points should attempt to ensure that the spatial error is controlled to meet the user’s requirements. It is then desirable to integrate the o.d.e. system in time with sufficient accuracy so that the temporal error does not corrupt the spatial accuracy or the reliability of the spatial error estimates. This paper is concerned with the development of a prototype algorithm of this type, based on a cell-centered triangular finite volume scheme, for two space dimensional convection-dominated problems.

The derivative patch recovery technique developed by Zienkiewicz and Zhu (l] – [3] for the finite element method is analyzed. It is shown that, for one dimensional problems and two dimensional problems using tensor product elements, the patch recovery technique yields superconvergence recovery for the derivatives. Consequently, the error estimator based on the recovered derivative is asymptotically exact.