Remarks on complexity of polynomial and special matrix computations

MaRDI QIDQ1824347zbMATH OpenFDO

Authors Zdeněk Vavřín

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

asymptotic order of complexityHankel matricesLöwner matricesmatrix inversionpolynomial evaluationrational interpolationToeplitz matrices

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Approximation by rational functions (41A20) Numerical interpolation (65D05) Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25)

Review text

The asymptotic order of complexity of the problems of polynomial and rational interpolation, polynomial evaluation and inversion of Löwner and Toeplitz or Hankel matrices is studied. The main result is that the solution of a Löwner matrix has not a larger order than the combination of rational interpolation and polynomial evaluation. There are other inequalities. The author emphasizes that there remains the open problem whether the whole group of the problems has the same order of complexity or not.

Recommendations

• Polynomial evaluation and interpolation on special sets of points
• Inversion formulas and fast algorithms for Löwner-Vandermonde matrices
• Complexity of Computations with Matrices and Polynomials
• scientific article; zbMATH DE number 1405666
• scientific article; zbMATH DE number 3915503

Cites work

• Fast algorithms for rational Hermite approximation and solution of Toeplitz systems
• Hankel and Loewner matrices
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3437485 (Why is no real title available?)
• scientific article; zbMATH DE number 3399806 (Why is no real title available?)
• Inverses of Löwner matrices
• Multiplication of diagonal transforms of Loewner matrices
• Über monotone Matrixfunktionen

Cited in

(5)

• A fast Hankel solver based on an inversion formula for Loewner matrices
• Complexity of computing interval matrix powers for special classes of matrices.
• An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
• Polynomial evaluation and interpolation on special sets of points
• Complexity of Computations with Matrices and Polynomials

This page was built for publication: Remarks on complexity of polynomial and special matrix computations

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