Back
2024INF018
Doctoral thesis

Numerical stability of barycentric interpolation

  • 2024

PhD: Università della Svizzera italiana

Numerical stability
Rounding errors
Floating-point arithmetic
Barycentric rational interpolation
C++ class template
Mean value coordinates
Rational Bézier curves
English In the field of Numerical Analysis, it is common practice to solve an arbitrary mathematical problem through the implementation of a numerical algorithm on a computer. Since not all data of a problem can be represented exactly on a computer as floating-point numbers, it can happen that the algorithm starts with rounding errors already from the initial set of input that then propagate throughout the process. Consequently, it is important to study the numerical stability of an algorithm, that is, its behaviour with respect to the propagation of the errors that occur during the arithmetic operations executed by the computer. In this dissertation we focus on the barycentric interpolation problem, both in the univariate and the bivariate setting. In the first case, we theoretically discuss the numerical stability of all algorithms that implement a barycentric rational interpolant, providing conditions under which it is possible to know a priori whether they are stable. In the second case, we focus on the barycentric interpolant defined on a planar polygon, and this leads to the study of the numerical stability of generalized barycentric coordinates, particularly the mean value coordinates. In the first part, we analyse the numerical stability of the algorithms that compute univariate barycentric rational interpolants. We begin by showing more generally that the evaluation of any function that can be expressed as r(x)=(\sum_{i=0}^n a_i(x) f_i) /(\sum_{j=0}^m b_j(x)) in terms of data values f_i and some functions a_i and b_j for i=0,…,n and j=0,…,m is forward and backward stable under certain assumptions. The proof considers the simplest and classical algorithm that involves summing the terms in the numerator and denominator first, followed by a final division. This result includes the two barycentric forms of rational interpolation as special cases. Our analysis further reveals that the stability of the second barycentric form depends on the Lebesgue constant associated with the interpolation nodes, which typically grows with n, whereas the stability of the first barycentric form depends on a similar, but different quantity, that can be bounded in terms of the mesh ratio, regardless of n. We support our theoretical results with numerical experiments. These findings contribute to the development of a new C++ class, named BRI (Barycentric Rational Interpolation), which contains all variables and functions related to linear barycentric rational interpolation. This class is designed to autonomously select the best method to use on a case-by-case basis, as it takes into account our theoretical results regarding the efficiency and numerical stability of barycentric rational interpolation. Moreover, we describe a new technique that makes the code robust and less prone to overflow and underflow errors. In addition to the standard C++ data types, the BRI template variables can also be defined with arbitrary precision, because the BRI class is compatible with the Multiple Precision Floating-Point Reliable (MPFR) library. The second part of the thesis focuses on the numerical stability of algorithms that compute generalized barycentric coordinates on polygons with more than three vertices. Among the different constructions proposed, mean value coordinates have emerged as a popular choice, particularly due to their suitability for the non-convex setting. Since their introduction, they have found applications in numerous fields, and several equivalent formulas for their evaluation have been presented in the literature. However, so far, there has been no study regarding their numerical stability. We show that all the known methods exhibit instability in some regions of the domain. To address this problem, we introduce a new formula for computing mean value coordinates, explain how to implement it, and formally prove that our new algorithm provides a stable evaluation of mean value coordinates. We finally validate our results through numerical experiments. Lastly, since the results of the first part can be applied to a broad range of numerical methods, we examine several algorithms used for evaluating Bézier curves. The de Casteljau algorithm is the first method introduced for evaluating polynomial Bézier curves, later also generalized to the rational case and surfaces. Although it presents an elegant definition through convex combinations and generally yields stable results, it has quadratic time complexity. This represents a significant limitation, especially when dealing with high-degree curves and real-time applications. For this reason, numerous studies have been conducted in order to provide alternative approaches and more efficient algorithms. We present a collection of the most commonly used algorithm in the state-of-the-art and provide a comparison of their numerical stability. Notably, although some error analyses exist only for some specific algorithm, the literature lacks an in-depth investigation into the numerical stability of all these methods, along with a corresponding comparison. Therefore, this represents the first comprehensive study of its kind.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1330791
Statistics
Document views: 25 File downloads:
  • 2024INF018.pdf: 56