Next: References Up: Results from Prior Previous: Development of Human
Vavasis
Vavasis has held an NSF Presidential Young Investigator Award ASC9057936 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:

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.
 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 singleauthor 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 reembed 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.

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 illconditioned
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.
 Optimization. Vavasis has also been active in numerical optimization. This work has also been supported by another NSF grant DMS8920550 with partial support from ONR, in which Vavasis is a coinvestigator. 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 ``layeredstep'' 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.
Next: References Up: Results from Prior Previous: Development of Human
nuprl project
Tue Nov 21 08:50:14 EST 1995