Deterministic and Probabilistic Complexity of Algorithms for Solving Equations

Please be patient while loading this page. We are running MathJax

Mario Wschebor Jean-Pierre Dedieu
1939-2011 1949-2012

General description

Solving systems of polynomial equations is a classical subject with a long history. It was one of the motivations in the classical development of Algebra and Algebraic Geometry. It was one of the main pursuits of early Numerical Analysis. Yet, our actual knowledge is not enough to solve but a small part of the systems that arise from many subjects, such as chemistry, physics, or engineering.

The main goals of this research program are:

1.Improve our understanding of algorithms for solving non-linear systems of equations, such as systems of polynomials.
2. Understand the mathematical limitations of that class of algorithms, e.g. lower bounds on complexity.
3. Understand better objects such as random polynomial systems.
4. Develop efficient algorithms, with proven complexity bounds.

This is the official page of the Complexity grant, funded by the MathAmSud consortium.

Main participants

The main participants of this MathAmSud grant are:

Gregorio Malajovich (gregorio.malajovich at gmail.com), UFRJ (International coordinator).

Guillaume Chèze, Université Paul Sabatier.

Teresa Krick, Universidad de Buenos Aires.

Mike Shub, Conicet, IMAS, Universidad de Buenos Aires, Argentina and CUNY graduate school, New York, US.

Diego Armentano, Universidad de la República.

Mario Wschebor and Jean-Pierre Dedieu were important participants in this project.

Other frequent collaborators not covered by the MathAmSud grant are Felipe Cucker and Carlos Beltrán.

Sub-projects.

Background information on the subject of real number complexity and homotopy algorithms may be found in Blum, Cucker, Shub and Smale (1998). For more recent textbooks related to polynomial solving, see Dedieu (2006) or Malajovich (2011).

Better understanding of algorithms for finding (or deciding or counting) real solutions of real polynomial systems.

A subset $X$ of $\bf R^{\infty}$ is in the complexity class $NP_{\bf R}$ if and only if there is a BSS machine $M=M(x,g)$ such that,
1. If $x \in X$ then there is $g$ such that $M(x,g)$ stops in polynomial time (w.r.t. the size of $x$).
2. If $x \not \in X$, then $M(x,g)$ will stop for no $g$.

The class $\#P_{\mathbb R}$ as defined by Meer (2000) consists of all functions $f: \mathbb R^{\infty} \rightarrow \mathbb N \cup \{0\} \cup \{\infty\}$ that $f(x)$ count the number of accepting guesses $g$ for a machine $M$ associated to a problem in the class $NP$.

A canonical $\#P$-complete problem is counting the number of real solutions of a real polynomial system. This is also a classical problem in logic and computational algebraic geometry. (See the references in our paper below).

