This project continues the investigation of effective algorithms for some major problems of polynomial and matrix computations. One of the main subjects of the current project is the study of approximating polynomial zeros, which has recently resulted in the design of new solution algorithms running in optimal time (up to polylog factors). The optimality has been reached under both Boolean and arithmetic and both sequential and parallel models of computing. The project includes the work on extension of the latter results to other major problems of algebraic and numerical computing, such as computing approximate common divisors of pairs of univariate polynomials, approximation of matrix eigenvalues, solving systems of polynomial equations, and algebraic optimization problems. Another major direction of the project is to continue and extend the work on computations with structured matrices, which have applications to numerous major practical and theoretical computational problems, including the areas of speech and signal processing, Markovs chains, fundamental algebraic computations with general matrices, and the solution of partial differential and integral equations. ***
