Gregorio Malajovich: Publications

Gregorio Malajovich: On the expected number of zeros of nonlinear equations . (Preprint, jul 21,2011).

ABSTRACT: This paper investigates the expected number of 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.

Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub: Adaptative 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.

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

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.

Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub: Convexity properties of the condition number . SIAM Journal on Matrix Analysis and Applications 31 No 3, pp 1491-1506 (January 2010).

ABSTRACT: We define in the space of n x m matrices of rank n, n ≤ m, the condition Riemannian structure as follows: For a given matrix A the tangent space at 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 σ_n(A). When this smallest singular value has multiplicity 1, the function A→ log(σ_n(A)^-2) is a convex function with respect to the condition Riemannian structure that is t → log(σ_n(A(t))^-2) is convex, in the usual sense for any geodesic A(t). In a more abstract setting, a function α defined on a Riemannian manifold (M,< , >) is said to be self-convex when log α (γ(t)) is convex for any geodesic in (M, α < , >). Necessary and sufficient conditions for self-convexity are given when α is C². When α(x)=d(x,N)^-2, where d(x,N) is the distance from x to a C² submanifold N⊆ R^j, we prove that α 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 σ_n(A) is self-convex in projective space and the solution variety.

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.

Felipe Cucker, Teresa Krick, Gregorio Malajovich and Mario Wschebor: A numerical algorithm for zero counting I: complexity and accuracy . Journal of Complexity 24 Issues 5-6, pp 582-605 (Oct-Dec 2008).

ABSTRACT: We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs $O(nD kappa(f)) iterations where n is the number of polynomials (as well as the dimension of the ambient space), D is a bound on the polynomials' degree, and kappa(f) is a condition number for the system. Each iteration uses an exponential number of operations. The algorithm uses finite-precision arithmetic and a polynomial bound for the precision required to ensure the returned output is correct which is polynomial in n, D and kappa and logarithmic in kappa The algorithm parallelizes well in the sense that each iteration can be computed in parallel polynomial time with an exponential number of processors.

Jean-Pierre Dedieu and Gregorio Malajovich: On the number of minima of a random polynomial . Journal of Complexity 24, pp 89--108 (2008).

ABSTRACT: We give the upper bound sqrt(2) (d-1)^(n+1)/2) for the expected number of critical points of a normal random polynomial with degree at most d and n variables. Using the large deviation principle for the spectral value of large random matrices we obtain the bound

K exp( -n² ln(3)/4 + ((n+1)/2) ln(d-1) )
for the expected number of minima of such a polynomial (here K is a positive constant). This proves that most normal random polynomials of fixed degree have only saddle points. Finally, we give a closed form expression for the expected number of maxima (resp. minima) of a random univariate polynomial, in terms of hypergeometric functions. (The ArXiV version is obsolete)

Gregorio Malajovich and Klaus Meer: Computing Multi-Homogeneous Bézout Numbers is Hard . Theory of Computing Systems 40 pp 553-570 (2007).

ABSTRACT: The multi-homogeneous Bézout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given an arbitrary, not necessarily multi-homogeneous system, one can ask for the optimal multi-homogenization that would minimize the Bézout number. In this paper, it is proved that the problem of computing, or even estimating the optimal multi-homogeneous Bézout number is actually NP-hard. In terms of approximation theory for combinatorial optimization, the problem of computing the best multi-homogeneous structure does not belong to APX, unless P = NP. Moreover, polynomial time algorithms for estimating the minimal multihomogeneous Bézout number up to a fixed factor cannot exist even in a randomized setting, unless BPP contains NP.

A conference version was published in: STACS 2005, Stuttgards. Lecture Notes in Computer Science 3404 pp. 244-255, Springer Verlag, Berlin, 2005.

Jean-Pierre Dedieu, Gregorio Malajovich and Mike Shub: On the Curvature of the Central Path of Linear Programming Theory . Foundations of Computational Mathematics 5 pp 145-171 (2005).

ABSTRACT: We prove a linear bound on the average total curvature of the central path of linear programming theory in terms on the number of independent variables of the primal problem, and independent on the number of constraints.

Gregorio Malajovich and J.Maurice Rojas: High probability analysis of the condition number of sparse polynomial systems . Theoretical Computer Science 315(2-3) pp. 525-555 (2004).

ABSTRACT: Let f:=(fⁱ,...,fⁿ) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than 1/ε. The bound depends on an integral of a differential form on a toric manifold and admits a simple explicit upper bound when the Newton polytopes (and underlying variances) are all identical.

We also consider polynomials with real coefficients and give bounds for the expected number of real roots and (restricted) condition number. Using a Kähler geometric framework throughout, we also express the expected number of roots of f inside a region U as the integral over U of a certain mixed volume form, thus recovering the classical mixed volume when U = (C^*)ⁿ.

Note: this paper supersedes Random Sparse Polynomial Systems

Jean-Pierre Dedieu, Pierre Priouret and Gregorio Malajovich: Newton Method on Riemannian Manifolds: Covariant Alpha-Theory . IMA Journal of Numerical Analysis 23-3 pp 395-419 (2003).

ABSTRACT: In this paper we study quantitative aspects of Newton method for finding zeros of mappings f: Mⁿ -> Rⁿ and vector fields X: Mⁿ -> TMⁿ.

Gregorio Malajovich and J.Maurice Rojas: Polynomial Systems and the Momentum Map . in: Cucker and Rojas (editors), Foundations of Computational Mathematics (Proceedings of SMALEFEST 2000) World Scientific, Singapore (2002).

