Gregorio Malajovich

Gregorio Malajovich

The mixed volume counts the roots of generic sparse polynomial systems. Mixed cells are used to provide starting systems for homotopy algorithms that can find all those roots, and track no unnecessary path. Up to now, algorithms for that task were of enumerative type, with no general non- exponential complexity bound. A geometric algorithm is introduced in this paper. Its complexity is bounded in the average and probability-one settings in terms of some geometric invariants: quermassintegrals associated to the tuple of convex hulls of the support of each polynomial. Besides the complexity bounds, numerical results are reported. Those are consistent with an output- sensitive running time for each benchmark family where data is available. For some of those families, an asymptotic running time gain over the best code available at this time was noticed.

Gregorio Malajovich

This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of $n$-variate polynomial equations is specified through $n$ monomial bases. The natural locus for the roots of those systems is known to be a certain toric variety. This variety is a compactification of $(\mathbb C\setminus\{0\})^n$, dependent on the monomial bases. A toric Newton operator is defined on that toric variety. Smale's alpha theory is generalized to provide criteria of quadratic convergence. Two condition numbers are defined and a higher derivative estimate is obtained in this setting. The Newton operator and related condition numbers turn out to be invariant through a group action related to the momentum map. A homotopy algorithm is given, and is proved to terminate after a number of Newton steps which is linear on the condition length of the lifted homotopy path. This generalizes a result from Shub (2009).

Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich et al.

We define in the space of n by m matrices of rank n, n less or equal than m, the condition Riemannian structure as follows: For a given matrix A the tangent space of A is equipped with the Hermitian inner product obtained by multiplying the usual Frobenius inner product by the inverse of the square of the smallest singular value of A denoted sigma_n(A). When this smallest singular value has multiplicity 1, the function A -> log (sigma_n(A)^(-2)) is a convex function with respect to the condition Riemannian structure that is t -> log (sigma_n(A(t))^(-2)) is convex, in the usual sense for any geodesic A(t). In a more abstract setting, a function alpha defined on a Riemannian manifold (M,<,>) is said to be self-convex when log alpha (gamma(t)) is convex for any geodesic in (M,<,>). Necessary and sufficient conditions for self-convexity are given when alpha is C^2. When alpha(x) = d(x,N)^(-2) where d(x,N) is the distance from x to a C^2 submanifold N of R^j we prove that alpha is self-convex when restricted to the largest open set of points x where there is a unique closest point in N to x. We also show, using this more general notion, that the square of the condition number ||A|||_F / sigma_n(A) is self-convex in projective space and the solution variety.

Felipe Cucker, Teresa Krick, Gregorio Malajovich et al.

In a recent paper (Cucker, Krick, Malajovich and Wschebor, A Numerical Algorithm for Zero Counting. I: Complexity and accuracy, J. Compl.,24:582-605, 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 P{kappa(f) > a} and the expected value E(log kappa(f)).

Gregorio Malajovich

This paper investigates the expected number of complex roots of nonlinear equations. Those equations are assumed to be analytic, and to belong to certain inner product spaces. Those spaces are then endowed with the Gaussian probability distribution. The root count on a given domain is proved to be `additive' with respect to a product operation of functional spaces. This allows to deduce a general theorem relating the expected number of roots for unmixed and mixed systems. Examples of root counts for equations that are not polynomials nor exponential sums are given at the end.

Gregorio Malajovich

Those lectures revolve around the following problem: given a system of n real polynomials in n variables, count the number of real roots. The first lecture is a course on Newton iteration and alpha-theory. The second describes an inclusion-exclusion algorithm for real polynomials, developed by Felipe Cucker, Teresa Krick, Mario Wschebor and myself. The third lecture introduces tools for complexity analysis of numerical algorithms, and uses those tools to analyze our root-counting algorithm.

Gregorio Malajovich

The average mixed volume of a random projection of $d$ convex bodies in $\mathbb R^n$ is bounded above in terms of a quermassintegral.

Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich et al.

In our previous paper [SIMAX 31 n.3 1491-1506(2010)], we studied the condition metric in the space of maximal rank matrices. Here, we show that this condition metric induces a Lipschitz-Riemann 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 (Theorem 1). We also show that a similar result holds for the solution variety of linear systems (Theorem 31). Some of our intermediate results, such as Theorem 12, on the second covariant derivative or Hessian of a function with symmetries on a manifold, and Theorem 29 on piecewise self-convex functions, are of independent interest. Those results were motivated by our investigations on the com- plexity of path-following algorithms for solving polynomial systems.

Felipe Cucker, Teresa Krick, Gregorio Malajovich et al.

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.

Jean-Pierre Dedieu, Gregorio Malajovich

We give an upper bound in O(d ^((n+1)/2)) for the number of critical points of a normal random polynomial with degree d and at most n variables. Using the large deviation principle for the spectral value of large random matrices we obtain the bound O(exp(-beta n^2 + (n/2) log (d-1))) (beta is a positive constant independent on n and d) for the number of minima of such a polynomial. This proves that most normal random polynomials of fixed degree have only saddle points. Finally, we give a closed form expression for the number of maxima (resp. minima) of a random univariate polynomial, in terms of hypergeometric functions.