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

- 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.

Mario Wschebor | Jean-Pierre Dedieu |

1939-2011 | 1949-2012 |

The main goals of this research program are:

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

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.

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.

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.

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.

**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.

**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.

**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.

**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.

**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))\).

**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.

**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.

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.