We describe algorithms for computing eigenpairs (eigenvalue--eigenvector) of a complex @math matrix @math . 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.
The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in n unknowns in time polynomial, on the average, in the size N of the input system. A partial solution to this problem was given by Carlos Beltr an and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that eciently implements a nonconstructive idea of V. I. Arnold, on behalf of the International Mathematical Union has written to a number of mathematicians with a suggestion that they describe some great problems for the next century. This report is my response. Arnold's invitation is inspired in part by Hilbert's list of 1900 (see e.g. [Browder, 1976]) and I have used that list to help design this essay. I have listed 18 problems, chosen with these criteria: We prove a new complexity bound, polynomial on the average, for the problem of finding an approximate zero of systems of polynomial equations. The average number of Newton steps required by this method is almost linear in the size of the input (dense encoding). We show that the method can also be used to approximate several or all the solutions of non-degenerate systems, and prove that this last task can be done in running time which is linear in the Bezout number of the system and polynomial in the size of the input, on the average.  We show that there are algorithms which find an approximate zero of a system of polynomial equations and which function in polynomial time on the average. The number of arithmetic operations is cN 4s , where N is the input size and c a universal constant  We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in @math complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed. Smale’s 17th Problem asks: “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?”. We give a positive answer to this question. Namely, we describe a uniform probabilistic algorithm that computes an approximate zero of systems of polynomial equations f : Cn −→ Cn, performing a number of arithmetic operations which is polynomial in the size of the input, on the average. In this paper we study volume estimates in the space of systems of n homegeneous polynomial equations of fixed degrees d i with respect to a natural Hermitian structure on the space of such systems invariant under the action of the unitary group. We show that the average number of real roots of real systems is D 1 2 where D = Π d i is the Be zout number. We estimate the volume of the subspace of badly conditioned problems and show that volume is bounded by a small degree polynomial in n, N and D times the reciprocal of the condition number to the fourth power. Here N is the dimension of the space of systems.