The novelty in our paper (Cucker, Krick, Malajovich and Wschebor, 2008) is that we estimated the complexity of real root counting in terms of a condition number. Condition numbers measure the sensistivity of solutions to the initial data. Here, since we deal with a counting problem, the condition number of a polynomial system should be defined such that is large if and only if,
1. It admits is an ill-conditionned real root, or
2. A small perturbation can `create' a root where there was none.

Those ideas are developed in our two papers (Cucker, Krick, Malajovich and Wschebor 2009 and in print). In the first one, a condition number theorem is proved and this is used to estimate the probability that this condition number is large. A smoothed analysis estimate of the condition number follows. In the last one, a sharper estimate on the probability that the condition number is large is given. A possible future development is to use this sort of ideas as a building block for a complexity theory for numerical algorithms.

Development of the theory of self-convexity

A Lipschitz-Riemann structure in a manifold is an inner product in that manifold that admits Lipschitz (not necessarily $C^1$) local coefficients.

It makes sense to speak of minimizing geodesics in a Lipschitz-Riemann structure, although there are given no more by a differential equation but by a differential inclusion.

Definition: Let $M,\langle\cdot,\cdot\rangle)$ be a $\mathcal C^2$ Riemannian manifold, and let $\alpha : M \rightarrow \mathbb R$ be a locally Lipschitz function with positive values. Let $M_\kappa$ be the manifold $M$ with the new metric \[ \langle\cdot,\cdot\rangle_{\kappa , x} = \alpha (x)\langle\cdot,\cdot\rangle_x \] called condition Riemann structure or simply condition structure. We say that $\alpha$ is self-convex when $\log \alpha(\gamma (t))$ is convex for any geodesic $\gamma$ in~$M_\kappa$.

Examples of self-convex maps are given in Beltrán-Dedieu-Malajovich-Shub (2010) where this concept was introduced for the first time.

The main motivation for this concept comes from the complexity analysis of homotopy methods for solving equations. The basic principle of those methods is to lift a path $f_t$ in the space of polynomial systems, to a path $(f_t, x_t)$ in the solution variety $\{ (f,x): f(x)=0 \}$. One approximates $x_t$ numerically, and $x_1$ is then an approximate zero for $f_1$.

The complexity of algorithms for approximating numerically this lifting is a current subject of research. The sharpest known complexity bound is proportional to the length of the lifted path with respect to the condition structure $\alpha(f,x) = \mu(f,x)^2$ where $\mu$ is the condition number. In that sense, the minimizing geodesic between the initial pair (polynomial, root) $(f_0, x_0)$ and the final pair $(f_1, x_1)$ corresponds to the fastest path.

Would this function $\alpha$ be self-convex, the condition number should be maximized at the extreme points of a geodesic segment. This would allow for better and cleaner estimates of the average complexity of solving complex polynomial systems.

In a recent (and difficult) paper, we proved that conjecture for the degree 1 case.

Implementation of condition-metric based, predictor-corrector methods for polynomial systems

We are interested in problems like: given a system of polynomial equations, find one (all) the roots. In order to do that with a homotopy algorithm, we need (given $f_1$) choose a path $f_t$.

Many algorithms use a random pair $(f_0,x_0)$ to start a linear homotopy. This means that $[f_0, f_1]$ is a straight line, or a great circle. In this project, we would like to develop algorithms that approximate a local geodesic in the condition metric. This would provide a better complexity than linear homotopy.

Eigenvalue problems

The aim of this project is to apply our results for general polynomial systems to the eigenvalue problem.

Activities.

A first meeting took place in Montevideo in April 2011. and a mini-conference was held in Paraty RJ in april 2012.

Results.

The following publicationss were funded by the mathamsud grant:

Diego Armentano: Complexity of Path-Following Methods for the Eigenvalue Problem . (2011).

ABSTRACT: In this paper we study path-following methods for the eigenvalue problem. We introduce a projective framework to analyze this problem. We define a condition number and a Newton's map appropriate for this context, proving a version of the $\gamma$-Theorem. Our main result bounds the complexity of path-following methods in terms of the length of the path in the condition metric.

Go to the ArXiV version

Diego Armentano: . Complexity and Random Polynomials Doctoral thesis, Universidad de la República and Université Paul Sabatier (2012).

ABSTRACT: In this dissertation we analyze two dierent approaches to the problem of solving system of polynomial equations. In the rst part of this thesis we analyze the complexity of certain algorithms for solving system of equations, namely, homotopic methods or path-following methods. Special attention is given to the eigenvalue problem, introducing a projective framework to analyze this problem. The main result is to bound the complexity of path-following methods in terms of the length of the path in the condition metric, proving the existence of short paths in the condition metric. We also address the problem of the complexity of Bezout's theorem, reconsidering Smale's algorithm in the light of work done in the intervening years. At the end of this rst part we dene a new condition number adapted to directionally uniform perturbations in a general framework of maps between Riemannian manifolds, relating it with the classical condition number in many interesting examples. In the second part of this dissertation we center our attention on the set of solutions of system of equations where the coecients are taken at random with some probability distribution. We start giving an outline on Rice formulas for random elds. We review some recent results concerning the expected number of real roots of random systems of polynomial equations. We also recall and give new proofs of some known results about the undetermined case, that is, when the random system of equations has less equations than unknowns. We also study complex random systems of polynomial equations. We introduce the technics of Rice formulas in the realm of complex random elds. In particular, we give a probabilistic approach of Bezout's theorem using Rice formulas. At the end of this second part we deal with the following question: How are the roots of complex random polynomials distributed?. We prove that points in the sphere associated with roots of random polynomials via the stereographic projection, are surprisingly well-suited with respect to the minimal logarithmic energy on the sphere. That is, roots of random polynomials provide a fairly good approximation to Elliptic Fekete points.

Download or Visualize PDF version

Diego Armentano and Mike Shub: Smale's Fundamental Theorem of Algebra reconsidered . (2012).

ABSTRACT: In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Our main theorem raises more problems than it solves.

Go to the ArXiV version Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub: Convexity properties of the condition number II . SIAM Journal on Matrix Analysis and Applications 33(3) pp 905--939 (Aug. 2012).

ABSTRACT: In our previous paper [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1491--1506], we studied the condition metric in the space of maximal rank imes m$ matrices. Here, we show that this condition metric induces a Lipschitz Riemannian structure on that space. After investigating geodesics in such a nonsmooth structure, we show that the inverse of the smallest singular value of a matrix is a log-convex function along geodesics. We also show that a similar result holds for the solution variety of linear systems. Some of our intermediate results such as those on the second covariant derivative or Hessian of a function with symmetries on a manifold, and those on piecewise self-convex functions, are of independent interest. Those results were motivated by our investigations on the complexity of path-following algorithms for solving polynomial systems.

Go to the journal version Download or Visualize PDF version Go to the ArXiV version

Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor: A numerical algorithm for zero counting III: Randomization and Condition . Advances in Applied Mathematics 48-1, pp. 215-248 (January 2012).

ABSTRACT: In a recent paper [A numerical algorithm for zero counting I: complexity and accuracy . J. of Complexity 24 5-6, pp 582-605 (Oct-Dec 2008)] we analyzed a numerical algorithm for computing the number of real zeros of a polynomial system. The analysis relied on a condition number \(\kappa(f)\) for the input system \(f\). In this paper we look at \(\kappa(f)\) as a random variable derived from imposing a probability measure on the space of polynomial systems and give bounds for both the tail \(\mathbb P\{\kappa(f)> a\}\) and the expected value \(\mathbb E(\log\kappa(f))\).

Go to the journal version Go to the ArXiV version

Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub: Adaptive Step Size Selection for Homotopy Methods to Solve Polynomial Equations . IMA Journal of Numerical Analysis 33, 1-29 (2013).

ABSTRACT: Given a \(C^1\) path of systems of homogeneous polynomial equations \(f_t\), \(t \in [a,b]\) and an approximation \(x_a\) to a zero \(\zeta_a\) of the initial system \(f_a\), we show how to adaptively choose the step size for a Newton based homotopy method so that we approximate the lifted path \((f_t,\zeta_t)\) in the space of (problems, solutions) pairs.

The total number of Newton iterations is bounded in terms of the length of the lifted path in the condition metric.

Free link to the paper Go to the journal version Go to the ArXiV version

Gregorio Malajovich: . Nonlinear Equations With an appendix by Carlos Beltrán, Jean-Pierre Dedieu, Luis Miguel Pardo and Mike Shub. Publicações Matemáticas do IMPA, [8^o\] Colóquio Brasileiro de Matemática (IMPA, Rio de Janeiro, 2011. xiv+177 pp. ISBN: 978-85-244-0329-3).

ABSTRACT: These notes correspond to a short course during the 28th Colóquio Brasileiro de Matemática, held in Rio de Janeiro in July 2011. My plan is to let them grow into a book that can be used for a graduate course on the mathematics of nonlinear equation solving.

Look in the Mathematical Reviews

Other related papers of this team, not funded by this grant:

Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor: A numerical algorithm for zero counting II: Distance to ill-posedness and smoothed analysis . Journal of Fixed Point Theory and Applications 6 No 2, pp 285-294 (Dec. 2009).

ABSTRACT: We show a Condition Number Theorem for the condition number of zero counting for real polynomial systems. That is, we show that this condition number equals the inverse of the normalized distance to the set of ill-posed systems (i.e., those having multiple real zeros). As a consequence, a smoothed analysis of this condition number follows.

Go to the journal version Go to the ArXiV version

Sponsors