Interval Arithmetic with Containment Sets

The idea of containment sets (csets) is due to Walster and Hansen, and the theory is mainly due to the first author. Now that floating point computation with infinities is widely accepted, it is necessary to achieve the same for interval computation. The cset of a function over a set in its domain space is the set of all limits of normal function values over that set. Csets form a sound basis for defining a number of practical models for interval arithmetic that handle division by zero and related operations in an intuitive and consistent manner. Cset-based systems offer new opportunities for compiler optimization by rearranging interval expressions, achieving tighter bounds by reducing dependencies within the expression. This paper presents basic theory. It discusses division by zero, the case for a global flag to support ``loose' evaluation, performance, and semantics. It presents numerical examples using a trial Matlab implementation.     

Horner's Rule for Interval Evaluation Revisited

Interval arithmetic can be used to enclose the range of a real function over a domain. However, due to some weak properties of interval arithmetic, a computed interval can be much larger than the exact range. This phenomenon is called dependency problem. In this paper, Horner's rule for polynomial interval evaluation is revisited. We introduce a new factorization scheme based on well-known symbolic identities in order to handle the dependency problem of interval arithmetic. The experimental results show an improvement of 25% of the width of computed intervals with respect to Horner's rule. Received December 14, 2001; revised March 27, 2002 Published online: July 8, 2002     

A Generalized Kahan-Babuška-Summation-Algorithm

In this article, we combine recursive summation techniques with Kahan-Babuška type balancing strategies [1], [7] to get highly accurate summation formulas. An i-th algorithm have only error beyond 1upl and thus allows to sum many millions of numbers with high accuracy. The additional afford is a small multiple of the naive summation. In addition we show that these algorithms could be modified to provide tight upper and lower bounds for use with interval arithmetic.     

Hardware Support for Interval Arithmetic

A hardware unit for interval arithmetic (including division by an interval that contains zero) is described in this paper. After a brief introduction an instruction set for interval arithmetic is defined which is attractive from the mathematical point of view. These instructions consist of the basic arithmetic operations and comparisons for intervals including the relevant lattice operations. To enable high speed, the case selections for interval multiplication (9 cases) and interval division (14 cases) are done in hardware. The lower bound of the result is computed with rounding downwards and the upper bound with rounding upwards by parallel units simultaneously. The rounding mode must be an integral part of the arithmetic operation. Also the basic comparisons for intervals together with the corresponding lattice operations and the result selection in more complicated cases of multiplication and division are done in hardware. There they are executed by parallel units simultaneously. The circuits described in this paper show that with modest additional hardware costs interval arithmetic can be made almost as fast as simple floating-point arithmetic.     

Stets konvergente Verfahren höherer Ordnung zur Berechnung von reellen Nullstellen

In this paper we give always convergent higher order methods for the computation of a real zero of a real function which has derivatives of sufficiently high order. The principle of constructing these methods consists in a generalization of that used by Ehrmann [5]. By making appropriate use of interval arithmetic we always can assure convergence.     

Extended interval Newton method based on the precise quotient set

The interval Newton method can be used for computing an enclosure of a single simple zero of a smooth function in an interval domain. It can practically be extended to allow computing enclosures of all zeros in a given interval. This paper deals with the extended interval Newton method. An essential operation of the method is division by an interval that contains zero (extended interval division). This operation has been studied by many researchers in recent decades, but inconsistency in the research has occurred again and again. This paper adopts the definition of extended interval division redefined in recent documents (Kulisch in Arithmetic operations for floating-point intervals, 2009; Pryce in P1788: IEEE standard for interval arithmetic version 02.2, 2010). The result of the division is called the precise quotient set. Earlier definitions differ in the overestimation of the quotient set in particular cases, causing inefficiency in Newton’s method and even leading to redundant enclosures of a zero. The paper reviews and compares some extended interval quotient sets defined during the last few decades. As a central theorem, we present the fundamental properties of the extended interval Newton method based on the precise quotient set. On this basis, we develop an algorithm and a convenient program package for the extended interval Newton method. Statements on its convergence are also given. We then demonstrate the performance of the algorithm through nine carefully selected very sensitive numerical examples and show that it can compute correct enclosures of all zeros of the functions with high efficiency, particularly in cases where earlier methods are less effective.     

Multiple/arbitrary precision interval computations in C-XSC

