UW Home Page

Stephen A. Vavasis

Favorite links

U. Waterloo

Workshops and conferences

Professional societies:

Research supported by:

photo of Vavasis
Associate Dean, Computing, Faculty of Mathematics
Director, Mathematics Faculty Computing Facility (MFCF)
Professor (PhD, Stanford, 1989), Department of Combinatorics & Optimization
MC 6304 (C&O office)
MC 3047 (MFCF office)
University of Waterloo
200 University Avenue W.
Waterloo, ON N2L 3G1

On Github, I am user StephenVavasis. I am an inactive user of Facebook. Anyone claiming to be me on LinkedIn or other social networks is probably an impostor.

email: vavasis@uwaterloo.ca
phone: +1-519-888-4567 ext. 32130 or 37719
fax: +1-519-725-5441


In Fall 2018, I am teaching CO673/CS794, Optimization for Data Science. This course has its website on UWaterloo Learn. For those without Learn access yet, you can access course-information material and Problem Set 1 here.

Research and Publications

My research interests are continuous optimization and numerical analysis. More specifically, I am interested in:

  • Efficient algorithms for optimization
  • Applications of optimization to data science,
  • complexity issues in continuous optimization.

I have also in the past been interested in geometric problems arising in scientific computing and numerical linear algebra arising in differential equations.

