eBook

Randomization, relaxation, and complexity in polynomial equation solving : Banff International Research Station workshop on Randomization, Relaxation, and Complexity, February 28-March 5, 2010, Banff, Ontario, Canada

Gurvits, Leonid, Thompson, David, Randomization, relaxation, and complexity, Pébay, Philippe, Rojas, J. Maurice

2011

Overview

This volume corresponds to the Banff International Research Station Workshop on Randomization, Relaxation, and Complexity, held from February 28-March 5, 2010 in Banff, Ontario, 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.

• Publisher: American Mathematical Society
• Subject: Algebraic geometry -- Computational aspects in algebraic geometry -- Effectivity, complexity. msc / Algebraic geometry -- Real algebraic and real analytic geometry -- Topology of real algebraic varieties. msc / Algebraic geometry -- Special varieties -- Toric varieties, Newton polyhedra. msc / Algebraic geometry -- Tropical geometry -- Tropical geometry. msc / Algorithms / Algorithms -- Congresses / Convex and discrete geometry -- Polytopes and polyhedra -- Computational aspects related to convexity. msc / Field theory and polynomials -- Computational aspects of field theory and polynomials -- Computational aspects of field theory and polynomials. msc / Geometry, Algebraic / Geometry, Algebraic -- Congresses / Number theory / Number theory -- Computational number theory -- Algorithms; complexity. msc / Number theory -- Congresses / Numerical analysis -- Computer aspects of numerical algorithms -- Complexity and performance of numerical algorithms. msc / Numerical analysis -- Nonlinear algebraic or transcendental equations -- Roots of polynomial equations. msc
• ISBN: 9780821852286, 0821852280