Diego Armentano

Diego Armentano, Michael Shub

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. Smale's upper bound estimate was infinite average cost. Our's is polynomial in the Bézout number and the dimension of the input. Hence polynomial for any range of dimensions where the Bézout number is polynomial in the input size. In particular not just for the case that Smale considered but for a range of dimensions as considered by Bürgisser-Cucker where the max of the degrees is greater than or equal to $n^{1+ε}$ for some fixed $ε$. It is possible that Smale's algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem.

Diego Armentano, Mario Wschebor

We consider random systems of equations over the reals, with $m$ equations and $m$ unknowns $P_i(t)+X_i(t)=0$, $t\in\mathbb{R}^m$, $i=1,...,m$, where the $P_i$'s are non-random polynomials having degrees $d_i$'s (the "signal") and the $X_i$'s (the "noise") are independent real-valued Gaussian centered random polynomial fields defined on $\mathbb{R}^m$, with a probability law satisfying some invariance properties. For each $i$, $P_i$ and $X_i$ have degree $d_i$. The problem is the behavior of the number of roots for large $m$. We prove that under specified conditions on the relation signal over noise, which imply that in a certain sense this relation is neither too large nor too small, it follows that the quotient between the expected value of the number of roots of the perturbed system and the expected value corresponding to the centered system (i.e., $P_i$ identically zero for all $i=1,...,m$), tends to zero geometrically fast as $m$ tends to infinity. In particular, this means that the behavior of this expected value is governed by the noise part.

Diego Armentano

A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale's $γ$-Theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.

Diego Armentano

We define a new condition number adapted to directionally uniform perturbations. The definitions and theorems can be applied to a large class of problems. We show the relation with the classical condition number, and study some interesting examples.

Diego Armentano, Leandro Bentancur, Federico Carrasco et al.

We consider the logarithmic Fekete problem, which consists of placing a fixed number of points on the unit sphere in $\mathbb{R}^d$, in such a way that the product of all pairs of mutual Euclidean distances is maximized or, equivalently, so that their logarithmic energy is minimized. Using tools from Computational Algebraic Geometry, we find and classify all critical configurations for this problem when considering at most six points in every dimension $d$. In particular, our approach gives new proofs of several key results appearing in the literature, with the benefit of using a unified approach. Furthermore, for seven points in $S^2$, we characterize the global minimizer among critical configurations having at least one pair of antipodal points, and give numerical evidence to support the conjecture that this configuration is also the unrestricted global minimizer.

Carlos Beltrán, Diego Armentano

We compute the exact value of the squared condition number for the polynomial eigenvalue problem, when the input matrices have entries coming from the standard complex Gaussian distribution, showing that in general this problem is quite well conditioned.

Diego Armentano, Carlos Beltrán, Peter Bürgisser et al.

Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).

Diego Armentano, Carlos Beltrán, Peter Bürgisser et al.

We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex $n\times n$ matrix $A$. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.

Diego Armentano, Carlos Beltrán, Michael Shub

We describe two algorithms for the eigenvalue, eigenvector problem which, on input a Gaussian matrix with complex entries, finish with probability 1 and in average polynomial time.