Vavasis

Vavasis has held an NSF Presidential Young Investigator Award ASC-9057936 for the past five years entitled ``Computational Issues in the Solution of Partial Differential Equations.'' During the period of this support Vavasis has made progress in a number of areas:

1. Mesh generation [82]. Mitchell and Vavasis have developed the first algorithm for triangulating three dimensional polyhedral regions so that all the resulting tetrahedra have a provable bound on their aspect ratio. Furthermore, the Mitchell/Vavasis algorithm has the desirable property that the domain is never refined more than necessary to capture its geometry, unless the user requests further refinement. (This second property can also be stated as a theorem).

   The algorithm exists on paper, and a prototype implementation is complete.

2. Mesh partitioning. The main problem considered in this work is: given a mesh, cut it into pieces for the purpose of domain decomposition, nested dissection, and parallel computing. Vavasis initially considered this problem in a single-author paper [113], and a series of joint papers followed [81,80,79], which steadily improved the method, making it more powerful and general. The basic method for solving the mesh partitioning problem is to re-embed the mesh in a certain manner in and the cut it with a simple shape such as a hypersphere. It turns out that this simple, efficient approach gives bounds that are the optimal bounds.
3. Numerical analysis. Vavasis has written several papers [16,117,119,106,111,120] on numerical methods for linear algebra and differential equations. We highlight one of those results, namely, a new method [119] for solving the linear systems arising from finite element problems of the form in the case that the conductivity field c varies by orders of magnitude over the domain. Although the problem is mathematically well conditioned (due to the existence of a maximum principle), the ordinary finite element method is swamped by roundoff error because the stiffness matrix is highly ill-conditioned when c varies greatly. Vavasis discovered a new method for solving the finite element problem that satisfies a roundoff error bound independently of c. The new method completely bypasses the formation of the stiffness matrix.

4. Optimization. Vavasis has also been active in numerical optimization. This work has also been supported by another NSF grant DMS-8920550 with partial support from ONR, in which Vavasis is a co-investigator. A subset of Vavasis's publications on optimization include papers [50,83,112,115,116,118,121] and a book [114]. These papers, which establish complexity results about various optimization problems, are perhaps not as relevant for the proposal at hand so we do not delve into them. However, we point out one exciting development, namely the discovery by Vavasis and Ye [121] of a new kind of interior point method for linear programming called a ``layered-step'' method. The new method represents the first theoretical advance in the complexity of interior point methods for linear programming since 1986. Furthermore, the algorithm appears to be quite practical, and could become the dominant form of interior point method for use in practice.