AF: Novel Methods for Fundamental Matrix and Polynomial Computations

矩阵和多项式计算是科学、工程、信号和图像处理中现代计算的支柱。本项目将推进该领域两个中心学科领域的已知算法，即线性方程组的解和多项式的求根。求解线性系统将通过新型预处理技术的发展而得到推进，这将使求解更快、更准确。所提出的新的随机预处理方法对于具有少量小奇异值的重要输入矩阵具有很高的应用前景。对于这个类来说，已知方法的成本要高得多。同样的随机化技术，以及使用同伦延拓的替代方法，有望在解决结构化（例如Hankel和Toeplitz）线性方程组方面取得实质性进展。所引用的承诺依赖于最初但相当广泛的正式和实验研究的结果，这些研究推动了该项目。所提方法的直接应用包括多项式最大公因数（gcd）和近似最大公因数的计算。这些本身就是符号和符号数值计算的非常重要的主题，应用于控制、图像和信号处理以及代数曲线和曲面的计算。多项式求根的经典问题已经被深入研究了四千年（自苏美尔时代以来），但由于代数和几何计算以及信号处理的重要应用，它仍然是深入研究的主题。除了推进复数求根的任务之外，一个众所周知的挑战，特别是由代数几何优化问题引起的，是当C/R比很大时，具有C个复数根的多项式的R个实根的近似。有趣的是，领先的数值多项式寻根包和程序MPSolve和Eigensolve通过将任务限制为真正的寻根，最多可以节省10%的运行时间。多项式求根的最新进展主要依赖于矩阵方法。其中一些可以通过采用新的线性方程组预处理技术来推进。这样的预处理可以并行加速寻根。另一个方向，也基于矩阵方法，使数值技术的设计能够近似单变量多项式的实根。这一新颖的算法特征暗示了已知数值方法被引用的大因子C/R的加速。进一步的研究方向包括多项式根的新矩阵算法的设计，以及最近新算法的无矩阵变型，将其推广到多元多项式系统的求根，以及实现工作。现代计算的两个核心领域的预期进展将产生跨学科的影响；将数值方法与符号方法相结合，促进符号与数字的结合；该项目将展示算法设计中一些重要的通用技术的力量，如随机化和同伦延拓，并将汇集来自不同地域的科学家群体的能量和资源，他们在不同的学科领域工作，但对参与该项目感兴趣。最后但并非最不重要的是，该项目需要纽约市立大学雷曼学院和纽约市立大学研究生中心的学生参与；对于这样的学生，这个项目将是一个很好的研究经验。来自少数民族和代表性不足群体的学生也有望参与其中，他们将得到国家科学基金会和纽约市立大学的支持。

Matrix and polynomial computations are the backbone of modern computing in sciences, engineering and signal and image processing. This project shall advance the known algorithms in two central subject areas of this field, namely the solution of linear systems of equations and polynomial root-finding. Solving linear systems will be advanced by the development of novel preconditioning techniques, which will enable faster and more accurate solutions. The proposed novel methods of randomized preconditioning are highly promising for the important class of input matrices that have small numbers of small singular values. Known methods are substantially more costly for this class. The same randomization techniques, as well as alternative methods using homotopic continuation, promise substantial advance in solving structured (e.g. Hankel and Toeplitz) linear systems of equations. The cited promise relies on the results of the initial but quite extensive formal and experimental study that motivated the project. Immediate applications of the proposed methods include the computation of polynomial greatest common divisors (GCDs) and approximate GCDs. These are themselves highly important subjects of symbolic and symbolic-numerical computing having applications to control, image and signal processing and the computation of algebraic curves and surfaces. The classical problem of polynomial root-finding has been intensively studied for four millennia (since the Sumerian times) but is still the subject of intensive research, motivated by important applications to algebraic and geometric computations and signal processing. Besides the task of advancing complex root-finding, a well known challenge, motivated in particular by problems in algebraic geometric optimization, is the approximation of the R real roots of a polynomial having C complex roots, when the ratio C/R is large. Interestingly, the leading numerical polynomial root-finding packages and programs MPSolve and Eigensolve can save at most 10% of their running time by restricting the task to real root-finding. The recent progress in polynomial root-finding largely relied on matrix methods. Some of them can be advanced by employing new preprocessing techniques for linear systems of equations. Such preprocessing enables parallel acceleration of root-finding. Another direction, also based on matrix methods, enables the design of numerical techniques that approximate just the real roots of univariate polynomials. This novel algorithmic feature implied the acceleration of the known numerical methods by the cited large factor C/R. Further research directions include the design of new matrix algorithms for polynomial roots as well as matrix-free variations of the recent novel algorithms, their extension to root-finding for the systems of multivariate polynomials, and the implementation work. The expected progress in two central areas of modern computing will have interdisciplinary impact; it will combine numerical and symbolic methods, thus promoting their symbolic-numerical combination; the project will demonstrate the power of some important general techniques of algorithm design, such as randomization and homotopic continuation, and will bring together the energy and resources of a geographically diverse group of scientists, who are working in various subject areas but are interested in participation in the project. Last but not the least, the project assumes participation of students from Lehman College of CUNY and the Graduate Center of CUNY; for such students this project will be an excellent research experience. Participation of students from minorities and underrepresented groups is also expected and they will be supported both by the NSF and CUNY.