As a new feature, C-XSC provides so-called wrapper classes to some external arbitrary precision real and interval packages. Operator and function name overloading is used to give the user easy access to the arithmetic operations and mathematical functions provided by the underlying Ansi C packages. We will discuss briefly so-called staggered precision arithmetics based on exact scalar products. Such an arithmetic is available in C-XSC e.g. for multiple precision complex intervals. We also discuss the usage of the arbitrary precision arithmetic packages MPFR and MPFI, which are now accessible conveniently from within C-XSC via class interfaces. As a typical application, we will present an arbitrary precision interval Newton method to find the root(s) of a continuously differentiable function in a prescribed domain. The user only has to supply the expression for the function in the usual mathematical notation. The derivative needed in the interval Newton operator is computed using automatic differentiation based on the arbitrary precision interval operations. To demonstrate the power of the package we compute an enclosure of the zero of a model problem with guaranteed accuracy of more than 10 million decimal digits.     

Ultra-arithmetic II: intervals of polynomials

In Part 1 of this paper (Function Data Types) we developed ultra-arithmetic. a calculus for functions which is performable on a digital computer. Here in analogy with the notion of interval arithmetic for intervals of reals we begin the development of an interval arithmetic for functions. The operations of addition, subtraction, multiplication, division, integration and differentiation for intervals of polynomials are defined and studied. In certain cases simplified isotonal approximations to the resultant interval as well as error analyses are also given.     

PROFIL/BIAS—A fast interval library

The interval data type is currently not supported in common programming languages. Therefore the implementation of algorithms using interval arithmetic requires special programming environments or at least special libraries. In this paper we present the C++ class library PROFIL which provides a user friendly environment for implementing interval algorithms. The main goals in the design of PROFIL were speed and portability. Therefore all interval operations in PROFIL use BIAS (Basic Interval Arithmetic Subroutines) [16]. BIAS defines a concise and portable interface for the basic scalar, vector, and matrix operations. The interface is independent of a specific interval representation or computation but permits machine specific and fast implementations. Based on this general specification we present an implementation in C using a lower/upper bound representation of intervals and directed roundings. By using few assembler instructions for switching the rounding modes and avoiding sign tests and rounding mode switches wherever possible, the computational costs of the interval operations were reduced significantly. This is especially important for RISC machines, where floating point instructions can be executed in few machine cycles. Comparisons with other interval arithmetic packages show an improvement in speed of about one order of magnitude.     

A Relation Between Morphological and Interval Operations

In our work we show that the operations of interval algebra can be expressed by morphological operations on an appropriately chosen lattice defined over the set of intervals on the real line, when regarding real interval arithmetic, and in the complex plane, when regarding complex interval arithmetic. Using the morphological representation of the interval operations, a generalization of the additive interval operations over the family of compact convex sets in Rn is considered.     

The Set of Hausdorff Continuous Functions— The Largest Linear Space of Interval Functions

Hausdorff continuous (H-continuous) functions are special interval-valued functions which are commonly used in practice, e.g. histograms are such functions. However, in order to avoid arithmetic operations with intervals, such functions are traditionally treated by means of corresponding semi-continuous functions, which are real-valued functions. One difficulty in using H-continuous functions is that, if we add two H-continuous functions that have interval values at same argument using point-wise interval arithmetic, then we may obtain as a result an interval function which is not H-continuous. In this work we define addition so that the set of H-continuous functions is closed under this operation. Moreover, the set of H-continuous functions is turned into a linear space. It has been also proved that this space is the largest linear space of interval functions. These results make H-continuous functions an attractive tool in real analysis and provides a bridge between real and interval analysis.     

Computing Interval Enclosures for Definite Integrals by Application of Triple Adaptive Strategies

In addition to the well-known and widely-used adaptive strategies for region subdivision and the choice of local quadrature rules, there still exists a third possibility for doing numerical integration adaptively, when interval computation is considered. Based on the Peano's kernels theorem and interval arithmetic, we are able to estimate the truncation error of a quadrature rule by means of different derivatives of the integrand, where the available orders of the derivatives depend on the degree of smoothness of the integrand and the exactness degree of the underlying quadrature rule. We classify the methods as the adaptive orders strategies, if they make use of the derivatives of different orders to improve each single local error estimation. In this paper, alternatives for adaptive error estimation are discussed. Moreover, a practical way for realization of the optimal error estimation is suggested. Numerical results for integrands of different classes as well as numerical comparisons of different methods are given.     

T-sum of sigmoid-shaped fuzzy intervals

