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

求多项式的根是一个经典的、有几个世纪历史的问题。尽管如此，它仍然被认为是计算数学中的一个基本问题，对当今的应用具有重大影响[Pan97]。在科学、工程、统计和金融等领域的典型问题，都需要求解中等次多项式的根。然而，研究的发展给我们带来了新的应用和更大的问题，例如，来自代数优化，代数几何和信号处理，需要解决数千次多项式。长期建立的求解器不再令人满意，通常需要不可接受的计算时间，甚至交付不可信的结果。目前主流的计算包通过对特征值与根重合的伴生矩阵应用qr算法来解决这一问题。尽管qr算法被评为20世纪十大算法之一[Cip00]，但正如Matlab的发明者C. Moler [Mol91]指出的那样，目前的形式还不是最好的，因为专门设计的算法可能会节省一个数量级的存储和计算时间。在这个建议中，我们将结合两个新颖和具有挑战性的研究轨迹。新开发的非常规qr算法[Van11， VW12]将应用于广义伴分解[Fie03]，以开发新的快速、准确和可靠的算法，与最先进的根求解器竞争。在这个建议中，我们将结合两个新颖和具有挑战性的研究轨迹。

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.