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.
