123 citations · 479 across the 28 of their papers we have counts for
19 papers · 1 filter
Complexity of Sparse Polynomial Solving 2: Renormalization
Gregorio Malajovich
Renormalized homotopy continuation on toric varieties is introduced as a tool for solving sparse systems of polynomial equations, or sparse systems of exponential sums. The cost of…
Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
Gregorio Malajovich
This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of -variate polynomial equations is specif…
Computing mixed volume and all mixed cells in quermassintegral time
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…
Average mixed volume under projection
Gregorio Malajovich
The average mixed volume of a random projection of convex bodies in is bounded above in terms of a quermassintegral.
Newton iteration, conditioning and zero counting
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 it…
Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations
Jean-Pierre Dedieu, Gregorio Malajovich, Michael Shub
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 choos…
A Numerical Algorithm for Zero Counting. III: Randomization and Condition
Felipe Cucker, Teresa Krick, Gregorio Malajovich +1
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…
A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis
Felipe Cucker, Teresa Krick, Gregorio Malajovich +1
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 norm…
A numerical algorithm for zero counting II: Randomization and Condition
Felipe Cucker, Teresa Krick, Gregorio Malajovich +1
This paper was witdrawn by the authors.
Convexity properties of the condition number
Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich +1
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…
On the number of minima of a random polynomial
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…
High Probability Analysis of the Condition Number of Sparse Polynomial Systems
Gregorio Malajovich, J. Maurice Rojas
Let F:=(f_1,...,f_n) 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…
Newton Method on Riemannian Manifolds: Covariant Alpha-Theory
Jean-Pierre Dedieu, Pierre Priouret, Gregorio Malajovich
In this paper we study quantitative aspects of Newton method for finding zeros of mappings f: M_n -> R^n and vector fields X: M_x -> TM_n
Random Sparse Polynomial Systems
Gregorio Malajovich, J. Maurice Rojas
Let f:=(f^1,\...,f^n) be a sparse random polynomial system. This means that each f^i has fixed support (list of possibly non-zero coefficients) and each coefficient has a Gaussian…
Tangent Graeffe Iteration
Gregorio Malajovich, Jorge P. Zubelli
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, s…
On the Geometry of Graeffe Iteration
Gregorio Malajovich, Jorge P. Zubelli
A new version of the Graeffe algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous t…
Ultimate Polynomial Time
Gregorio Malajovich
The class of `ultimate polynomial time' problems over is introduced; it contains the class of polynomial time problems over . The…
Lower bounds for some decision problems over C
Gregorio Malajovich
Lower bounds for some explicit decision problems over the complex numbers are given.
Condition number bounds for problems with integer coefficients
Gregorio Malajovich
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…