论文标题
Chebyshev rootinging的等级结构QR
Rank-structured QR for Chebyshev rootfinding
论文作者
论文摘要
我们考虑以Chebyshev表示多项式的根的计算。我们扩展了[Eidelman，Y.，Gemignani，L。和Gohberg，I.，Numer。算法，47.3（2008）：pp。253-273]引入了一种积极的早期通缩策略，并表明等级结构允许并行化算法，以避免使用的数据依赖性，这些数据依赖性在非结构性QR中存在。我们利用同事线性化的特定结构来达到二次复杂性和线性存储要求。除非系数为$ \ | p \ |，否则用于Chebyshev rootinging的（不平衡的）QR迭代不能保证在多项式系数上的向后稳定性。 \大约1 $，几乎从未对近似平滑函数的多项式进行验证。即使所提出的方法在数学上等同于不平衡的QR算法，但我们表明，利用等级结构可以保证多项式上的小落后误差，最多可显式计算的放大因子$ \hatγ_1（p）$，这取决于在考虑的情况下，这取决于多项式。我们表明，此参数几乎总是中等大小，这使得该方法在几个数值测试上的准确性与非结构化不平衡QR中发生的情况相反。
We consider the computation of roots of polynomials expressed in the Chebyshev basis. We extend the QR iteration presented in [Eidelman, Y., Gemignani, L., and Gohberg, I., Numer. Algorithms, 47.3 (2008): pp. 253-273] introducing an aggressive early deflation strategy, and showing that the rank-structure allows to parallelize the algorithm avoiding data dependencies which would be present in the unstructured QR. We exploit the particular structure of the colleague linearization to achieve quadratic complexity and linear storage requirements. The (unbalanced) QR iteration used for Chebyshev rootfinding does not guarantee backward stability on the polynomial coefficients, unless the vector of coefficients satisfy $\|p\| \approx 1$, an hypothesis which is almost never verified for polynomials approximating smooth functions. Even though the presented method is mathematically equivalent to the unbalanced QR algorithm, we show that exploiting the rank structure allows to guarantee a small backward error on the polynomial, up to an explicitly computable amplification factor $\hatγ_1(p)$, which depends on the polynomial under consideration. We show that this parameter is almost always of moderate size, making the method accurate on several numerical tests, in contrast with what happens in the unstructured unbalanced QR.
