Stephen A. Vavasis
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
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.
- J. S. Guggenheim Fellow, 1996-1997
- Chair: Computing Facilities Executive Committee, Computer Science
- Chair: PhD Admissions Committee, Center for Applied Mathematics
- 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).
- 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,
- 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.
1995-1996 Annual Report Home Page
Departmental Home Page
If you have questions or comments please contact:
Last modified: 2 November 1996 by Denise Moore