Fast and accurate con-eigenvalue algorithm for optimal rational approximations

DOI10.1137/110821901MaRDI QIDQ4918156zbMATH OpenOpenAlexFDO

Authors Gregory Beylkin, Terry Haut

Publication date 23 April 2013

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3196

zbMATH Keywords

con-eigenvalue problemhigh relative accuracyoptimal rational approximations

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of matrix norms, conditioning, scaling (65F35) (H^infty)-control (93B36)

Abstract: The need to compute small con-eigenvalues and the associated con-eigenvectors of positive-definite Cauchy matrices naturally arises when constructing rational approximations with a (near) optimally small $L^{infty}$ error. Specifically, given a rational function with $n$ poles in the unit disk, a rational approximation with $mlln$ poles in the unit disk may be obtained from the $m$th con-eigenvector of an $nimesn$ Cauchy matrix, where the associated con-eigenvalue $lambd{a}_m>0$ gives the approximation error in the $L^{infty}$ norm. Unfortunately, standard algorithms do not accurately compute small con-eigenvalues (and the associated con-eigenvectors) and, in particular, yield few or no correct digits for con-eigenvalues smaller than the machine roundoff. We develop a fast and accurate algorithm for computing con-eigenvalues and con-eigenvectors of positive-definite Cauchy matrices, yielding even the tiniest con-eigenvalues with high relative accuracy. The algorithm computes the $m$th con-eigenvalue in $mathcalO(m^{2}n)$ operations and, since the con-eigenvalues of positive-definite Cauchy matrices decay exponentially fast, we obtain (near) optimal rational approximations in $mathcalO(n(logdelt{a}^{-1}{)}^2)$ operations, where $delta$ is the approximation error in the $L^{infty}$ norm. We derive error bounds demonstrating high relative accuracy of the computed con-eigenvalues and the high accuracy of the unit con-eigenvectors. We also provide examples of using the algorithm to compute (near) optimal rational approximations of functions with singularities and sharp transitions, where approximation errors close to machine precision are obtained. Finally, we present numerical tests on random (complex-valued) Cauchy matrices to show that the algorithm computes all the con-eigenvalues and con-eigenvectors with nearly full precision.

Recommendations

• Rational approximations from power series of vector-valued meromorphic functions
• Fast approximate computations with Cauchy matrices, polynomials and rational functions
• scientific article; zbMATH DE number 2065333
• Accurate computations for eigenvalues of products of Cauchy-polynomial-Vandermonde matrices
• Accurate bidiagonal decomposition of totally positive Cauchy-Vandermonde matrices and applications

Cited in

(11)

• Spherical Bessel transform via exponential sum approximation of spherical Bessel function
• On computing distributions of products of non-negative independent random variables
• Computation of adaptive Fourier series by sparse approximation of exponential sums
• Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices
• \textsc{mxpfit}: a library for finding optimal multi-exponential approximations
• Near optimal rational approximations of large data sets
• On computing distributions of products of random variables via Gaussian multiresolution analysis
• Evaluation of small elements of the eigenvectors of certain symmetric tridiagonal matrices with high relative accuracy
• Efficient representation and accurate evaluation of oscillatory integrals and functions
• Data-driven algorithms for signal processing with trigonometric rational functions
• Consimilarity of quaternions and coneigenvalues of quaternion matrices

This page was built for publication: Fast and accurate con-eigenvalue algorithm for optimal rational approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4918156)