There has been a preliminary meeting for the seminar on
Wednesday, Feb 17, 13:00 in room 126 (A6)
where we presented potatial topics and fixed a
schedule.
If you were not there, you can of course still attend the seminar.
Contact us!
Systems of polynomial equations are for everyone: from
graduate students in computer science, engineering, or economics to
experts in algebraic geometry. This [seminar] aims to provide a
bridge between mathematical levels and to expose as many [aspects]
of the subject as possible.
Today, polynomial models are ubiquitous and widely applied across
the sciences. They arise in robotics, coding theory, optimization,
mathematical biology, computer vision, game theory, statistics,
machine learning, control theory, and numerous other areas.
[...]
Exciting recent developments in symbolic algebra and numerical
software for geometric calculations have revolutionized the field,
making formerly inaccessible problems tractable.''
(After [S])
The goal of the seminar is to explain some recent algorithms to find
some/all solutions to a polynomial system, assuming that their number
is finite. We will start by explaining to each other the needed
notions from numerical analysis and algebraic geometry.
- Newton's method, condition numbers and numerical homotopy
- Newton polytopes and mixed volumes
- Bernstein's theorem and polyhedral homotopies
- Bürgisser-Cucker algorithm to find some solution
- Gröbner bases and moment matrices
- Real-root finding using semi-definite optimization
Wed 10 - 11,
and by appointment
(Room 201, Arnimallee 3).
Thu 11 - 12
(Room 130, Arnimallee 6).
We will reserve some books in the library ("Handapparat").
| |
| Text Books |
| [D] |
Peter Deuflhard:
Newton methods for nonlinear problems. Affine invariance and adaptive
algorithms.
Springer Series in Computational Mathematics 35, 2004
|
| [SW] |
Andrew J. Sommese and Charles W. Wampler II: The Numerical
Solution of Systems of Polynomials Arising in Engineering and
Science. World Scientific, 2005
|
| [S] |
Bernd Sturmfels: Solving systems of polynomial equations.
CBMS Regional Conference Series in Mathematics 97 American
Mathematical Society, 2002
|
| |
| Journal Articles |
| [BC] |
Peter Bürgisser and Felipe Cucker: On a Problem Posed by Steve
Smale. arXiv:0909.2114
|
| [Dt] |
Jérôme Dégot:
A condition number theorem for underdetermined polynomial systems.
Math. Comput. 70 329-335 (2001)
|
| [DSZ] |
Michael Dellnitz, Oliver Schütze and Qinghua Zheng: Locating
all the zeros of an analytic function in one complex variable.
J. Comput. Appl. Math. 138 325-333 (2002)
|
| [G] |
Walter Gautschi:
On the condition of algebraic equations.
Numer. Math. 21 405-424 (1973)
|
| [HS] |
Birkett Huber and Bernd Sturmfels: A Polyhedral Method for Solving
Sparse Polynomial Systems.
Mathematics of
Computation 64 1541-1555 (1995)
|
| [HV] |
Birkett Huber and Jan Verschelde: Polyhedral end games for
polynomial continuation.
Numerical
Algorithms 18 91-108 (1998)
|
| [R] |
James Renegar: On the worst-case arithmetic complexity of
approximating zeros of systems of polynomials.
SIAM J. Comput. 18
350-370 (1989)
[PDF]
|
| [RB] |
Werner C. Rheinboldt & John V. Burkardt:
A locally parameterized continuation process.
ACM Transactions on Mathematical Software (TOMS) 9 215-235 (1983)
|
| [ST] |
Daniel A. Spielman & Shang-Hua Teng:
Smoothed analysis of algorithms.
Ta Tsien Li
(ed.) et al., Proceedings of the ICM 2002, Vol. I: Plenary lectures and ceremonies
World Scientific 2002
|
| |
| Software & links |
|
Coming soon ...
|
| |
You need to be open minded - you should consider neither numerical
analysis nor algebraic geometry as no-go areas. Background in one of
the following will be advantageous (but not required):
numerical analysis, algebraic geometry, convex optimization.
