Interpolation error estimates in terms of geometric quality measures are established for harmonic coordinates on polytopes in two and three dimensions. First we derive interpolation error estimates over convex polygons that depend on the geometric quality of the triangles in the constrained Delaunay triangulation of the polygon. This characterization is sharp in the sense that families of polygons with poor quality triangles in their constrained Delaunay triangulations are shown to produce large error when interpolating a basic quadratic function. Non-convex polygons exhibit a similar limitation: large constrained Delaunay triangles caused by vertices approaching a non-adjacent edge also lead to large interpolation error. While this relationship is generalized to convex polyhedra in three dimensions, the possibility of sliver tetrahedra in the constrained Delaunay triangulation prevent the analogous estimate from sharply reflecting the actual interpolation error. Non-convex polyhedra are shown to be fundamentally different through an example of a family of polyhedra containing vertices which are arbitrarily close to non-adjacent faces yet the interpolation error remains bounded.

I propose two Galerkin methods based on the transfer-of-approximation property for static and dynamic acoustic boundary value problems in seismic applications. For problems with heterogeneous coefficients, the polynomial finite element spaces are no longer optimal unless special meshing techniques are employed. The transfer-of-approximation property provides a general framework to construct the optimal approximation subspace on regular grids. The transfer-of-approximation finite element method is theoretically attractive for that it works for both scalar and vectorial elliptic problems. However the numerical cost is prohibitive. To compute each transfer-of-approximation finite element basis, a problem as hard as the original one has to be solved. Furthermore due to the difficulty of basis localization, the resulting stiffness and mass matrices are dense. The 2D harmonic coordinate finite element method (HCFEM) achieves optimal second-order convergence for static and dynamic acoustic boundary value problems with variable coefficients at the cost of solving two auxiliary elliptic boundary value problems. Unlike the conventional FEM, no special domain partitions, adapted to discontinuity surfaces in coe cients, are required in HCFEM to obtain the optimal convergence rate. The resulting sti ness and mass matrices are constructed in a systematic procedure, and have the same sparsity pattern as those in the standard finite element method. Mass-lumping in HCFEM maintains the optimal order of convergence, due to the smoothness property of acoustic solutions in harmonic coordinates, and overcomes the numerical obstacle of inverting the mass matrix every time update, results in an efficient, explicit time step.

Finite difference and finite element methods exhibit first order convergence when applied to static interface problems where the grid and interface are not aligned. Although modified and unstructured grid methods would address the issue of misalignment for finite elements, application to large models of stratified media, such as those encountered in exploration geophysics, may require not only manual mesh manipulation but also more degrees of freedom than are ultimately necessary to resolve the solution. Instead using fitted or otherwise modified grids, this thesis details an improvement to an existing upscaling method that incorporates fine-scale variations of material properties by composing standard piecewise linear basis functions with a specific type of harmonic map. This technique requires that the problem domain be discretized using two meshes: one fine mesh where the harmonic map is computed to resolve fine-scale structures, and a coarse mesh where the solution to the problem is approximated. The implementation of this method in the literature restricts these composite basis functions to triangular elements in 2D leading to a non-conforming finite element method and suboptimal convergence. However, the support of these basis functions in harmonic coordinates is triangular. I present a mesh-mesh intersection algorithm that exploits this alternative representation to determine the true support of the composite basis functions in terms of the fine mesh. The result is a conforming, high-resolution finite element basis that is associated with the original coarse mesh nodes. Leveraging this fine scale information, I develop a new finite element matrix assembly algorithm. Knowing the shape of the basis support leads naturally to an integration method for computing the finite element matrix entries that is exact up to the accuracy of the harmonic map approximation. This new conforming method is shown to improve the accuracy of solutions to elliptic PDE with discontinuous coefficients on coarse, regular grids.