Randomization, Relaxation, and Complexity in Polynomial Equation Solving
About this Title
Leonid Gurvits, Los Alamos National Laboratory, Los Alamos, NM, Philippe Pébay, Sandia National Laboratories, Livermore, CA, J. Maurice Rojas, Texas A&M University, College Station, TX and David Thompson, Sandia National Laboratories, Livermore, CA, Editors
Publication: Contemporary Mathematics
Publication Year 2011: Volume 556
ISBNs: 978-0-8218-5228-6 (print); 978-0-8218-8235-1 (online)
This volume corresponds to the Banff International Research Station Workshop on Randomization, Relaxation, and Complexity, held from February 28–March 5, 2010 in Banff, Alberta, Canada.
This volume contains a sample of advanced algorithmic techniques underpinning the solution of systems of polynomial equations. The papers are written by leading experts in algorithmic algebraic geometry and touch upon core topics such as homotopy methods for approximating complex solutions, robust floating point methods for clusters of roots, and speed-ups for counting real solutions. Vital related topics such as circuit complexity, random polynomials over local fields, tropical geometry, and the theory of fewnomials, amoebae, and coamoebae are treated as well. Recent advances on Smale's 17th Problem, which deals with numerical algorithms that approximate a single complex solution in average-case polynomial time, are also surveyed.
Graduate students and research mathematicians interested in algorithms in algebraic geometry.
Table of Contents
- Martin Avendaño and Ashraf Ibrahim – Multivariate ultrametric root counting
- Daniel J. Bates, Jonathan D. Hauenstein and Andrew J. Sommese – A parallel endgame
- Carlos Beltrán and Luis Miguel Pardo – Efficient polynomial system solving by numerical methods
- Bruno Grenet, Erich L. Kaltofen, Pascal Koiran and Natacha Portier – Symmetric determinantal representation of formulas and weakly skew circuits
- Tsung-Lin Lee and Tien-Yien Li – Mixed volume computation in solving polynomial systems
- Anton Leykin – A search for an optimal start system for numerical homotopy continuation
- Mounir Nisse – Complex tropical localization, and coamoebas of complex algebraic hypersurfaces
- Osbert Bastani, Christopher J. Hillar, Dimitar Popov and J. Maurice Rojas – Randomization, sums of squares, near-circuits, and faster real root counting
- Korben Rusek, Jeanette Shakalli and Frank Sottile – Dense fewnomials
- Zhonggang Zeng – The numerical greatest common divisor of univariate polynomials