In computational geometry, the construction of essential primitives like convex hulls, Voronoi diagrams and Delaunay triangulations require the evaluation of the signs of determinants, which are sums of products. The same signs are needed for the exa
ct solution of linear programming problems and systems of linear inequalities. Computing these signs exactly with inexact floating point arithmetic is challenging, and we present yet another algorithm for this task. Our algorithm is efficient and uses only of floating point arithmetic, which is much faster than exact arithmetic. We prove that the algorithm is correct and provide efficient and tested C++ code for it.
Two articles published by Information Science discuss the derivatives of interval functions, in the sense of Svetoslav Markov. The authors of these articles tried to characterize for which functions and points such derivatives exist. Unfortunately, t
heir characterization is inaccurate. This article describes this inaccuracy and explains how it can be corrected.
We argue that reducing nonlinear programming problems to a simple canonical form is an effective way to analyze them, specially when the problem is degenerate and the usual linear independence hypothesis does not hold. To illustrate this fact we solv
e an open problem about constraint qualifications using this simple canonical form.
This article presents the Moore library for interval arithmetic in C++20. It gives examples of how the library can be used, and explains the basic principles underlying its design.
We extend the work by Mastroianni and Szabados regarding the barycentric interpolant introduced by J.-P. Berrut in 1988, for equally spaced nodes. We prove fully their first conjecture and present a proof of a weaker version of their second conjectur
e. More importantly than proving these conjectures, we present a sharp description of the asymptotic error incurred by the interpolants when the derivative of the interpolated function is absolutely continuous, which is a class of functions broad enough to cover most functions usually found in practice. We also contribute to the solution of the broad problem they raised regarding the order of approximation of these interpolants, by showing that they have order of approximation of order 1/n for functions with derivatives of bounded variation.
We present the library Moore, which implements Interval Arithmetic in modern C++. This library is based on a new feature in the C++ language called concepts, which reduces the problems caused by template meta programming, and leads to a new approach
for implementing interval arithmetic libraries in C++.
We present fast and accurate ways to normalize two and three dimensional vectors and quaternions and compute their length. Our approach is an adaptation of ideas used in the linear algebra library LAPACK, and we believe that the computational geometr
y and computer aided design communities are not aware of the possibility of speeding up these fundamental operations in the robust way proposed here.
Floating point arithmetic allows us to use a finite machine, the digital computer, to reach conclusions about models based on continuous mathematics. In this article we work in the other direction, that is, we present examples in which continuous mat
hematics leads to sharp, simple and new results about the evaluation of sums, square roots and dot products in floating point arithmetic.
We propose a rational version of the classic Rodrigues rotation formula, which leads to a more accurate and efficient modelling of rotations and their derivatives in finite precision arithmetic. We explain how the rational Rodrigues formula can be us
ed to describe the kinematics of rigid bodies, in a practical example in which we model the rotation of a cell phone using the data obtained from its gyroscope.
We present a new analysis of the stability of extended Floater-Hormann interpolants, in which both noisy data and rounding errors are considered. Contrary to what is claimed in the current literature, we show that the Lebesgue constant of these inter
polants can grow exponentially with the parameters that define them, and we emphasize the importance of using the proper interpretation of the Lebesgue constant in order to estimate correctly the effects of noise and rounding errors. We also present a simple condition that implies the backward instability of the barycentric formula used to implement extended interpolants. Our experiments show that extended interpolants mentioned in the literature satisfy this condition and, therefore, the formula used to implement them is not backward stable. Finally, we explain that the extrapolation step is a significant source of numerical instability for extended interpolants based on extrapolation.
