Compensated de Casteljau algorithm in K times the working precision

DOI10.1016/J.AMC.2019.03.047zbMATH Open1429.65037arXiv1808.10387OpenAlexW2889493128WikidataQ128120555 ScholiaQ128120555MaRDI QIDQ2009574FDOQ2009574

Authors: Danny Hermes 

Publication date: 29 November 2019

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

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.

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

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

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)

Cites Work

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

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

Uses Software

• mctoolbox
• ORTHOPOLY

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)