Some publications and recent manuscripts:
  • S. Vavasis and Y. Ye, ``A primal dual accelerated interior point method whose running time depends only on A'' (compressed postscript, 170k). Final version appeared in Math. Progr. 74 (1996) 79-120.
  • P. Hough and S. Vavasis, ``Complete orthogonal decomposition for weighted least squares'' (gzip'd postscript, 84k; plain postscript, 330k). Final version appeared in SIAM J. Matrix Anal. Appl., 18 (1997) 369-392.
  • S. Mitchell and S. Vavasis, ``An aspect ratio bound for triangulating a d-grid cut by a hyperplane'' (compressed postscript, 118k; plain postscript, 339k). Extended abstract appeared in Proc. 1996 Symp. Comput. Geom., ACM Press, 48-57.
  • T. Driscoll and S. Vavasis, ``Numerical conformal mapping using cross-ratios and Delaunay triangulation'' (gzip'd postscript, 139k; plain postscript, 395k). Final version appeared in SIAM J. Sci. Comp. 19 (1998) 1783-1803.
  • S. Mitchell and S. Vavasis, ``Quality Mesh Generation in Higher Dimensions'' (gzip'd postscript, 130k; plain postscript, 388k). Final version appeared in SIAM J. Comput. 29 (2000) 1334-1370.
  • E. Bobrovnikova and S. Vavasis, ``Accurate Solution of Weighted Least Squares by Iterative Methods'' (gzip'd postscript, 105k; plain postscript, 349k). Final version appeared SIAM J. Matrix An. App 22 (2001) 1153-1174.
  • E. Bobrovnikova and S. Vavasis, ``A Norm Bound for Projections with Complex Weights'' (gzip'd postscript, 106k; plain postscript, 215k). Final version appeared Linear Alg. Appl. 307 (2000) 69-75.
  • V. Howle and S. Vavasis, ``Preconditioning complex-symmetric layered systems arising in electric power modeling'' (gzip'd postscript, 42k; plain postscript, 156k).
  • S. Vavasis, ``A note on efficient computation of the gradient in semidefinite programming'' (gzip'd postscript, 99k; plain postscript, 196k).
  • G. Jónsson and S. Vavasis, ``Solving polynomials with small leading coefficients'' (gzip'd postscript, 100k; plain postscript, 290k). Final version appeared: SIAM J. Matrix Analysis App., 26 (2005) 400-414.
  • V. Howle and S. Vavasis, ``An iterative method for solving complex-symmetric systems arising in electric power modeling'' (gzip'd postscript, 123k; plain postscript, 343k). Final version appeared: SIAM J. Matrix Analysis App., 26 (2005) 1150-1178
  • G. Jónsson and S. Vavasis, ``Accurate solution of polynomial equations using Macaulay resultant matrices'' (gzip'd postscript, 284k; plain postscript, 689k). Final version appeared: Mathematics of Computation, 74 (2005) 221-262
  • S. Vavasis, ``A Bernstein-Bezier sufficient condition for invertibility of polynomial mapping functions'' (revised 3 Nov 2001) (gzip'd postscript, 100k; plain postscript, 200k).
  • K. Papoulia and S. Vavasis, ``Time continuity in cohesive finite element modeling'' (pdf, 319k). Final version appeared: International Journal for Numerical Methods in Engineering 58(5) 679-701, 2003.
  • P. Ganguly, S. Vavasis and K. Papoulia, ``An algorithm for two-dimensional mesh generation based on the pinwheel tiling'' (pdf, 289k) SIAM J. Scientific Comput., 28 (2006) 1533-1562.
  • E. Boman, B. Hendrickson, and S. Vavasis, ``Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners'' (Arxiv link), SIAM J. Numer. Anal. 46 (2008) 3264-3284.
  • K. Papoulia, S. Vavasis and P. Ganguly, Spatial convergence of crack nucleation using a cohesive finite element model on a pinwheel-based mesh, International J. Numer. Meth. Eng. (pdf, 291k), 67(2006) 1-16.
  • Chin-Hang Sam, K. Papoulia, Stephen Vavasis, Obtaining initially rigid cohesive finite element models that are temporally convergent, Engineering Fracture Mechanics, 72 (2005) 2247-2267. (pdf, 310k)
  • S. Shontz and S. Vavasis, ``A linear weighted laplacian smoothing framework for warping tetrahedral meshes'' (arxiv link) Analysis of and workarounds for element reversal for a finite element-based algorithm for warping triangular and tetrahedral meshes, BIT Numerical Mathematics, Volume 50 (2010), Issue 4, 863-884.
  • Gun Srijuntongsiri and S. Vavasis, A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming, submitted to SIAM Journal on Optimization (arxiv link)
  • S. Vavasis, A conjecture that the roots of a univariate polynomial lie in a union of annuli (arxiv link)
  • Gun Srijuntongsiri and S. Vavasis, A condition number analysis of a line-surface intersection algorithm (arxiv link). SIAM J. Sci. Comput 30 (2008) 1064-1081.
  • S. Shontz and S. Vavasis, ``A robust solution procedure for hyperelastic solids with large boundary deformation'' (arxiv link). Final version appeared in Engineering with COmputers, posted on line 2011-June-11, print edition to appear.
  • Gun Srijuntongsiri and S. Vavasis, Properties of polynomial bases used in line-surface intersection algorithm (arxiv link)
  • S. Vavasis, On the complexity of nonnegative matrix factorization (arxiv link). Final version appeared, SIAM J. Optim. Volume 20, Issue 3, pp. 1364-1377 (2009).
  • Gun Srijuntongsiri and S. Vavasis, A condition number analysis of a surface-surface intersection algorithm (arxiv link)
  • M. Biggs, A. Ghodsi and S. Vavasis, Nonnegative matrix factorization via rank-one downdate, preliminary journal version from arxiv.org, ICML 2008 conference version.
  • B. Ames and S. Vavasis, Nuclear norm minimization for the planted clique and biclique problems (arxiv link; published paper.)
  • B. Ames and S. Vavasis, Convex relaxation for the planted k-disjoint-clique problem (arxiv link)
  • X. V. Doan and S. Vavasis, Finding approximately rank-one submatrices with the nuclear norm and l1 norm (arxiv link). Unpublished proof of NP-hardness of LAROS problem.
  • X. V. Doan, K.-C. Toh and S. Vavasis, A proximal point algorithm for sequential feature extraction applications (arxiv link)
  • S. Karimi and S. Vavasis, Detecting and correcting loss of independence in nonlinear conjugate gradient (arxiv link) (previously "Conjugate gradient with subspace optimization").
  • N. Gillis and S. Vavasis, Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization (arxiv link).
  • S. Sastry, S. Shontz, and S. Vavasis, A log-barrier method for mesh quality improvement and untangling, Final version appeared in Engineering with Computers, Nov 2012 (Springer Link web publication). Preliminary version appeared in Proceedings of the 2011 International Meshing Roundtable.
  • L. Elkin, Ting Kei Pong and S. Vavasis, Convex relaxation for finding planted influential nodes in a social network (arxiv link).
  • S. Vavasis, Some notes on applying computational divided differencing in optimization (arxiv link).
  • N. Gillis and S. Vavasis Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization, SIAM J. Optimiz., 25 (2015) 677-698, (arxiv link).
  • D. Drusvyatskiy, S.Vavasis, H. Wolkowicz Extreme point inequalities and geometry of the rank sparsity ball, Math. Progr. A 152 (2015) 521-544, (arxiv link).
  • X. V. Doan and S. Vavasis, Finding the largest low-rank clusters with Ky Fan 2-k-norm and l1 norm (arxiv link).
  • S. Karimi & S. Vavasis, IMRO: a proximal quasi-Newton method for solving l1-regularized least squares problem, (arxiv link).
  • N. Gillis & S. Vavasis, On the complexity of robust PCA and l1-norm low-rank matrix approximation, arxiv link).
  • S. Karimi & S. Vavasis, A unified convergence bound for conjugate gradient and accelerated gradient, (arxiv link).
  • S. Karimi & S. Vavasis, A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent, (arxiv link).
  • S. Vavasis, K. Papoulia and M. Hirmand, A second-order cone interior-point method for initially rigid cohesive fracture, PDF.