Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials

详细信息	查看全文 | 推荐本文 |

• 作者：James Demmel and Plamen Koev
• 关键词：Vandermonde matrix ; High relative accuracy ; Singular value decomposition ; Orthogonal polynomial
• 刊名：Linear Algebra and its Applications
• 出版年：2006
• 期刊代码：38_00243795
• 类别：mt
• 出版时间：1 September 2006
• 卷：417
• 期：2-3
• 页码：382-396
• 文件大小：178 K

摘要

We present a new O(n³) algorithm for computing the SVD of an n × n polynomial Vandermonde matrix V_P = [P_i−1(x_j)] to high relative accuracy in O(n³) time. The P_i are orthonormal polynomials, deg P_i = i, and x_j are complex nodes. The small singular values of V_P can be arbitrarily smaller than the largest ones, so that traditional algorithms typically compute them with no relative accuracy at all.

We show that the singular values, even the tiniest ones, are usually well-conditioned functions of the data x_j, justifying this computation.

We also explain how this theory can be extended to other polynomial Vandermonde matrices, involving polynomials that are not orthonormal or even orthogonal.