We consider the prospect of a processor that can perform interval arithmetic at the same speed as conventional floating-point arithmetic. This makes it possible for all arithmetic to be performed with the superior security of interval methods without any penalty in speed. In such a situation the IEEE floating-point standard needs to be compared with a version of floating-point arithmetic that is ideal for the purpose of interval arithmetic. Such a comparison requires a succinct and complete exposition of interval arithmetic according to its recent developments. We present such an exposition in this paper. We conclude that the directed roundings toward the infinities and the definition of division by the signed zeros are valuable features of the standard. Because the operations of interval arithmetic are always defined, exceptions do not arise. As a result neither Nans nor exceptions are needed. Of the status flags, only the inexact flag may be useful. Denormalized numbers seem to have no use for interval arithmetic; in the use of interval constraints, they are a handicap.
For most of the time since the beginning of interval arithmetic, two systems have coexisted. One was the official one, where intervals were bounded, and division by an interval containing zero was undefined. Recognizing the unpracticality of this approach, there was also a definition of extended'' interval arithmetic @cite_5 where these limitations were lifted. Representative of this state of affairs are the monographs by Hansen @cite_4 and Kearfott @cite_0 . However, here the specification of interval division is quite far from an efficient implementation that takes advantage of the IEEE floating-point standard. The specification is indirect via multiplication by the interval inverse. There is no consideration of the possibility of undefined operations: presumably one is to perform a test before each operation.
@cite_0 @cite_5 @cite_4
1504204411 2036740708 2041977310 2103860626
This paper applies interval methods to a classical problem in computer algebra. Let a quantified constraint be a first-order formula over the real numbers. As shown by A. Tarski in the 1930's, such constraints, when restricted to the predicate symbols <, = and function symbols +, ×, are in general solvable. However, the problem becomes undecidable, when we add function symbols like sin. Furthermore, all exact algorithms known up to now are too slow for big examples, do not provide partial information before computing the total result, cannot satisfactorily deal with interval constants in the input, and often generate huge output. As a remedy we propose an approximation method based on interval arithmetic. It uses a generalization of the notion of cylindrical decomposition—as introduced by G. Collins. We describe an implementation of the method and demonstrate that, for quantified constraints without equalities, it can efficiently give approximate information on problems that are too hard for current exact methods. The range of Fourier methods can be significantly increased by extending a nonperiodic function f(x) to a periodic function f? on a larger interval. When f(x) is analytically known on the extended interval, the extension is straightforward. When f(x) is unknown outside the physical interval, there is no standard recipe. Worse still, like a radarless aircraft groping through fog, the algorithm may wreck on the “mountain-in-fog” problem: a function f(x) which is perfectly well behaved on the physical interval may very well have singularities in the extended domain. In this article, we compare several algorithms for successfully extending a function f(x) into the “fog” even when the analytic extension is singular. The best third-kind extension requires singular value decomposition with iterative refinement but achieves accuracy close to machine precision. We show how interval arithmetic can be used in connection with Borsuk's theorem to computationally prove the existence of a solution of a system of nonlinear equations. It turns out that this new test, which can be checked computationally in several different ways, is more general than an existing test based on Miranda's theorem in the sense that it is successful for a larger set of situations. A numerical example is included. We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non commutative arithmetic formulas: the algorithm gets as an input an arithmetic formula in the non-commuting variables x sub i ,...,x sub n and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure arithmetic circuits: the algorithm gets as an input a pure arithmetic circuit (as defined by N. Nisan and A. Wigderson (1996)) in the variables x sub i ,...,x sub n and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by N. Nisan (1991). One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known by N. Nisan and A. Wigderson (1996).