An Overview of the Upcoming IEEE P-1788 Working Group Document: Standard for Interval Arithmetic

Please download to get full document.

View again

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Taxes & Accounting

Published:

Views: 2 | Pages: 6

Extension: PDF | Download: 0

Share
Related documents
Description
An Overview of the Upcoming IEEE P-1788 Working Group Document: Standard for Interval Arithmetic Ralph Baker Kearfott Department of Mathematics University of Louisiana at Lafayette Lafayette, Louisiana
Transcript
An Overview of the Upcoming IEEE P-1788 Working Group Document: Standard for Interval Arithmetic Ralph Baker Kearfott Department of Mathematics University of Louisiana at Lafayette Lafayette, Louisiana Abstract We provide a summary of the goals, underlying philosophy, work, decisions, product, and completion schedule of the IEEE P-1788 working group on interval arithmetic. I. INTRODUCTION Interval arithmetic, invented several times during the early twentieth century and rising to prominence with Ramon Moore s initial work [16], [17], [18], has had a consistent presence within the scientific computing world during the past 50 years. Publicly available software packages, as well as several hardware implementations, have been available throughout this time span, and continue to be developed, for platforms and languages such as Fortran 66, Fortran 77, Fortran 90 and 2003, C, C++, Matlab, Mathematica, Maple, Java, etc. It also is not uncommon for developers of higherlevel packages to supply their own interval arithmetic. A partial list of interval arithmetic software and packages using or built upon interval arithmetic can be found on the web page [12]. Some of our own work containing basic introductions to interval arithmetic, as well as tutorials on certain packages and further references, is in [10], [19]. Some articles describing applications relating interval computations and soft computing appear in [9]. Several hundred researchers presently identify themselves as experts in interval computations. However, with a solid scholarly literature and web presence, many others, initially unknown to the core interval community, are experimenting with interval arithmetic or are incorporating it into their projects. A basic goal of interval arithmetic is to take account of both uncertainties in input data and roundoff errors in floating point computations in a mathematically rigorous way 1. This leads to the ability to use floating point computations to provide mathematical proofs of appropriately posed assertions, to provide guarantees that a system subject to manufacturing uncertainties will remain within performance bounds, etc. Such proofs are largely effected by computing mathematically rigorous upper and lower bounds on the range of a function over 1 However, some useful applications of interval arithmetic, such as [8], among them fuzzy applications such as in [9] are non-rigorous computations. hyper-rectangles, using the fundamental theorem of interval arithmetic: Theorem 1: (Fundamental Theorem of Interval Arithmetic) Suppose f(x 1,, x n ) is an expression of n variables built from the four basic arithmetic operations addition, subtraction, multiplication, and division, and other functions ϕ of one or more variables, collectively called library functions. Suppose interval evaluations ϕ(x) of the library functions ϕ are defined such that ϕ(x) contains the range of ϕ over x. Then the interval evaluation f(x) obtained by replacing each arithmetic operation and library function by the corresponding interval version contains the range of f over x. Proofs utilizing the fundamental theorem of interval arithmetic perhaps even have legal implications, but will be correct only if the software utilizing interval arithmetic is bug-free. Also, such software is more likely to be available if it is reasonably portable. These goals are more easily attained if the underlying system is standardized in a logical, complete way that is as simple as possible. Furthermore, programmers and implementers are less likely to make mistakes or misinterpret results if different interval arithmetic systems behave in the same, known way. II. WHY ISN T STANDARDIZATION TRIVIAL? Basic interval arithmetic can be specified with simple, welldefined rules. For example, addition and multiplication for non-empty bounded intervals can be characterized by [x, x] + [y, y] = [x + y, x + y] and (1) [x, x] [y, y] = [ min { xy, xy, xy, xy }, max { xy, xy, xy, xy }], with analogous operations for subtraction and division. Within common floating environments, it is even straightforward to unambiguously define the computer-generated results corresponding to (1). For example, to ensure interval versions of the four basic operations contain the actual ranges of those operations, it is sufficient to round the floating point computation of the lower bound (such as in (1)) down and the upper bound up. In IEEE-754 arithmetic [14], this can be effected in an optimally tight way with the standard rounding modes: One simply sets the rounding mode to down when computing the lower end point of the result and the rounding mode to up when computing the upper end point. Since this method of proceeding is seemingly so clear, why are there challenges and controversy in standardization of interval arithmetic? The following issues come to the forefront. Evaluation over partial domains: Even though the result of an individual arithmetic operation is a very close approximation to the actual range of that operation (and rigorously contains the range), combining a sequence of such operations to evaluate an expression gives an interval that only contains the range, often with considerable overestimation beyond that due simply to roundoff error 2. For example, suppose we wish to evaluate E(x) = x 2 + x + 1 over x = [ 1, 1]. The exact range of e(x) = x 2 + x + 1 over [ 1, 1] is [0.75, 3], while an interval evaluation, using [ 1, 1] 2 = [0, 1], gives e(x) = [ 1, 1] 2 + [ 1, 1] + 1 = [ 1, 3]. When we subsequently take the square root of this expression, we are left with the problem of evaluating a square root over an interval that contains zero. If we are interested only in the range of E over x, we may ignore the negative part, and return [0, 3] = [0, 3] (or the smallest floating point interval containing this interval) for E(x). In many contexts, such continuation of the evaluation over the intersection of the input interval with the domain is permissible. However, in some contexts, it is not. For example, the Brouwer fixed point theorem states that if G is a continuous function over a compact set x (such as an interval vector) and the range of G over x is contained in x, then there is a fixed point x x, x = G(x ). Since the interval evaluation G(x) contains the range of G over x, G(x) x leads to the conclusion G has a fixed point in x. However, if, we take we would obtain G(x) = x 2 1 and x = [ 2, 2], G(x) = [ 1, 3] = [0, 3] [ 2, 2], and we would conclude G had a fixed point in [ 2, 2], an incorrect conclusion. (To see this, note that x 2 1 = x implies x 2 1 = x 2, from which 1 = 0; thus, G can have no fixed points.) The standard needs to somehow accommodate evaluation over partial domains, while raising an exception when needed. Exceptions in general: The working group has devoted a significant amount of effort discussing the types of exceptions that can occur, which must be tracked, and how to track them efficiently; see the synopsis for Motion 36 in the next section. Extended arithmetic: Conceptually, the result of a single arithmetic operation is defined to be the range of that operation 2 This is due to the dependency problem. See any good elementary introduction to interval arithmetic, such as [19, Section 5.2, p. 38] for an explanation. over the input intervals. This is not a problem for interval division when the denominator is an interval that does not contain zero, but is a problem when it does. Furthermore, due to overestimation, the actual range of a denominator may not contain zero, while the interval evaluation does. If we consider to be part of the number system, that is, if we consider the underlying set to be the two-point compactification R of the real numbers, the interval evaluation of, say, 1/[0, 1] might be construed to be set of two disjoint intervals [, ] [1, ]. In contrast, if the underlying system is simply the set of real numbers R, the quantity 1/0 is not defined, and 1/[0, 1] can only be defined over a partial domain. In this case, a logical definition would be 1/[0, 1] = [1, ). In the former case, the single smallest interval containing the range would be the entire set of extended reals [, ]. For other interval pairs, such as [1, 2]/[ 1, 1], two disjoint intervals, namely (, 1/2] [1/2, ), seem inevitable whether or not the underlying set is assumed to be R or R. It is sometimes useful for the program or application to know both parts of the range, but may also be convenient to simply return an interval containing the union of the parts, and it is appropriate in some contexts to raise or signal an exception. For consistency but also utility, the standard needs to specify interval division. Extensions of the elementary functions: The functions ϕ in Theorem (1) typically are the functions such as sin, cos, exp, asin, etc. usually accessible with common scientific programming languages such as C++ and Fortran. If ϕ is such a function, the logical interval value for ϕ(x) (where x is an interval vector) would be the narrowest floating point interval containing the mathematical range of ϕ over x. However, for some ϕ and x, it may be difficult to return this optimal range with a reasonable cost. Furthermore, analogously to division, standard functions such as the inverse trigonometric functions and square roots have points where they are undefined and can have inverse images consisting of more than one connected component. A consistent, well-documented and universally available way of handling such situations, flexible enough for all common applications should therefore be defined. Alternative systems: With one or two exceptional situations, the IEEE-754 standard data types and rounding modes can be combined naturally with intervals represented in terms of lower bound and upper bound and arithmetic defined such as in (1), with the rules clearly and simply specified. The IEEE 754 standard even provides specification for the accuracy of elementary functions that can be used in an interval standard (subject to the exception handling and need for additional specification we have listed). However, other representations and underlying systems are in use today in various applications. Some of these are multiple and variable precision interval arithmetic such as in [23], representation in terms of midpoint and radius ( mid-rad arithmetic) 3 such as in [24], and modal or Kaucher arithmetic 4 such as in [2], [6], [21], [7], [7] or in fuzzy computing [25]. The standardization process has needed to decide how much and how to standardize such systems, common features and consistency of these systems, and conversion between representations in these systems. Reproducibility: Is it practical to specify the arithmetic in the standard in such a way that the same computation carried out on two different systems conforming to the standard always give the same result? Is such reproducibility desirable? The IEEE P-1788 working group discussed such issues in its mailing list [13]. Two main sources that prohibit reproducibity are compiler optimizations and accuracy requirements. Guaranteeing high accuracy in all cases can require either special hardware or extensive computing time, while effcient softwareimplementable methods exist that will guarantee the result is within one or two floating point numbers of the exact result; However, specifying an operation to such a relaxed accuracy does not guarantee reproducibility. For example the IEEE 754R floating point standard [14, Section 11] gives requirements for reproducible results, to be available with an optional reproducibility mode. This issue has been the subject of P-1788 working group discussion. Accurate dot product: A special (and controversial) operation tied with tight enclosures of exact results in linear algebra operations is the accurate dot product. In particular, there are ways of computing the dot product v w such that the computed result is the nearest machine number to the exact result. Guaranteeing such accuracy in the worst case can require either special hardware or extensive computing time, while efficient software-implementable methods exist that will guarantee the result is within one or two floating point numbers of the exact result; however, specifying an operation to such a relaxed accuracy does not guarantee reproducibility. The IEEE P-1788 working group has dealt with inclusion of a dot product specification of exact or relaxed accuracy; see the synopsis for Motion 9 in the next section. After giving a brief history of interval standardization efforts, we present an overview of the present state of the standards document and how these issues have been resolved. III. A SHORT HISTORY The author participated in a relatively early effort at standardization through a formally sanctioned committee in the mid 1990 s, in the ANSI X3J3 / ISO WG5 working groups on Fortran standardization. A working document was produced, but a consensus could not be reached, particularly within the community of experts on interval computation, and the Fortran working group needed to focus on other issues. 3 more efficient for certain matrix operations 4 efficiently implemented and also useful for obtaining inner estimations, that is, intervals guaranteed to be contained in the range, and a coherent algebraic system Slightly after and overlapping with the Fortran standardization effort, Chenyi Hu, Jürgen Wolff von Gudenberg, Michael Nooner and others produced a document in the BLAST forum, an organization for standardizing the level-1, level-2, and level- 3 Basic Linear Algebra Subroutines for modern computer architectures [5], [1]; a C++ implementation is described in [20]. Somewhat later (in the mid 2000 s), Ulrich Kulisch led an effort within the IFIP (International Federation for Information Processing) Working Group 2.5 on Numerical Software to develop a recommendation for interval arithmetic within the eventual IEEE standard. Simultaneously, the Interval Subroutine Library (ISL) working group studied interval arithmetic standardization [22]. Due to timing and also the inability of highly interested participants to attend certain crucial working group meetings, action was not taken within the P-754 working group. However, Prof. Kulisch s efforts have formed the basis for the present IEEE P-1788 working group, officially approved to develop a separate interval standard in Simultaneously with Prof. Kulisch s effort, Hervé Brönnimann, Guillaume Melquiond, and Sylvain Pion led an effort within the ISO/IEC JTC1/SC22/WG21 committee (International Standards Organization working group on standardization of C++) to specify a standard library for interval arithmetic, based on the BOOST library for interval arithmetic in C++ [15], [3]. The author of this article, along with George Corliss, Ned Nedialkov, John Pryce, and Spencer Smith participated in this as part of the focus of the ISL (Interval Subroutine Library) project [4]. The IEEE P-1788 working group first planning meeting occurred in January, 2008 at Schloss Dagstuhl Seminar 08021, Numerical Validation in Current Hardware Architectures, and the PAR (Project Authorization Request) was officially approved on June 12, 2008, for a four year work period, with Nathalie Revol as chair. A two-year extension was approved in 2012, for an completion-of-work date by December 31, IV. CURRENT STATUS OF THE STANDARD As of the writing of this article, the committee is still processing motions, and the standards document is still under development, and subject to change. However, we summarize decisions (successful motions) that have been made as well as the current state. We present the summary in the order in which corresponding motions were made Notation: The notation used in the standards document will be as in [11]. 2. Structure: An agreement on the overall structure of the document, largely borrowed from the IEEE-754 standard. 3. Sets of reals: The P1788 Interval arithmetic standard defines intervals as closed and connected sets of real numbers. That means that ± may be used as bounds of an interval but are never considered 5 We also give motion numbers. as members of an interval. In particular, this has implications for the results of division by intervals that contain zero, as explained in the introduction to this article. 5. The basic operations: A four-page report giving explicit rules for computing the results of the four basic operations, including handling of unbounded intervals such as [2, 3] [1, ) and explicitly prescribing rounding modes to be used, was approved. 6. Formats (now interval types ): An 8-page report was adopted. Therein, it states that multiple formats will be supported within the 1788 document, and that an implementation must support at least one format. A special 754-conforming format is defined, as well as general terminology for formats. A basic idea is that different interval formats correspond to different floating point formats (such as single, double, decimal), through the representation of their end points. However, interval formats can go beyond that, such as representation by a midpoint and radius or representation of an interval [a, b] by [ a, b]. (In this last format, operations on the lower and upper bounds can proceed without a change of rounding mode.) Clarifying definitions are made, and conversions shall be provided between all supported interval formats. 8. Exception handling: Exception handling will be provided through the concept of decorations. A decoration is an interval datum with extra bits giving information about the computation leading to the datum. For example, a decoration for the interval [0, 3] resulting from computing [ 1, 3] would carry information that at least one operation in the chain leading to [0, 3] had an argument partially outside its domain. The standard is to require bare intervals (without decorations), bare decorations, and decorated intervals. A rough analogue in IEEE 754 is the NaN: the NaN can be viewed as a rudimentary form of a bare decoration. 9. Exact dot product: A standard-conforming interval arithmetic implementation shall include an exact dot product. 10. Elementary functions: A table of required elementary functions and a table of additional recommended functions has been approved. 12. Inner addition and subtraction: In ordinary interval arithmetic, [ 1, 1] [ 1, 1] = [ 2, 2] 0, since the first [ 1, 1] doesn t necessarily represent the same interval as the second [ 1, 1]. If we assume it does, we get the cancellation or inner version of subtraction, the result of which is [0,0]. Such cancellation operations, useful in several contexts, are approved to be required. 13. Comparison relations: A table of required comparison operations (number order relations and set inclusion relations) has been approved. 16. On endpoint and midpoint-radius arithmetic: This states that a standard-conforming implementation shall have at least one inf-sup (representation in terms of endpoints) data type with all required operations implemented, and that conversions between infsup and midpoint-radius form shall be provided. The conversions shall preserve containment and return the tightest representable interval in the target type. 17. I/O: Syntax for intervals in text form is defined, as well as conversions between text and internal intervals that preserve enclosure in either direction. This includes an exact text form for each interval type, from which the interval value can be recovered exactly. 18. A first requirement for an exception-handling decoration: Basically, the decision is that a decoration shall be provided to carry information on whether or not there were points in an argument to an operation that were outside of its domain. 19. Implicit and explicit data types: This clarifies some details related to endpoint and midpoint-radius arithmetic (as in item 16). 21. Overlapping detection: A function shall be provided to determine in wh
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x