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

利用非常规 QR 算法快速准确地计算多项式的根

• 批准号: 227388185
• 负责人: Dr. Thomas Mach
• 金额: --
• 依托单位: Department of Computer Science
• 依托单位国家: 德国
• 项目类别: Research Fellowships
• 财政年份: 2012
• 资助国家: 德国
• 起止时间: 2011-12-31 至 2012-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/227388185?language=en
• 关键词: Exploiting; unconventional; QR; algorithms; fast

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.

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