Compensated de Casteljau algorithm in K times the working precision

DOI10.1016/J.AMC.2019.03.047MaRDI QIDQ2009574zbMATH OpenOpenAlexWikidataFDO

Authors Danny Hermes

Publication date 29 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

Bernstein polynomialfloating-point arithmeticround-off errorcompensated algorithmerror-free transformationpolynomial evaluation

Mathematics Subject Classification ID

Computer-aided design (modeling of curves and surfaces) (65D17)

Abstract: In computer aided geometric design a polynomial is usually represented in Bernstein form. This paper presents a family of compensated algorithms to accurately evaluate a polynomial in Bernstein form with floating point coefficients. The principle is to apply error-free transformations to improve the traditional de Casteljau algorithm. At each stage of computation, round-off error is passed on to first order errors, then to second order errors, and so on. After the computation has been "filtered" $(K-1)$ times via this process, the resulting output is as accurate as the de Casteljau algorithm performed in $K$ times the working precision. Forward error analysis and numerical experiments illustrate the accuracy of this family of algorithms.

Recommendations

• Accurate evaluation of a polynomial and its derivative in Bernstein form
• Accurate evaluation algorithm for bivariate polynomial in Bernstein-Bézier form
• Algorithms for accurate, validated and fast polynomial evaluation
• Evaluation algorithms for multivariate polynomials in Bernstein-Bézier form
• Accurate evaluation of a polynomial in Chebyshev form

Cites work

• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 3336306 (Why is no real title available?)
• A floating-point technique for extending the available precision
• Accuracy and Stability of Numerical Algorithms
• Accurate Sum and Dot Product
• Accurate evaluation of Bézier curves and surfaces and the Bernstein-Fourier algorithm
• Accurate evaluation of a polynomial and its derivative in Bernstein form
• Algorithms for accurate, validated and fast polynomial evaluation
• Error analysis of corner cutting algorithms
• On the numerical condition of polynomials in Bernstein form
• Running error analysis of evaluation algorithms for bivariate polynomials in barycentric Bernstein form
• \textsf{ORTHOPOLY}: a library for accurate evaluation of series of classical orthogonal polynomials and their derivatives

Cited in

(4)

• Accurate evaluation of a polynomial and its derivative in Bernstein form
• Recursive de Casteljau bisection and rounding errors
• Accurate evaluation algorithm for bivariate polynomial in Bernstein-Bézier form
• Evaluation algorithms for multivariate polynomials in Bernstein-Bézier form

Describes a project that uses

Uses Software

• ORTHOPOLY
• mctoolbox

This page was built for publication: Compensated de Casteljau algorithm in \(K\) times the working precision

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