Exploiting unconventional QR-algorithms for fast and accurate computations of roots of polynomials

• Applicant: Dr. Thomas Mach
• Subject Area: Mathematics
• Term: from 2012 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 227388185

Retrieving the roots of a polynomial is a classical, centuries old problem. Still it is considered a fundamental problem in computational mathematics, with significant impact on present-day applications [Pan97]. Typical problems in sciences, engineering, statistics and financing, require the roots of moderate degree polynomials. Research evolutions, however, brought us new applications and larger problems coming, e.g., from algebraic optimization, algebraic geometry, and signal processing, requiring the solution of polynomials having degrees of several thousands. Long-established solvers are not satisfactory anymore, often needing unacceptable computing time or even delivering untrustworthy results. At this moment dominant computing packages tackle this problem by applying the QR-algorithm on the associated companion matrix, whose eigenvalues coincide with the roots. Even though the QR-algorithm is named one of the top 10 algorithms of the 20th century [Cip00], the current form, as pointed out by C. Moler [Mol91], Matlab´s inventor, is not yet the best possible, as specifically designed algorithms might save an order of storage and computing time. In this proposal we will unite two novel and challenging research trajectories. Newly developed unconventional QR-algorithms [Van11, VW12] will be applied on generalized companion factorizations [Fie03] to develop new fast, accurate, and reliable algorithms competing with state-of-the-art root-solvers. In this proposal we will unite two novel and challenging research trajectories.

• DFG Programme: Research Fellowships
• International Connection: Belgium
• Host: Professor Dr. Raf Vandebril