Stephen Vavasis

Stephen A. Vavasis
Associate Professor
vavasis@cs.cornell.edu
http://www.cs.cornell.edu/home/vavasis/vavasis.html
Ph.D. Stanford University, 1989

As computer hardware becomes more powerful, there is a corresponding growth in the demand for more efficient algorithms to solve large-scale scientific problems. My research is on the design and analysis of such algorithms. One area of interest is algorithms for optimization. With Ph.D. student Patricia Hough, we have developed methods for stably solving the weighted least squares problems arising in interior point methods. This new method has been tested using state-of-the-art software for linear programming and is found to be much more robust in the case of near degenerate. With PhD student Elena Bobrovnikova, we are investigating iterative methods for weighted least squares and considering applications to electrical networks.

With Hough and John Gilbert of Xerox PARC, we are developing a method for efficiently computing the "layered least squares'' step in an interior point method. The layered step, a new search direction introduced by Vavasis and Ye, has the potential to lead to much more efficient solution of linear programming problems.

Work on geometry in scientific computing also continues. An improved version of QMG is scheduled for release in June, 1996. QMG is a three-dimensional volumetric unstructured mesh generator for very general polyhedral regions with guaranteed aspect ratio bound, developed jointly with S. Mitchell of Sandia. In new work with PhD student Tobin Driscoll, we have developed an algorithm for conformal mapping of a polygon. The new algorithm can find the correct conformal map for any polygon even if it is elongated, unlike previous algorithms for the problem. The new algorithm can be used for extremely accurate solutions of Laplace's equation and also for two-dimensional structured mesh generation.

Awards

J. S. Guggenheim Fellow, 1996-1997

University Activities

Chair: Computing Facilities Executive Committee, Computer Science Department
Chair: PhD Admissions Committee, Center for Applied Mathematics

Professional Activities

Editor: Journal on Global Optimization
Referee: Mathematical Programming; Journal of Algorithms; MIT Press; National Science Foundation; SIAM Review; SIAM Press; Mathematics of Computation; National Science and Engineering Research Council (Canada); Journal of the ACM; Symposium on Computation Geometry; SIAM Journal Scientific Computing; Parallel Processing Letters; IMA Journal; Journal of Complexity, Cornell Theory Center; Information Processing Letters; Journal of Parallel and Distributed Computing; International Journal on Parallel Processing
Visiting Researcher: Xerox Palo Alto Research Center, Research Institute for Advanced Computer Science (NASA Ames Research Center).

Lectures

Indicators for interior point methods and the layered step. AMS Conference on the Mathematical Foundations of Numerical Analysis, Park City, UT, July 24, 1995.
Finite element mesh generation with QMG. Dartmouth University, Hanover, NH, January 17, 1996.
A condition number for rectangular matrices. Operations Research and Industrial Engineering, Cornell University, February 6, 1996.
Efficient layered step computation for interior point methods. SIAM Conference on Optimization, Victoria, B.C., May 20, 1996.
An aspect ratio bound for triangulating a d-grid cut by a hyperplane. ACM Symposium on Computational Geometry, Philadelphia, PA, May 24, 1996.

Publications

An aspect ratio bound for triangulating a d-grid cut by a hyperplane (extended abstract). Proceedings 12th ACM Symposium on Computation Geometry, 1996 (with S. Mitchell).
Condition numbers for polyhedra with real number data. Operations Research Letters 17 (1995), 209-214 (with Y. Ye).
Stable finite elements for problems with wild coefficients. SIAM Journal on Numerical Analysis 33 (1996), 890-916.

Return to: