123 citations · 479 across the 28 of their papers we have counts for
28 papers
Global analysis of the Kuramoto flow
Daniel Burns, Gregorio Malajovich, Charles Pugh +2
Kuramoto's differential equation describes a synchronization process between several harmonic oscillators. It has been used to model biological phenomena such as the synchronizatio…
Complexity of sparse polynomial solving 3: Infinity
Gregorio Malajovich
A theory of numerical path-following in toric varieties was suggested in two previous papers. The motivation is solving systems of polynomials with real or complex coefficients. Wh…
On the expected number of real roots of polynomials and exponential sums
Gregorio Malajovich
The expected number of real projective roots of orthogonally invariant random homogeneous real polynomial systems is known to be equal to the square root of the Bézout number. A si…
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…
A theory of NP-completeness and ill-conditioning for approximate real computations
Gregorio Malajovich, Mike Shub
We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition…
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…
On the expected number of zeros of nonlinear equations
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. Thos…
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…
Convexity properties of the condition number II
Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich +1
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 Lips…
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…
A Numerical Algorithm for Zero Counting. I: Complexity and Accuracy
Felipe Cucker, Teresa Krick, Gregorio Malajovich +1
We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs O(n D kappa(f)) iterations where n is the number of po…
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…
Computing Multi-Homogeneous Bezout Numbers is Hard
Gregorio Malajovich, Klaus Meer
The multi-homogeneous Bezout 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…
On the Curvature of the Central Path of Linear Programming Theory
Jean-Pierre Dedieu, Gregorio Malajovich, Mike Shub
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 i…
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…