An algebraic approach to approximate evaluation of a polynomial on a set of real points
type: Item
instance of: scholarly article
title: An algebraic approach to approximate evaluation of a polynomial on a set of real points
zbMATH Open document ID: 0836.65022
DOI: 10.1007/BF02431995
published in: Advances in Computational Mathematics
publication date: 1995-10-09T00:00:00Z
review text: Making use of algebraic techniques, the author develops an algorithm to approximate (on a fixed bounded set \(X(m)\) of \(m + 1\) real points) a degree \(n\) polynomial \(p(x) = \sum^n_{i = 0} p_i x^i\), within the error bound \(2^{-u} p\), \(p \leq \sum^n_{i = 0} |p_i|\) for a given positive \(u\). This algorithm decreases the record estimate of the algorithm of \textit{V. Rokhlin} [J. Complexity 4, No. 1, 12-32 (1988; Zbl 0646.65094)] which uses \(O(mu + nu^3)\) (infinite precision) arithmetic operations, to \(O(m \log^2u + n \min \{u, \log n\})\), and also improves other known algorithms for multipoint polynomial evaluation. The algorithm can be performed over abstract rings or fields and is furthermore applicable to algebraic and numerical computing.
Mathematics Subject Classification ID: 65D20
Mathematics Subject Classification ID: 65D15
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 26C10
Mathematics Subject Classification ID: 12Y05
zbMATH DE Number: 803462
zbMATH Keywords: computational complexity
zbMATH Keywords: algorithm
zbMATH Keywords: error bound
zbMATH Keywords: polynomial evaluation
author: Victor Y. Pan
reviewed by: Nácere Hayek
MaRDI profile type: Publication
cites work: Q4314299
cites work: Polynomial division and its computational complexity
cites work: Evaluating polynomials at many points
cites work: Q3359644
cites work: Error Analysis for Polynomial Evaluation
cites work: Fast evaluation and interpolation at the Chebyshev sets of points
cites work: Complexity of Computations with Matrices and Polynomials
cites work: A new approach to fast polynomial interpolation and multipoint evaluation
cites work: A fast algorithm for the discrete Laplace transformation
cites work: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
cites work: Polynomial Interpolation: Lagrange versus Newton
full work available at URL: https://doi.org/10.1007/bf02431995
OpenAlex ID: W2091124791
description: scientific article; zbMATH DE number 803462