Polynomial and Matrix Computations

这个项目继续研究多项式和矩阵计算的一些主要问题的有效算法。 当前项目的主要课题之一是研究多项式零点的近似，这导致了最近在最佳时间（polylog因子）运行的新的解决方案算法的设计。在布尔和算术以及顺序和并行计算模型下都达到了最优。该项目包括对后者的结果扩展到其他主要问题的代数和数值计算，如计算近似公约数对单变量多项式，近似矩阵特征值，解决系统的多项式方程，代数优化问题的工作。 该项目的另一个主要方向是继续和扩展结构矩阵计算的工作，这些工作应用于许多主要的实际和理论计算问题，包括语音和信号处理，马尔可夫链，一般矩阵的基本代数计算以及偏微分和积分方程的解决方案。 ***

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. ***