The usual arithmetic operations on real numbers can be extended to arithmetical operations on fuzzy intervals by means of Zadeh’s extension principle based on a t-norm T. A t-norm is called consistent with respect to a class of fuzzy intervals for some arithmetic operation, if this arithmetic operation is closed for this class. It is important to know which t-norms are consistent with particular types of fuzzy intervals. Recently, Dombi and Gy?rbíró [J. Dombi, N. Gy?rbíró, Additions of sigmoid-shaped fuzzy intervals using the Dombi operator and infinite sum theorems, Fuzzy Sets and Systems 157 (2006) 952-963] proved that addition is closed if the Dombi t-norm is used with sigmoid-shaped fuzzy intervals. In this paper, we define a broader class of sigmoid-shaped fuzzy intervals. Then, we study t-norms that are consistent with these particular types of fuzzy intervals. Dombi and Gy?rbíró’s results are special cases of the results described in this paper.     

Specification of hardware for interval arithmetic

Interval arithmetic, as it is standardized by the IEEE working group P1788 can be implemented by using floating point arithmetic units with directed rounding modes. The easiest way to represent an interval is by its two bounds. Simple formulas for the arithmetic operations can be applied. Our goal is to perform interval operations as fast as their floating point counterparts. Hence, we provide at least two units per operation. We also specify the operation for reverse multiplication (Neumaier in Vienna proposal for interval standardization, 2008) which can be implemented with the division unit. In this paper we do not care about optimization. Our primary intention is to give an easily understandable specification of hardware for interval arithmetic.     

Efficient multiple-precision integer division algorithm

Design and implementation of division algorithm is one of the most complicated problems in multi-precision arithmetic. Huang et al. [1] proposed an efficient multi-precision integer division algorithm, and experimentally showed that it is about three times faster than the most popular algorithms proposed by Knuth [2] and Smith [3]. This paper reports a bug in the algorithm of Huang et al. [1], and suggests the necessary corrections. The theoretical correctness proof of the proposed algorithm is also given. The resulting algorithm remains as fast as that of [1].     

A comparison of some methods for bounding connected and disconnected solution sets of interval linear systems

Summary Finding bounding sets to solutions to systems of algebraic equations with uncertainties in the coefficients, as well as rapidly but rigorously locating all solutions to nonlinear systems or global optimization problems, involves bounding the solution sets to systems of equations with wide interval coefficients. In many cases, singular systems are admitted within the intervals of uncertainty of the coefficients, leading to unbounded solution sets with more than one disconnected component. This, combined with the fact that computing exact bounds on the solution set is NP-hard, limits the range of techniques available for bounding the solution sets for such systems. However, the componentwise nature and other properties make the interval Gauss–Seidel method suited to computing meaningful bounds in a predictable amount of computing time. For this reason, we focus on the interval Gauss–Seidel method. In particular, we study and compare various preconditioning techniques we have developed over the years but not fully investigated, comparing the results. Based on a study of the preconditioners in detail on some simple, specially–designed small systems, we propose two heuristic algorithms, then study the behavior of the preconditioners on some larger, randomly generated systems, as well as a small selection of systems from the Matrix Market collection.      

An Application of Interval Methods to Stock Market Forecasting

Stock market forecasting has been a challenging financial research topic for decades. In the literature, there are numerous results based on point methods. However, poor forecasting quality has been a continuous problem. Motivated by the fact that financial data varies within intervals, we apply interval methods on a well known stock pricing model [3] to predict stock market variability as intervals. Empirical results obtained with a few different approaches in this paper consistently suggest that interval forecasts have better overall quality than traditional point forecasts.     

Frequency domain conditions for strictly positive real functions

Frequency domain conditions for strictly positive real (SPR) functions which appear in literature are often only necessary or only sufficient. This point is raised in [1], [2], where necessary and sufficient conditions in thes-domain are given for a transfer function to be SPR. In this note, the points raised in [1], I2] are clarified further by giving necessary and sufficient conditions in the frequency domain for transfer functions to be SPR. These frequency-domain conditions are easier to test than those given in thes-domain or time domain [1], [2].     

Complex Interval Arithmetic Using Polar Form

In this paper, the polar representation of complex numbers is extended to complex polar intervals or sectors; detailed algorithms are derived for performing basic arithmetic operations on sectors. While multiplication and division are exactly defined, addition and subtraction are not, and we seek to minimize the pessimism introduced by these operations. Addition is studied as an optimization problem which is analytically solved. The complex interval arithmetic thus defined is illustrated with some numerical examples which show that in many applications, the polar representation is more advisable.