ABSTRACT: This paper outlines a Kahler-geometric approach to the study of random sparse polynomial systems, with a view toward understanding the distribution of solutions and their numerical conditioning.

Gregorio Malajovich: Lower bounds for some decision problems over C . Theoretical Computer Science 276Pages 425-434 (2002).

ABSTRACT: Lower bounds for some explicit decision problems over the complex numbers are given

Gregorio Malajovich: On a transfer theorem for the P ≠ NP Conjecture . Journal of Complexity 17(1)(pp. 27-85) (March 2001).

ABSTRACT: A model of computation is defined over the algebraic numbers and over number fields. This model is non-uniform, and the cost of operations depends on the height of the operands and on the degree of the extension of the rational defined by those operands.

A transfer theorem for the P ≠ NP Conjecture is proved, namely: P≠NP in this model over the real algebraic numbers if and only if P≠NP in the classical setting.

Gregorio Malajovich and Jorge P. Zubelli: Tangent Graeffe Iteration . Numerische Mathematik 89 pp. 749-782 (2001).

ABSTRACT: Graeffe iteration was the choice algorithm for solving univariate polynomials in the XIX-th and early XX-th century. In this paper, a new variation of Graeffe iteration is given, suitable to IEEE floating-point arithmetics of modern digital computers.

We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterations and the running cost.

The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed.

We thank Mike McNamee for finding and helping to fix a series of typos in the published paper (see the errata below).

Gregorio Malajovich and Jorge P. Zubelli: On the Geometry of Graeffe Iteration . Journal of Complexity 17 pp.541-573 (2001).

ABSTRACT: A new version of the Graeffe's algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous to renormalization of dynamical systems.

This iteration is called Renormalized Graeffe Iteration. It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm.

If we start with a degree-d polynomial, each renormalized Graeffe iteration costs O(d²) arithmetic operations, with memory O(d).

A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed.

A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000.

James Demmel, Benjamin Diament and Gregorio Malajovich: On the Complexity of computing error bounds . Foundations of Computational Mathematics 1(1) pp 101-125 (2001).

ABSTRACT: We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e. estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they must sometimes exhibit large errors. Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors.

Most of condition estimation algorithms currently in use seem to satisfy the following properties: they perform at least one operation on each matrix entry, and they are arbitrarily faster than any zero tester. It is shown that any condition estimator satisfying those assumptions will give estimates wrong of a factor 2^{γ k + τ(n)}, where n is the dimension of the input matrix, k the bitsize, and where either γ >= .5 or τ(n) grows faster than any polynomial in n.

Gregorio Malajovich: Condition number bounds for problems with integer coefficients . J. of Complexity 16(3) 529-551 (2000).

ABSTRACT: An apriori bound for the condition number associated to each of the following problems is given: general linear equation solving, minimum squares, non-symmetric eigenvalue problems, solving univariate polynomials, solving systems of multivariate polynomials. It is assumed that the input has integer coefficients and is not on the degenerate locus of the respective problem (i.e. the condition number is finite). Then condition numbers are bounded in terms of the dimension and of the bit-size of the input.

In the same setting, bounds are given for the speed of convergence of the following iterative algorithms: QR without shift for the symmetric eigenvalue problem, and Graeffe iteration for univariate polynomials.

Gregorio Malajovich: Ultimate Polynomial Time . Unpublished MSRI Preprint 1999-03 (1999).

ABSTRACT: The class UP of `ultimate polynomial time' problems over C is introduced; it contains the class P of polynomial time problems over C. The tau-Conjecture for polynomials implies that UP does not contain the class of non-deterministic polynomial time problems definable without constants over C. This latest statement implies that P is not NP over C.

A notion of `ultimate complexity' of a problem is suggested. It provides lower bounds for the complexity of structured problems.

Gregorio Malajovich and Klaus Meer: On the structure of NP(C). . SIAM Journal on Computing 28(1) pp 27-35 (1998).

ABSTRACT: This paper deals with complexity classes P(C) and NP(C), as they were introduced over the complex numbers by Blum, Shub and Smale. Under the asssumption P(C) is not NP(C), the existence of non-complete problems in NP(C), not belonging to P(C), is established.

Gregorio Malajovich and Jorge P. Zubelli: A fast and stable algorithm for splitting polynomials . Computers & Mathematics with Applications 33(3) pp.1-23 (1997).

ABSTRACT: A new algorithm for splitting polynomials is presented. This algorithm requires O(d log(1/ε))^1+δ floating point operations, with O(log(1/ε))^1+δ bits of precision. As far as complexity is concerned, this is the fastest algorithm known by the authors for that problem.

An important application of the method is factorizing polynomials or polynomial root-finding.

Gregorio Malajovich: On generalized Newton algorithms : Quadratic convergence, path-following and error analysis . Theoretical Computer Science 133 No 65-84 (1994).

ABSTRACT: Newton iteration is known (under some precise conditions) to converge quadratically to zeros of non-degenerate systems of polynomials. This and other properties may be used to obtain theorems on the global complexity of solving systems of polynomial equations (See Shub and Smale in [Bezout1]), using a model of computability over the reals.

However, it is not practical (and not desirable) to actually compute Newton iteration exactly. In this paper, approximate Newton iteration is investigated for several generalizations of the Newton operator. Quadratic covergence theorems and a robustness theorem are extended to approximate Newton iteration, generalizing some of the results in [Bezout1]. The results here can be used to prove complexity theorems on path following algorithms for solving systems of polynomial equations, using a model of computation over the integers ([Malajovich])