Paper Info
Title
Fast Reduction of Generalized Companion Matrix Pairs for Barycentric Lagrange Interpolants.
Abstract
For a barycentric Lagrange interpolant p(z), the roots of p(z) are exactly the eigenvalues of a generalized companion matrix pair (A, B). For real interpolation nodes, the matrix pair (A, B) can be reduced to a pair (H, B), where H has tridiagonal plus rank-one structure. In this paper we propose two fast algorithms for reducing the pair ( A, B) to Hessenberg-triangular form. The matrix pair (A, B) has two spurious infinite eigenvalues, and if the leading coefficients of the interpolant are zero, there will also be other infinite eigenvalues. We propose tools for detecting when the leading coefficients of p(z) are zero, and describe a procedure to deflate all of the infinite eigenvalues from the reduced matrix pair (H, B), while still maintaining the tridiagonal plus rank-one structure of the resulting standard eigenvalue problem. Since fast QR algorithms exist for such structured matrices, the complexity of computing the roots of barycentric Lagrange interpolants could be significantly reduced.
Year
DOI
Venue
2013
10.1137/130904508
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Keywords
Field
DocType
polynomial interpolation,Lagrange interpolation,barycentric formula,generalized companion matrices,polynomial roots,eigenvalue problem,semiseparable matrices
Companion matrix,Tridiagonal matrix,Lagrange polynomial,Mathematical optimization,Polynomial interpolation,Mathematical analysis,Matrix (mathematics),Properties of polynomial roots,Mathematics,Eigenvalues and eigenvectors,Barycentric coordinate system
Journal
Volume
Issue
ISSN
34
3
0895-4798
Citations 
PageRank 
References 
4
0.49
0
Authors
1
Name
Order
Citations
PageRank
Piers W. Lawrence1214.77