From walster@kindra.Eng.Sun.COM Sat May 10 22:25:22 1997 Received: from mercury.Sun.COM (mercury.Sun.COM [192.9.25.1]) by dkuug.dk (8.6.12/8.6.12) with ESMTP id WAA29766 for ; Sat, 10 May 1997 22:25:16 +0200 Received: from Eng.Sun.COM ([129.146.1.25]) by mercury.Sun.COM (SMI-8.6/mail.byaddr) with SMTP id NAA15896; Sat, 10 May 1997 13:36:53 -0700 Received: from kindra.eng.sun.com by Eng.Sun.COM (SMI-8.6/SMI-5.3) id NAA27517; Sat, 10 May 1997 13:24:08 -0700 Received: from gww.eng.sun.com by kindra.eng.sun.com (SMI-8.6/SMI-SVR4) id NAA07611; Sat, 10 May 1997 13:24:08 -0700 Received: by gww.eng.sun.com (SMI-8.6/SMI-SVR4) id NAA03601; Sat, 10 May 1997 13:24:11 -0700 Date: Sat, 10 May 1997 13:24:11 -0700 From: walster@kindra.Eng.Sun.COM (William Walster) Message-Id: <199705102024.NAA03601@gww.eng.sun.com> To: Michel.Olagnon@ifremer.fr, Michael.Metcalf@cern.ch, sc22wg5@dkuug.dk, rbk@usl.edu Subject: Re: (SC22WG5.1372) Floating-point arithmetic Cc: Bill.Walster@Eng.Sun.COM X-Sun-Charset: US-ASCII >From rbk@usl.edu Wed May 7 07:34:43 1997 >X-Sender: rbk5287@pop.usl.edu >Mime-Version: 1.0 >Date: Wed, 07 May 1997 09:27:00 -0500 >To: Michel.Olagnon@ifremer.fr, Michael.Metcalf@cern.ch, sc22wg5@dkuug.dk >From: "R. Baker Kearfott" >Subject: Re: (SC22WG5.1372) Floating-point arithmetic >Cc: Bill.Walster@Eng > >At 11:23 AM 5/7/97 +0200, Michel.Olagnon@ifremer.fr wrote: > >>I strongly agree with Mike. I would appreciate if someone could point >>out an application, other than benchmarking purposes of vendors marketing >>teams, where standardization of interval arithmetic would be useful. >>On the opposite, predictability is essential in many actual applications. It is neither required nor desired to "standardize" interval arithmetic in the sense of requiring different implementations to produce exactly the same interval endpoints. What IS required is that any standard conforming interval implementation produce interval results to any computation that are guaranteed to contain the set of all possible outcomes. This is called "guaranteed containment" or "containment". It is not desired to require the same interval endpoints as this will inhibit different vendors from working to achieve results that are as "sharp" or narrow as possible while still guaranteeing containment. Of course, speed is always a virtue. If "predictability" of point results, means getting the same results, then this will simply hide the effects of rounding followed by cancelation in numerically or inherrently unstable algorithms. As long as interval arithmetic is available as an alternative, whether floating-point results are exactly reproducable or not is of little consequence. What is needed to implement interval arithmetic is to know the properties of the underlying floating-point arithmetic on any given platform. IEEE 754 compliance is the ideal environment with some minor modifications needed for interval exception handling. >> > >Actually, benchmarking purposes of vendor's marketing teams is a >minor application within the full body of experience of interval >arithmetic. Particularly successful applications have been in >global optimization and constraint propagation. When interval arithmetic >is viewed as a painless way of manipulating inequalities and constraints, >it is very powerful. For example, in global optimization, bounds on >the objective can be obtained that greatly facilitate elimination of >parts of the search region. There is a group of people who have developed >similar algorithms with non-interval methods, by doing ad-hoc classical >(by-hand) mathematical analysis for each particular problem to obtain >bounds on the variation. However, the non-interval techniques are more >complicated, and they also usually are less efficient. Similarly, >bounds on the values of expressions can be used to determine feasible >regions for systems of constraints. Such systems of constraints arise >in robot kinematics problems, among other things. For some interesting examples of complicated functions and relations in 2D that can be easily displayed using interval arithmetic, take a look at: http://www.peda.com/grafeq/ Graphing these relations and functions without interval arithmetic would be difficult, if not impossible, without interval arithmetic. > >Some strong actual applications have been in the chemical industry. >For example, in the analysis of trayed towers, the models often have >several solutions, and floating point methods only converge to one >solution, not the GLOBAL optimum, and with no way to check >whether it is the global optimum. However, the global optimum is >the only one that is meaningful in a chemical engineering sense. >In contrast, interval methods have successfully given the global optimum, >with a mathematically airtight guarantee that it is, indeed, the global >optimum. > >Many other industrial-strength problems are similar to the ones >encountered in chemical engineering. I can list more successes >and references upon demand. > >Another particularly attractive application is in adaptive quadrature. >Instead of using a heuristic to estimate the error, the actual error >can be bounded in a simple but airtight way. The result is an algorithm >that is not only more efficient, but has GUARANTEED accuracy. > >A final application I would like to mention at this point is verification >of the results of floating point computations. For example, a simple, >quick interval computation can be applied to the result of a linear >equation solution algorithm. Tiny intervals are constructed about >the approximate solution to a linear algebraic system, within which >interval arithmetic proves (with an airtight guarantee) that there >is a unique solution to the linear system. For many classes of problems, >the bounds so obtained are not only tighter than those implied by >condition number estimation, but are also obtained in less computation >time (than even the heuristic LINPACK condition number estimator). >For a reference, see C. F. Korn and Ch. Ullrich, "Extending LINPACK by >verification routines for linear systems," Mathematics and Computers in >Simulation 39 (1-2), pp. 21-37, 1995. > >I'll stop here, but I can go into more detail, give references, >and list more, if someone so desires. Any problem in which initial conditions or measurements contain errors can be ellegantly and rigorously handled using interval arithmetic. Nothing comparable exists with points. A window into the interval domain is located at: http://cs.utep.edu/interval-comp/main.html > >Best regards, > >Baker > >--------------------------------------------------------------- >R. Baker Kearfott, rbk@usl.edu (318) 482-5346 (fax) >(318) 482-5270 (work) (318) 981-9744 (home) >URL: http://interval.usl.edu/kearfott.html >Department of Mathematics, University of Southwestern Louisiana >USL Box 4-1010, Lafayette, LA 70504-1010, USA >--------------------------------------------------------------- > >