2!X9&EV+FQA;FPN9V]V
M("@X+C8N,3(O."XV+C$R*2!W:71H(%--5% @:60@3T%!,#(U,3D@9F]R(#QR
M96QI86)L95]C;VUP=71I;F= :6YT97)V86PN=7-L+F5D=3X[($9R:2P@."!$
M96,@,3DY-2 Q-#HP.#HS-R M,#2!X9&EV+FQA;FPN
M9V]V+GAD:78@*#0N,2]334DM-"XQ*0H):60@04$P-#2U4;SH@4F%J(%!A=&EL(#QR8G Q0&QA;FPN9V]V/@I396YD97(Z(&]W
M;F5R+7)E;&EA8FQE7V-O;7!U=&EN9PI07-I8V%L('-Y&%M<&QE6]U(&UA>2!N;W1I8V4@86QL(&]F('1H92!A8F]V92!A9'9A;G1A
M9V5S(&-A;B!B92!A9&1R97-S97,@;VX@=&AE"B @(&)A2!T:&%T(&-A;B!B92!G=6%R86YT965D(&)Y('1H92!V97)I9FEE9"!C;VUP
M=71I;F<@<&%R861I9VTN"B @($D@86T@;&]O:VEN9R!F;W(@'!L86YA=&EO;B!A;F0@8V]N=FEN8VEN9R!E>&%M<&QE" Q,30U"DQO
M); Wed, 13 Dec 1995 11:01:27 -0600
Received: from plot79.math.utah.edu (beebe [at] plot79 [dot] math.utah.edu [128.110.198.3]) by csc-sun.math.utah.edu (8.7.1/8.7.1) with ESMTP id KAA11868; Wed, 13 Dec 1995 10:01:10 -0700 (MST)
From: "Nelson H. F. Beebe"
Received: (from beebe@localhost) by plot79.math.utah.edu (8.7.1/8.7.1) id KAA19113; Wed, 13 Dec 1995 10:01:06 -0700 (MST)
Date: Wed, 13 Dec 1995 10:01:06 -0700 (MST)
To: reliable_computing [at] interval [dot] usl.edu
Cc: beebe [at] math [dot] utah.edu, bibnet [at] math [dot] utah.edu, ehg [at] research [dot] att.com
X-Us-Mail: "Center for Scientific Computing, University of Utah, Salt Lake
City, UT 84112, USA"
X-Telephone: +1 801 581 5254
X-Fax: +1 801 581 4148
X-Url: http://www.math.utah.edu/~beebe
Subject: Seeking bibliographies of interval arithmetic
Message-Id:
Sender: owner-reliable_computing
Precedence: bulk
Content-Length: 1475
X-Lines: 33
Status: O
Are any of you aware of Internet-accessible bibliographies of papers
and books on interval arithmetic?
As one of the editors of the BibNet Project, I think that it would be
useful to have such a bibliography in the BibNet archives. The master
archive for the Project resides at ftp://ftp.math.utah.edu/pub/bibnet,
and is mirrored nightly to Netlib hosts at AT&T and Oak Ridge National
Laboratory. The WorldWideWeb URL http://www.netlib.org/bibnet/ this
morning reports:
>> ...
>> bibnet
>> There have been 25,956 accesses to this library.
>> (Count updated 12/12/95 at 03:08:00)
>> ...
and the ftp logs for ftp.math.utah.edu show 7478 accesses as of
7-Dec-1995, so evidently, people are finding the collection useful.
I have a summer 1994 snapshot of 632 bibliographies from the huge
Computer Science bibliography archive in Karlsruhe
(http://www.ira.uka.de/), and no single file in that collection
concerns itself exclusively with interval arithmetic, though I'm
confident that the collection could be mined to start such a
bibliography.
========================================================================
Nelson H. F. Beebe Tel: +1 801 581 5254
Center for Scientific Computing FAX: +1 801 581 4148
Department of Mathematics, 105 JWB Internet: beebe [at] math [dot] utah.edu
University of Utah URL: http://www.math.utah.edu/~beebe
Salt Lake City, UT 84112, USA
========================================================================
From owner-reliable_computing Fri Dec 15 08:35:53 1995
Received: by interval.usl.edu id AA04263
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 15 Dec 1995 00:42:15 -0600
Received: from ixgate02.dfnrelay.d400.de by interval.usl.edu with SMTP id AA04257
(5.65c/IDA-1.4.4 for ); Fri, 15 Dec 1995 00:41:54 -0600
X400-Received: by mta d400relay in /PRMD=dfnrelay/ADMD=d400/C=de/; Relayed;
Fri, 15 Dec 1995 07:41:00 +0100
X400-Received: by /PRMD=UNI-LEIPZIG/ADMD=D400/C=DE/; Relayed;
Fri, 15 Dec 1995 07:35:53 +0100
Date: Fri, 15 Dec 1995 07:35:53 +0100
X400-Originator: rex [at] mathematik [dot] uni-leipzig.d400.de
X400-Recipients: non-disclosure:;
X400-Mts-Identifier: [/PRMD=UNI-LEIPZIG/ADMD=D400/C=DE/;ULMTA10389951215073553-W9K]
X400-Content-Type: P2-1984 (2)
From: Kearfott "R." Baker
Message-Id: <951215073552*/S=rex/OU=mathematik/PRMD=UNI-LEIPZIG/ADMD=D400/C=DE/@MHS>
To: RELIABLE_COMPUTING [at] INTERVAL [dot] USL.edu (Receipt Notification Requested) (Non
Receipt Notification Requested)
Cc: rbk [at] usl [dot] edu
Subject: Re: information on applications
Sender: owner-reliable_computing
Precedence: bulk
Content-Length: 5198
X-Lines: 99
Status: O
------------------------------ Start of body part 1
----- Additional Unix mail Header Lines -----
Received: from mihp710.mathematik.uni-leipzig.de by server1.rz.uni-leipzig.de with SMTP
(1.37.109.16/16.2) id AA066387126; Tue, 12 Dec 1995 20:38:46 +0100
Received: from interval.usl.edu by mihp710.mathematik.uni-leipzig.de with SMTP
(16.8/15.6) id AA06118; Tue, 12 Dec 95 20:34:03 +0100
Received: from localhost by interval.usl.edu with SMTP id AA01870
(5.65c/IDA-1.4.4); Tue, 12 Dec 1995 10:21:07 -0600
Received: by interval.usl.edu id AA01844
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 12 Dec 1995 10:19:41 -0600
Received: by interval.usl.edu id AA01834
(5.65c/IDA-1.4.4 for reliable_computing); Tue, 12 Dec 1995 10:19:39 -0600
------------------------------ Start of body part 2
----------
I would like to encourage people to reply, as specifically as possible,
to Rajendra Patil's request for information on actual applications of
interval computations. For convenience, I have attached his original
message.
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] usl [dot] edu (318) 482-5346 (fax)
(318) 482-5270 (work) (318) 981-9744 (home)
URL: ftp://interval.usl.edu/pub/interval_math/www/kearfott.html
Department of Mathematics, University of Southwestern Louisiana
---------------------------------------------------------------
Dear Baker,
Thank you for this message, but unfortunately I can not read this text.
Georg
begin 600 sun-deskset-message
M1G)O;2!O=VYE2!I;G1E&1I=BYL86YL+F=O=B!B>2!M86EL:&]S="YL86YL+F=O=B H."XV+C$R
M+S$N,BD*"6ED($]!03(R-C,U.R!&&1I=BYL86YL+F=O=BYX9&EV("AA;F=U
M2!X9&EV+FQA;FPN9V]V
M("@X+C8N,3(O."XV+C$R*2!W:71H(%--5% @:60@3T%!,#(U,3D@9F]R(#QR
M96QI86)L95]C;VUP=71I;F= :6YT97)V86PN=7-L+F5D=3X[($9R:2P@."!$
M96,@,3DY-2 Q-#HP.#HS-R M,#2!X9&EV+FQA;FPN
M9V]V+GAD:78@*#0N,2]334DM-"XQ*0H):60@04$P-#2U4;SH@4F%J(%!A=&EL(#QR8G Q0&QA;FPN9V]V/@I396YD97(Z(&]W
M;F5R+7)E;&EA8FQE7V-O;7!U=&EN9PI07-I8V%L('-Y&%M<&QE6]U(&UA>2!N;W1I8V4@86QL(&]F('1H92!A8F]V92!A9'9A;G1A
M9V5S(&-A;B!B92!A9&1R97-S97,@;VX@=&AE"B @(&)A2!T:&%T(&-A;B!B92!G=6%R86YT965D(&)Y('1H92!V97)I9FEE9"!C;VUP
M=71I;F<@<&%R861I9VTN"B @($D@86T@;&]O:VEN9R!F;W(@'!L86YA=&EO;B!A;F0@8V]N=FEN8VEN9R!E>&%M<&QE" Q,30U"DQO
M); Fri, 15 Dec 1995 13:59:23 -0600
Received: from xdiv.lanl.gov by mailhost.lanl.gov (8.6.12/1.2)
id MAA26564; Fri, 15 Dec 1995 12:59:20 -0700
Received: from xdiv.lanl.gov.xdiv (angus.lanl.gov [128.165.123.30]) by xdiv.lanl.gov (8.6.12/8.6.12) with SMTP id MAA22684 for ; Fri, 15 Dec 1995 12:59:12 -0700
Date: Fri, 15 Dec 1995 12:59:12 -0700
From: "Rajendra B. Patil"
Message-Id: <199512151959.MAA22684 [at] xdiv [dot] lanl.gov>
Received: by xdiv.lanl.gov.xdiv (4.1/SMI-4.1)
id AA02371; Fri, 15 Dec 95 12:59:12 MST
To: reliable_computing [at] interval [dot] usl.edu
Subject: Applications...
Reply-To: Raj Patil
Sender: owner-reliable_computing
Precedence: bulk
Content-Length: 764
X-Lines: 23
Status: O
Hi:
Regarding my previous message, Dr. Birdie suggested I change
the wording as that might provoke many responses. Until now
I have only received 3 messages.
Interval arithmetic/analysis appears to provide elegant tools
for dealing with system uncertainty. I am looking for examples
of these in the design and development of real systems.
Thanks,
-------------------------------------------------------------
Raj Patil email: rbp1 [at] lanl [dot] gov
phone: (505)-665-0581
MS - F 645 fax : (505)-665-4479
XCM, Los Alamos National Laboratory
Los Alamos, NM 87545
------------- alternate address -----------------------------
P.O Box 1145
Los Alamos, NM 88003
-------------------------------------------------------------
From owner-reliable_computing Fri Dec 15 08:02:34 1995
Received: by interval.usl.edu id AA04880
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 15 Dec 1995 14:02:35 -0600
Received: by interval.usl.edu id AA04870
(5.65c/IDA-1.4.4 for reliable_computing); Fri, 15 Dec 1995 14:02:34 -0600
Date: Fri, 15 Dec 1995 14:02:34 -0600
From: "Kearfott R. Baker"
Message-Id: <199512152002.AA04870 [at] interval [dot] usl.edu>
To: reliable_computing
Subject: Request for applications -- another try and an apology
Sender: owner-reliable_computing
Precedence: bulk
Content-Length: 2657
X-Lines: 72
Status: O
Colleagues:
I apologize that the attachment on my previous message may have been
unreadable. Sorry for the inconvenience. I'm learning!
I repeat:
I would like to encourage people to reply, as specifically as possible,
to Rajendra Patil's request for information on actual applications of
interval computations. For convenience, I have appended his original
message (in a hopefully readable form this time).
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] usl [dot] edu (318) 482-5346 (fax)
(318) 482-5270 (work) (318) 981-9744 (home)
URL: ftp://interval.usl.edu/pub/interval_math/www/kearfott.html
Department of Mathematics, University of Southwestern Louisiana
---------------------------------------------------------------
From: "Rajendra B. Patil"
Message-Id: <199512082108.OAA02519 [at] xdiv [dot] lanl.gov>
Received: by xdiv.lanl.gov.xdiv (4.1/SMI-4.1)
id AA04777; Fri, 8 Dec 95 14:08:20 MST
To: reliable_computing [at] interval [dot] usl.edu
Subject: Applications info....
Reply-To: Raj Patil
Sender: owner-reliable_computing
Hi:
I am looking for help in collecting following information to convince
a group of people in using Interval Arithmetic for verified computing
in problems where safety issues are important in the design of a
physical system.
1) Very simple examples to demonstrate the concept of verification for
people without much mathematical and computer background.
2) ANY industrial application areas with a need for such verification
properties.
3) What are the benefits of verification in an application
a. economic impact, e.g. saving over unverified systems (estimates are ok),
b. reducing risk (due to verification),
c. improved working conditions,
d. improved environment,
e. whatever improvements you think are possible that will help
convince administration for using this approach.
As you may notice all of the above advantages can be addresses on the
basis of safety that can be guaranteed by the verified computing paradigm.
I am looking for some concrete explanation and convincing examples.
I will post the summary, IF i receive any replies....
Thanks in advance,
-------------------------------------------------------------
Raj Patil email: rbp1 [at] lanl [dot] gov
phone: (505)-665-0581
MS - B 258 fax : (505)-665-4479
XCM, Los Alamos National Laboratory
Los Alamos, NM 87545
------------- alternate address -----------------------------
P.O Box 1145
Los Alamos, NM 88003
-------------------------------------------------------------
From owner-reliable_computing Tue Dec 19 11:26:53 1995
Received: by interval.usl.edu id AA07119
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 19 Dec 1995 03:27:47 -0600
Received: from paradoxe.irisa.fr by interval.usl.edu with SMTP id AA07113
(5.65c/IDA-1.4.4 for ); Tue, 19 Dec 1995 03:27:30 -0600
Received: from paraffine.irisa.fr (paraffine.irisa.fr [131.254.20.8]) by paradoxe.irisa.fr (8.6.12/8.6.9) with ESMTP id KAA00476; Tue, 19 Dec 1995 10:26:54 +0100
From: Olivier Beaumont
Date: Tue, 19 Dec 1995 10:26:53 +0100
Message-Id: <199512190926.KAA06030 [at] paraffine [dot] irisa.fr>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Polynomials...
Sender: owner-reliable_computing
Precedence: bulk
_________________________________________________________________________
I'd like to know methods in order to enclose surely the image set of a
polynomial in one or several variables. The aim is not to compute exactly
the image set but just to enclose it as precisely as possible.
Any reference would be helpful.
Thank you for your help,
Olivier Beaumont
(33) 99 84 75 05
obeaumon [at] irisa [dot] fr
Institut de Recherche en Informatique et Sytemes aleatoires. Rennes. France
_________________________________________________________________________
From owner-reliable_computing Thu Dec 21 12:04:04 1995
Received: by interval.usl.edu id AA13722
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Thu, 21 Dec 1995 20:04:13 -0600
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA13716
(5.65c/IDA-1.4.4 for ); Thu, 21 Dec 1995 20:04:08 -0600
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA13180; Thu, 21 Dec 95 19:04:04 MST
Date: Thu, 21 Dec 95 19:04:04 MST
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9512220204.AA13180 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Double bubble paper on-line
Sender: owner-reliable_computing
Precedence: bulk
The paper by J. Hass et al.
in which interval computations have been used to
solve a long-standing geometric problem is on-line
(for details on the problem, see my previous announcement).
It can be accessed from the homepage of the first author:
URL http://www.math.ucdavis.edu/~hass
This homepage can also be accessed from the Personalia
and Applications sections of the Interval Computations homepage:
URL http://cs.utep.edu/interval-comp/main.html
From owner-reliable_computing Fri Dec 22 09:33:00 1995
Received: by interval.usl.edu id AA14507
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 22 Dec 1995 15:34:14 -0600
Received: from boris.mscs.mu.edu by interval.usl.edu with SMTP id AA14501
(5.65c/IDA-1.4.4 for ); Fri, 22 Dec 1995 15:34:05 -0600
Received: by boris.mscs.mu.edu (Smail3.1.28.1 #9)
id m0tTF5s-000083C; Fri, 22 Dec 95 15:33 CST
Message-Id:
Date: Fri, 22 Dec 95 15:33 CST
From: georgec [at] boris [dot] mscs.mu.edu (Dr. George F. Corliss MU MSCS)
To: reliable_computing [at] interval [dot] usl.edu
Subject: Applications of intervals (long)
X-Sun-Charset: US-ASCII
Sender: owner-reliable_computing
Precedence: bulk
Raj,
> I am looking for help in collecting following information to convince
> a group of people in using Interval Arithmetic for verified computing
> in problems where safety issues are important in the design of a
> physical system.
Here are some stories I know. Interval techniques are no "silver
bullet", but they CAN provide insight.
1. arctan
Some years back, a major oil company was running a portion of an
oil reservoir simulation code. They were running identical codes
on identical IBM 3090 computers with identical software configurations
at two different sites. One machine consistently gave non-physical
negative concentrations. After MUCH investication, the difference
was traced to different arctan routines in the vendor-supplied
libraries. The engineers, of course, standardized on the library
that led to positive concentrations, ALTHOUGH THAT WAS THE ARCTAN
THAT YIELDED _WRONG_ RESULTS. The engineers went away satisfied,
but the computer support people were MOST dismayed, and called me
as an interval consultant. When I arrived, though, they preferred
that I look at different problems. I do not know the outcome of
the engineers continuing intentionally to use the incorrect arctan.
2. sqrt (negative)
The same oil company DID ask me to look at a crack propagation
submodel in their reservoir simulation model. The crack propagation
model was a nonlinear PDE, which they solve by time stepping. At
each time step, they solved a nonlinear system by Newton's method.
Computations proceeded smoothly for about 100 time steps, when
suddenly, computation halted with a sqrt (negative). We used
interval techniques to validate the existing approximating
computations and to discover that the problem was a need for a more
accurate starting guess for the Newton iteration. That modification
was made to the approximate code, and the simulation ran for more
than 200 time steps.
3. Singular linear systems.
The same oil company gave me a linear system they were trying to solve
by a conjugate gradient algorithm. The algorithm was not converging
as they expected. I coded it up using the accurate linear solver
in ACRITH, and ACRITH computed 1 ULP enclosures of an answer on an
IBM 3090 while we ate lunch. They hadn't solved the problem, but I
had. Great! Actually, the long accumulator had more to do with the
success than interval arithmetic, but the interval techniques DID
allow us to validate our results. Next, I wanted to explore the
sensitivity of the result, so I inclated their matrix coefficients
by a relative width of about 10^{-3}. ACRITH said the interval
matrix contained a singular matrix. After further experiments,
when I inflated ANY element of their original point-valued matrix
to an interval 1 UPL wide, ACRITH again said that the matrix was
singular. So I went to the engineers and triumphantly proclaimed,
"The reason you were having trouble is that you are trying to solve
a singular system, and interval techniques have validated that!"
One engineer looked puzzled. "Oh, didn't we tell you? ALL our
matrices are singular." So I learned something, even if they knew
it already.
These stories are described in more detail in the attached paper.
4. Bounded solutions of linear systems.
A biomodeler cam to me with a problem of blood flow in a capillary
bed. He had a pressure in a single incoming artery and the pressure
in a single outgoing vein. In between was a complicated network
flow problem. He had formulated the pressure model as a linear
system, which he had solved, but he was concerned about the accuracy
and robustness of his results. After all, the problem was very
sensitive, since a restriction in one vessel in the bed causes
BIG changes in the flows of nearby vesslels. We set up an
interval-valued system to reflect the uncertainties in his data.
This time, when we passed the system to an interval solver, we
were surprised to find everything perfectly well behaved. There
was no evidence (in the pressures) of any sensitivity at all.
My client thought for a moment and exclaimed, "Of course! The
pressures _must_ be bounded by the input and the output pressures,
so we have no fear of unbounded solutions!" The application of
interval techniques allowed him to concentrate on his model, without
fears of numerical difficulties.
5. In recent talks, Professor Kulisch has described a turbine
application. You should get details from him.
6. A book of a couple years ago edited by Adams and Kulisch
contains many articles describing applications.
7. I headr a wonderful talk by Wolfram Klein at SCAN 95 in Wuppertal
about using interval techniques and automatic differentiation for
a circuit simulation problem.
8. Ernst Adams and others have applied interval techniques to the
study of chaotic dynamical systems.
% File: INT_TEC2.TEX 03-JAN-1990
%
% Industrial Applications of Interval Techniques
% Paper for Basel conference
% Based on technical report 301
% How Can You Apply Interval Techniques in an Industrial Setting?
% No page numbers?
% Line spacing?
\documentstyle [11pt]{article}
\topmargin -0.2 true in
%\textheight 8.5 true in
\textheight 232 mm
%\textwidth 6 true in
\textwidth 160 mm
\hoffset 0.5 true in
\begin {document}
\renewcommand {\vector}[1]{{\bf #1}}
\newcommand {\beginsection}[1]{{\vspace {15pt} \message{#1}
\leftline{\bf #1}
\nobreak \smallskip \vskip-\parskip}}
\newcommand {\subsect}[1]{{\bigskip
\leftline{\bf #1}
\nobreak \smallskip \vskip-\parskip}}
\newcommand {\subsubsub}[1]{
\vspace {20 pt}
\noindent
{\large \em #1}
\vspace {10 pt}
}
\newcommand {\recommend}[1]{
\vspace {20 pt}
\noindent
{\bf #1}
\vspace {20 pt}
}
\newcommand {\real}{\bf R}
\large
\pagestyle {empty}
\baselineskip 8 mm
\begin {center}
{\Large
INDUSTRIAL APPLICATIONS OF INTERVAL TECHNIQUES
} \vspace {10 pt} \\
George F. Corliss \\
Marquette University \\
Milwaukee, WI 53233 USA \vspace {10 pt}
\end {center}
\noindent
{\bf Abstract.} Tools for achieving high accuracy and guaranteed
inclusions in scientific computations have been promoted by the
research community for many years. Commercial products have made
those tools widely available. We apply the tools of ACRITH to a
least squares problem, a problem involving matrix products and
inverses, the conjugate gradient algorithm, and a partial
differential equation with a moving boundary. We discuss the
lessons learned from these experiences about how interval techniques
and high accuracy computations can be used cost-effectively for
industrial problems.
\beginsection {1. Introduction}
Since Moore's {\sl Interval Analysis\/} \cite{Moor66a} appeared
in 1966, the academic research community has been promoting the use
of interval techniques to achieve guaranteed bounds for the results
of scientific computations. Conventional algorithms, or
{\em point\/} algorithms, compute an estimate for an answer and
perhaps an error estimate. The user cannot tell how accurate the
estimated answer may be without extensive, expensive error analysis.
The quality of scientific software packages has improved, but there
are still problems for which catastrophically incorrect answers are
returned to the user with no warning.
Interval techniques compute an interval in which the correct
answer is guaranteed to lie. If interval techniques compute an
answer $ [1.23456, 1.23457] $, then 6 decimal places are
{\em known\/} to be correct. If an algorithm yields the interval
$ [-10^{30}, \ +10^{30} ] $, then you {\em know\/} that you do not
know the answer. Hence, interval results carry with them an
assurance of their quality.
In the early days, it was hard for a scientist or engineer to
apply interval techniques because suitable software was not widely
available. Now there are at least four commercially available
systems which support interval arithmetic and the Kulisch-Miranker
accurate scalar product \cite{Kuli81a}:
\begin {description}
\item [Pascal-SC] - Variant of Pascal for scientific
computation. Runs on popular microcomputers. Available
from Wiley-Teubner. \cite{Kuli87a}
\item [ACRITH] - Fortran callable subroutine library. Runs on
IBM 370 architecture. Available from IBM. \cite{IBM86a}
Fortran-SC \cite{Metz87a} makes ACRITH subroutine calls
easier to program.
\item [ARITHMOS] - Fortran callable subroutine library. Runs on
Siemens BS 2000. Available from Siemens. \cite{Siem86a}
\item [NAG] - Ada programming language library. Requires VAX/VMS Ada
compiler. Available from Numerical Algorithms Group.
\cite{Delv87a}
\end {description}
Hence, a scientist or engineer now has ready access to these tools
on a variety of commonly used computers.
This paper addresses ways in which tools for interval methods
can be applied to industrial problems drawn from the author's
consulting experience. We illustrate with a least squares problem,
a problem involving matrix products and inverses, the conjugate
gradient algorithm, and a partial differential equation with a
moving boundary. We consider when interval tools should be used and
how to use them.
\beginsection {2. High Accuracy}
Interval techniques compute an interval in which the
correct answer is validated to lie. On the other hand, techniques
for high accuracy compute an answer which is accurate to as many
places as possible. Interval and high accuracy techniques are
related, because we want the widths of interval inclusions to be as
narrow as possible. However, techniques for high accuracy
computation are very useful in their own right, with no reference to
intervals. This section describes the support provided by ACRITH for
high accuracy computations and how those tools have are applied to
some actual problems.
\subsect {2.1. Accurate scalar product}
The fundamental tool provided by ACRITH for high accuracy
computation is the accurate scalar product. Its use
often prevents the error from growing with problem size.
Let $ \vector {w} = (w_1, w_2, \ldots , w_n) $ and
$ \vector {v} = (v_1, v_2, \ldots , v_n) $ be vectors in $ \real^n $.
Then ACRITH's scalar product computes
\begin {equation}
\vector {w} \bullet \vector {v} = \sum_{i=0}^n w_i \cdot v_i
\label {Scalar_Product}
\end {equation}
with only {\em one rounding error.\/} The ACRITH scalar product is
more accurate than the corresponding Fortran DO loop. On some
hardware, it is also about 15% faster.
A Fortran DO loop for evaluating Equation
(\ref{Scalar_Product}) commits $ 2 n $ rounding errors, while the
ACRITH program commits only one rounding error {\em independent\/}
of the size of $ n $. This is important since industrial problems tend to
be large. Since the ACRITH program commits only one rounding error
at the conclusion of the calculation, it is not subject to
catastrophic cancellation errors or to intermediate overflow.
Conventional wisdom in numerical analysis suggests that it is
often useful to accumulate scalar products in a higher precision. If
a Fortran DO loop accumulates the sum in double
precision, the $ 2 n $ rounding errors are of the order of double
precision machine roundoff. The result is more accurate one
computed by the single precision program, but it is not as accurate
as the results from ACRITH. Further, the double precision
accumulation of scalar products is still sensitive to catastrophic
cancellation and overflow of intermediate results.
\subsect {2.2. How does it work?}
A detailed discussion of the algorithms used by ACRITH is
beyond the scope of this paper (see \cite{IBM86a}, pp. 57--61 for
details). ACRITH uses a long accumulator with a capacity for 328
hexadecimal digits. The accumulation of the scalar product is done
in fixed-point arithmetic with partial products being added into the
accumulator in the appropriate digit positions. When the summation
is completed, the result is rounded once for storing back into a
single or double precision memory location.
\subsect {2.3. An example -- Least squares}
Let $ A $ be an $ m \times n $ matrix, with $ m > n $. We wish
to solve
\begin {equation}
A \vector {x} = \vector {b}
\label {Least_Squares}
\end {equation}
in the least squares sense. This problem arises often in
many industrial applications, and it is often very large. The least
squares solution to Equation (\ref{Least_Squares}) is the same as
the solution to the square system
\begin {equation}
A^T A \vector {x} = A^T \vector {b},
\label {Normal_Equations}
\end {equation}
which are called the normal equations. It is well known that the
normal equations are very poorly conditioned. The conventional
wisdom in numerical analysis is that one can almost never solve a
least squares problem using the normal equations. Methods such as
Gram-Schmidt orthonormalization, Q-R factorization, or singular
valued decomposition were developed to overcome the numerical
difficulties of ill conditioned systems.
The accurate scalar product calls this conventional wisdom into
question. The reason the ill conditioning of the normal
equations is a problem is that with conventional arithmetic,
roundoff errors accumulate so fast that the computed
solution is worthless. With ACRITH's scalar product, the accumulation
of roundoff errors is much less severe, and it is independent of
the size of the problem.
The program in Listing 1 solves a modest
least squares problem. This program uses ACRITH routines to form
$ A^T A $, $ A^T b $, and to solve the normal equations.
\begin {verbatim}
PARAMETER (M = 228, N = 178)
DOUBLE PRECISION A (M, N), AT(N, M), APROD(N, N), B(M),
+ BT(N), XL(N), XU(N)
C Get matrix A
C AT = A transpose
C APROD = A transpose * A
CALL DMAMN (N, M, N, AT, A, APROD, IER)
C BT = A transpose * B
CALL DMAMN (N, M, 1, AT, B, BT, IER)
C Solve A trans A x = A trans b
CALL DLIN (N, APROD, BT, BT, XL, XU, IER)
\end{verbatim}
\begin {center}
Listing 1. Solve the normal equations.
\end {center}
\vspace {10 pt}
For the data we were given, ACRITH was able to solve the normal
equations with an absolute residual error of 4.02E-14. For
comparison, Listing 2 is code using IMSL routines to form and solve
the normal equations.
\begin {verbatim}
C APROD = A transpose * A
CALL DMXTXF (M, N, A, M, N, APROD, N)
C BT = A transpose * B
CALL DMXTYF (M, N, A, M, M, 1, B, M, N, 1, BT, N)
C Solve A trans A x = A trans b
CALL DL2ARG (N, APROD, N, BT, 1, XL, FAC, IPVT, WK)
\end{verbatim}
\begin {center}
Listing 2. Solve the normal equations using IMSL routines.
\end {center}
\vspace {10 pt}
Since the difficulty of using tools for high accuracy is an issue,
we remark that changing from the IMSL subroutines to the ACRITH
subroutines requires only the replacing of one set of subroutine
calls by another. The two programs are of the same complexity.
The IMSL library provides a routine L2BRR for solving linear
least squares problems using a Q-R decomposition with optimal
column pivoting. This routine was unable to solve this problem; it
fails because of an underflow. In Section 4, we will see that L2BRR
fails because the problem is very close to a singular problem.
If the ACRITH linear equation solving routine DLIN is unable to
solve the normal equations because of excess width arising from the
explicit formation of $ A^T A $ and $ A^T b $, then
the normal equations are recast
as an $ (2 m + n) \times (2 m + n) $ block system with no matrix
products:
\begin {equation}
\left ( \begin {array}{ccc}
A & -I \\ & A^T \\ && I \end {array} \right )
\left ( \begin {array}{c}
x \\ y \\ z \end {array} \right )
=
\left ( \begin {array}{c}
0 \\ 0 \\ b \end {array} \right ).
\label {Large_System}
\end {equation}
Then DLIN is called to solve Equation (\ref{Large_System}).
% derivation:
% A^T A x = A^T b
%
% A x = y
% A^T y = A^T b
%
% A^T y - A^T z = 0
% z = b
%
% x y z
% A -I 0 m
% A^T -A^T 0 n
% I b m
% n m m
\subsect {2.4. An example - Conjugate gradient}
A second approach to solving Problem (\ref{Least_Squares}) is the
conjugate gradient algorithm \cite{Hest52a}, which involves many
scalar products. We suspected that an accumulation of roundoff
errors was forcing a conventional program to take several times as
many iterations than should be necessary. We replaced the existing
scalar products with ACRITH calls to improve the accuracies. We
present an outline of the analysis and our experiences as an example
of how to apply the tools of ACRITH.
Suppose that $ A $ is an $ m \times n $ matrix. The conjugate
gradient algorithm for solving the least squares problem
$$
A \vector {x} = \vector {b}
$$
is:
\begin {tabbing}
\hspace {1.3 in} \= Choose $ \vector {x}_0 $; \\
\> Put \= $ \vector {s}_0 = \vector {b} - A \vector {x}_0 $; \\
\> \> $ \vector {r}_0 = \vector {p}_0
= A^T (\vector {b} - A \vector {x}_0) $; \\
\> \> $ \vector {q}_0 = A \vector {p}_0 $; \\
\> For $ k = 0, 1, \ldots $ \\
\> \> $ \alpha_{k+1}
= (\vector {r}_k, \vector {r}_k)
/ (\vector {q}_k, \vector {q}_k) $; \\
\> \> $ \vector {x}_{k+1}
= \vector {x}_k + \alpha_{k+1} \vector {p}_k $; \\
\> \> $ \vector {s}_{k+1}
= \vector {s}_k - \alpha_{k+1} \vector {q}_k $; \\
\> \> $ \vector {r}_{k+1} = A^T \vector {s}_{k+1} $; \\
\> \> $ \beta_{k+1}
= (\vector {r}_{k+1}, \vector {r}_{k+1})
/ (\vector {r}_k, \vector {r}_k) $; \\
\> \> $ \vector {p}_{k+1}
= \vector {r}_{k+1} + \beta_{k+1} \vector {p}_k $; \\
\> \> $ \vector {q}_{k+1} = A \vector {p}_{k+1} $;
\end {tabbing}
If arithmetic is done with infinite precision, the conjugate
gradient algorithm converges in $ n $ iterations. In practice, the
accumulation of roundoff errors requires extra iterations. We
observed 4 -- 5 $ \times \ n $ iterations being required for
satisfactory convergence.
Initially, we replaced each of the scalar products
$ ( \cdot , \cdot ) $ by a call to the scalar product from ACRITH.
Calculations such as $ \vector {b} - A \vector {x} $ or
$ \vector {x} + \alpha \vector {p} $ are potentially subject to
catastrophic cancellation, so each was reformulated to use the
ACRITH scalar product. It is critical to evaluate the expression
\begin {eqnarray}
\vector {x}_{k+1}
= \vector {x}_k + \alpha_{k+1} \vector {p}_k
= \vector {x}_0 + \sum_{j=0}^k \alpha_{j+1} \vector {p}_j.
\label {x_k+1}
\end {eqnarray}
accurately. By storing $ \vector {p}_0, \ldots , \vector {p}_k $,
each component of $ \vector {x}_{k+1} $ can be computed with a
single rounding error. Similarly, each component of
$ \vector {s}_{k+1} $ can be computed with a single rounding error.
This requires storing all previous iterates and negates one of
the advantages of the conjugate gradient algorithm. We developed a
compromise algorithm which retained about 10 previous iterates.
It is common to design algorithms to achieve high accuracy by
reformulating a problem as a residual correction.
Suppose we wish to compute the double precision value $ y =
\sum_{j=1}^n u_j v_j $ as for each component of $ \vector {x}_{k+1} $
in Equation (\ref{x_k+1}). The value of $ y $ is computed with
only one rounding error, but suppose that still introduces too much
error into succeeding calculations. If so, we compute $ y_1 =
\sum_{j=1}^n u_j v_j $ and then $ y_2 = - y_1 + \sum_{j=1}^n u_j v_j
$ as a single scalar product. The effect is that $ y_1 + y_2 $ is a
quadruple precision value of $ y $. Later computations use $
y_1 + y_2 $ in place of $ y $. We applied this trick to the
computation of $ \vector {x}_{k+1} $ and $ \vector {s}_{k+1} $.
We had eliminated several different sources of accumulation of
rounding error from the original program, so we ran the modified
program with great anticipation. The resulting vectors $ \vector
{x}_k $ agreed to several figures with those calculated previously.
That is, there was no significant improvement.
Close inspection of the intermediate results showed that while
the vectors $ \vector {x}_k $ agreed with those calculated
previously, the search directions $ \vector {p}_k $ and the
residual vectors $ \vector {r}_k $ were completely different after the
first few iterations. When we checked the orthogonalities
$$
(\vector {r}_j, A \vector {r}_{k+1}) = 0
\mbox { for } j = 0, \ldots , k
$$
predicted by the theory, the ``accurate'' residuals were only
slightly more nearly orthogonal than the original residuals. This
suggests that to improve the accuracy of the algorithm, we must do
a partial reorthonormalization.
What did we learn from this attempt to apply the ACRITH scalar
product to the conjugate gradient algorithm? First, we
were able to replace calls to conventional scalar product routines
by calls to the ACRITH scalar product routine. Second, we learned
about the behavior of the algorithm. We now understand that the
source of the inaccuracies is a gradual deterioration in the
orthonormality of the residual vectors. Finally,
we are reminded that hard problems are hard. The
scalar product from ACRITH is a useful tool to achieve increased
accuracies, but it is not a magic wand. To use the tool
effectively, we must understand the algorithm to which it is being
applied. A mechanical replacement of one scalar product by another
is not necessarily enough.
Since the human time required to use these methods is an issue,
we remark that these results have required about 3 man-days of an
expert on ACRITH who was unfamiliar with the conjugate gradient
algorithm.
\subsect {2.5. An example - Hat matrices}
Another example using ACRITH's high accuracy arises in
computing Allen's PRESS criterion for selecting variables in
regression \cite{Alle74a}. Let $ A $ be an $ m \times n $ matrix of
derivatives of a model function with respect to $ n $ model
parameters at $ m $ values of the independent variable. Problems of
interest are about $ 100 \times 5 $. The PRESS criterion requires
the diagonal elements of the $ m \times m $ ``hat'' matrix
\begin {equation}
H = A (A^T A)^{-1} A^T.
\label {Hat}
\end {equation}
The sum of the diagonal elements of $ H $ is $ n $, and $ H $ is
idempotent ($ H \cdot H = H $). These two properties can be used
to check the computed values.
Hoaglin and Welsch \cite{Hoag78a} suggest using Householder
transformations or singular value decompositions to minimize
roundoff errors. If possible, we preferred a simpler implementation
based on the definition for ease of coding and maintenance.
Neither single nor double precision routines from the Harwell or
IMSL libraries were sufficiently accurate, even for systems as small
as $ 10 \times 4 $. When the calls to Harwell or IMSL library
routines are replaced by calls to double precision ACRITH routines,
the sum of the diagonal elements is $ n $, and $ H $ is idempotent
to full machine accuracy.
The human and machine time required is an issue. The engineer
who did this work remarks, ``In my application, the extra time
required by ACRITH routines is insignificant in comparison to the
time it would have required to program more complex methods and to
maintain the program as changes in FORTRAN, etc. occur. It
certainly is less than the clock and CPU time I would have wasted
by now in trying to make sense of less accurate computed results.''
If the accumulation of errors is still too great using ACRITH
routines to evaluate $ H $, Equation (\ref{Hat}) can be recast as a
block system in $ m \times m + n \times m $ unknowns
\begin {equation}
\left ( \begin {array}{cc}
I & -A \\ A^T \end {array} \right )
\left ( \begin {array}{c}
H \\ V \end {array} \right )
=
\left ( \begin {array}{c}
0 \\ A^T \end {array} \right ).
\label {HAT}
\end {equation}
Then DLIN is called to solve Equation (\ref{HAT}).
% derivation:
% H = A (A^T A)^{-1} A^T
%
% H = A V H is m \times m; V is n \times m
% V = (A^T A)^{-1} A^T
% (A^T A) V = A^T
%
% A V = W implies W = H
% A^T W = A^T H = A^T
%
% H V
% I -A 0 m
% A^T A^T n
% m n
%
% The unknowns are the elements of H and V. That is, this
% matrix equation should be viewed in terms of the column vectors
% of H and V.
\subsect {2.6. How should you use techniques for high accuracy?}
Scientists and engineers can begin at once to apply tools for high
accuracy computation to their industrial problems.
\subsubsub {Use accurate scalar product in new or existing code.}
The accurate scalar product can be profitably used whenever a
scalar or dot product is required. Both authors of new development
codes and those maintaining existing codes can look for code
segments which sum vectors or compute scalar products. Replacing
conventional code with a call to the appropriate ACRITH scalar product
routine improves the accuracy. Depending on the host hardware, the
execution speed may also be improved.
This strategy is similar to that of seeking to recognize scalar
products in algorithms being implemented on vector or parallel
machines. In both cases, the strategy works because the scalar
product is treated as an elementary operation by the machine.
\subsubsub {Use high accuracy general-purpose problem solving routines.}
ACRITH provides several powerful, general-purpose problem
solving routines which can serve as major building blocks. Examples
include solving linear equations, eigenvalue/eigenvector analysis,
polynomial rootfinding, and solving nonlinear equations. These
routines can be used modularly in the same manner as routines from
the NAG or IMSL libraries. Hence, a scientist or engineer can
include the ACRITH library among the libraries searched for existing
software to help solve applications problems.
\subsubsub {Use simpler methods before more complicated ones.}
The accurate scalar product from ACRITH can be used to make
algorithms which have historically been discarded as numerically
unstable behave satisfactorily. Examples include solving
a least squares approximation problem using the normal equations or
by Gram-Schmidt orthonormalization. Such methods are poorly
conditioned using conventional arithmetic. However, they may be
well behaved when carefully programmed using the accurate scalar
product. The simpler methods may work using accurate arithmetic, and
they are much easier to program. Of course, some bad methods are
still bad methods, even with the accurate scalar product.
\subsect {2.7. What are the costs?}
The primary cost of using the ACRITH tools for high accuracy
is the human cost of learning to use them. Those costs are
highly variable and difficult to quantify. Learning costs may be
minimal, since one form of a scalar product is being replaced
with another. Learning costs may be modest, since
problem solving routines from the ACRITH library replace
similar routines from other libraries. Learning costs also may be
large, since new programming tools are replacing familiar
ones. Further, a fundamental analysis of the algorithm being used
is sometimes required to achieve the potential benefits of the
accurate scalar product.
\beginsection {3. When should interval techniques be considered?}
Now we turn our attention to our main focus: interval techniques
for computing validated inclusions. We address a scientist or
engineer who is acquainted with conventional point numerical
algorithms and who is interested in appropriate uses of interval
algorithms for their problems.
Interval techniques should be considered in two circumstances:
\begin {enumerate}
\item Accuracy of the computed answer is in doubt.
\item Input data or parameters in the problem are uncertain.
\end {enumerate}
We consider each of these circumstances separately.
\subsect {3.1. Accuracy of the computed answer is in doubt.}
Interval techniques should be considered whenever to provide
some assurance about how accurately the answer is computed. An
interval answer $ [1.23456, 1.23457] $ provides assurance that the
answer is known correctly to 6 decimal places, while a point answer
1.23456 may have the wrong sign. The accuracy of many scientific and
engineering calculations is in doubt. Sections 4 and 5 give
two examples.
\subsect {3.2. Uncertain data or parameters.}
The second circumstance in which interval techniques should be
considered are problems whose input data or parameters are
uncertain. Often, data are known to be accurate to only 3 or 4
decimal places. How does the uncertainty in the data contribute to
uncertainty in the answer? This question is especially important
when the problem is known to be ill conditioned. The question may
be ignored, or it may be addressed by hard analysis, by simulations,
or by appealing to experience. The analysis is often difficult or
impossible; simulations are expensive, especially in many
dimensions; and experience may be lacking or misleading.
In contrast, interval techniques provide guarantees, and they
may be applied almost automatically. If we start with intervals in
which the input data or parameters must lie, then computations
using interval arithmetic give intervals in which the answers must
lie.
\beginsection {4. An example - Least squares}
Interval techniques should be considered when the accuracy of
the computed solution is in doubt. For example, we asserted in
Section 2.4 that the program in Listing 1 solved a least squares
problem accurately. We gave as evidence a residual of 4.02E-14.
However, a small residual does not assure a small relative error in
the solution, and the conventional wisdom suggests that it is not
possible to solve the normal equations as accurately as we claim
to have done. Hence, the accuracy of our answer is in doubt.
The ACRITH routine DLIN in Listing 1 computes an interval
[XL(J), XU(J)] containing each component of the solution:
\begin {verbatim}
J [XL(J), XU(J)]
1 ( 0.1044068767878713D+02, 0.1044068767878714D+02 )
2 ( 0.1182954682872744D+02, 0.1182954682872745D+02 )
.
.
.
177 ( -0.1808366597477822D+02, -0.1808366597477821D+02 )
178 ( 0.6148360648647853D-01, 0.6148360648647854D-01 )
\end{verbatim}
\begin {center}
Listing 3. Inclusions of least squares solution.
\end {center}
\vspace {10 pt}
For each of these intervals, XL(J) differs from XU(J) by one
unit in the last hexadecimal place. These interval answers verify
that we have computed the answers with full double precision
accuracy. This example illustrates the
power of interval techniques for automated error analysis. An
interval answer carries with it a guarantee of its uncertainty. By
contrast, a point value carries no measure of its
uncertainty. Even a sound error analysis can only estimate the
error.
Interval techniques should also be considered when input data or
parameters in the problem are uncertain. For example, if we replace
the point valued coefficients of $ A $ in Equation
(\ref{Least_Squares}) by intervals whose endpoints differ in the 4th
decimal place, we get intervals containing the solution. The width
of the solution intervals is a measure of the uncertainty in the
answer as a result of uncertainty in the data. This is a type of
sensitivity analysis which can replace costly, repeated simulation
runs.
However, if the interval coefficients of $ A $ in our problem
are only one
double precision unit wide, ACRITH's linear equation solver finds
that $ A $ contains a singular matrix. That is, the data differs from
a singular problem by less than double precision accuracy. Since the
data is certainly not known with double precision accuracy, the
tight inclusions shown in Listing 3 are meaningless. In the
terminology of \cite{Kuli88a}, we have solved the specified least
squares problem with high accuracy, but the specified problem has no
physical meaning. We would prefer to be assured that everything is
fine, but if we are attempting to solve a meaningless problem, we
welcome a warning of that fact.
This example illustrates that
\begin {enumerate}
\item It is possible to solve poorly conditioned linear
systems with high accuracy.
\item It is possible to be guaranteed of the accuracy
attained.
\item ACRITH can tell us when our problems are too poorly
conditioned relative to their input data to render any
computed solution physically meaningless.
\end {enumerate}
\beginsection {5. An example - Nonlinear systems}
Another example of the application of interval techniques is
the Nordgren crack model \cite{Nord72a}. The underlying mathematical
problem is a partial differential equation with a moving boundary. Let
$ w(x,t) $ be the width of the crack at position $ x $ and time
$ t $. Let $ L(t) $ be the length of the crack at time $ t $, and
$ \tau (x) $ be the time required for the crack to reach length
$ x $. Then $ w(x, t) $ satisfies the PDE:
\begin {eqnarray}
(w^4)_{xx} & = & w_t + \frac {1}{\sqrt {t - \tau (x)}},
\quad 0 \le x \le L(t), 0 \le t,
\nonumber \\
-(w^4)_x(0, t) & = & 1
\quad \mbox {(flow from wellbore is constant)}
\label {Nordgren} \\
w^4(x,0) & = & 0
\quad \mbox {(crack starts opening at $ t = 0 $)}
\nonumber \\
w^4(L(t), t) & = & 0
\quad \mbox {(no flow at the crack tip)}
\nonumber \\
-(w^4)_x (L(t), t) & = & \frac {dL}{dt} \cdot w(L(t), t)
\nonumber \\
&& \qquad \qquad \mbox {(fluid velocity equals tip propagation speed)}
\nonumber \\
& \mbox {or} &
\nonumber \\
-(w^4)_x (L(t), t) & = & 0
\quad \mbox {(no volume of fluid flow at the tip).}
\nonumber
\end {eqnarray}
A standard algorithm uses a discretization in $ x $ and
$ t $ to form finite difference approximations to the partial
derivatives appearing in Equation (\ref{Nordgren}). At each time
step $ t_j $, one must solve a nonlinear system of equations for
$ w_{i,j} = w(x_i, t_j) $ using a Newton iteration. A conventional
implementation of this algorithm gave results which agreed with
asymptotic results and with results computed by Nordgren. However,
after about 100 time steps, the solution failed when the program
attempted to take the square root of a negative number.
Consider the approximations made in modeling the crack:
\begin {enumerate}
\item The physical behavior of cracking rock is approximated
by Equation (\ref{Nordgren}).
\item Equation (\ref{Nordgren}) has exact solution $ w(x,t) $.
\item Equation (\ref{Nordgren}) is approximated by finite
difference equations.
\item The finite difference equations have exact solution
$ w_{i,j} $ which approximates $ w(x,t) $.
\item At time step $ t_j $, $ w_{i,j} $ is approximated by a
sequence of Newton iterates based on approximations to
$ w_{i,j-1} $.
\end {enumerate}
No interval algorithms for Problem (\ref{Nordgren}) are known, but
we can use interval techniques to explore the behavior of the point
algorithm. We do not attempt to compute an inclusion for $ w(x, t) $.
Instead, we take as our specified problem the finite difference
equations which define $ w_{i,j} $.
Suppose we assume that $ w_{i,j-1} $ at time step $ t_j $ are
known exactly. Then the values $ w_{i,j} $ satisfy a system of
$ j + 1 $ nonlinear
equations. The interval Newton algorithm \cite{Moor79a} computes 1
ULP inclusions for $ w_{i,j} $. This gives inclusions for $ w_{i,j}
$, not for $ w(x, t) $, and not for the width of the physical crack.
Further, the algorithm of assumes that $ w_{i,j-1} $ are exact,
which they are not. Hence, we have an inclusion of the answer which
the point algorithm in Step 5 above should have computed.
The interval program described in the preceding paragraph showed
that as time passes, the Newton iteration becomes extremely
sensitive to the initial guess for $ w_{i,j} $ used to
start the iteration. The problem is not with the convergence of
the Newton iteration, but that a very carefully constructed
initial guess is required to evaluate the first Newton
iteration. The interval algorithm gives us a better understanding
of the behavior of the point algorithm, so we can improve its
performance.
Another approach is to view the entire set of $ w_{i,j} $ for
$ 0 < j \le N $ as determined by a single system of
$ (N + 1)(N + 2) / 2 $ nonlinear equations. Solving as a single
system rather than solving one time step at a time allows us to
compute inclusions for $ w_{i,j} $ without assuming that $ w_{i,j-1}
$ are exact. Further, the widths at earlier times are automatically
computed with sufficient accuracy to allow the widths at later times
to be computed with 1 ULP inclusions.
This is a slight improvement over the previous algorithm
because it gives inclusions for all the $ w_{i,j} $ without
assuming that some are known exactly.
The result is {\em not\/} an inclusion for $ w(x,t) $
because we have taken the finite difference equations as our
specified problem. To
compute an inclusion for $ w(x,t) $ requires an interval algorithm,
not just an interval version of a point algorithm. Interval
algorithms for PDE's are under development. One could capture the
truncation error in the finite difference approximations to the
derivatives, but a better interval algorithm will probably result
from an application of a maximum principle or from reformulating
the PDE as an integral equation and applying a contractive mapping.
The nonlinear equation solver in ACRITH was overly restrictive
for this application, so we had to write our own. We estimate that
it took approximately 60 -- 100 times as long to write our own
interval Newton algorithm following \cite{Moor79a} than would be
required to simply use an existing point nonlinear equation solver
from the IMSL or NAG libraries.
\beginsection {6. What are some limitations of interval techniques?}
We do not pretend that interval techniques are the solution to
all scientific computation problems. Among the difficulties
involved in using interval techniques are:
\begin {enumerate}
\item What do we get an inclusion of?
\item How do we develop interval algorithms?
\item How do we develop interval models?
\item Is it worth the cost?
\end {enumerate}
We address each of these in turn.
\subsect {6.1. What do we get an inclusion of?}
Interval problems should be interpreted in the sense of sets.
For example, consider the interval valued system of linear
equations
\begin {equation}
A \vector {x} = \vector {b},
\label {Interval_System}
\end {equation}
where the elements of the matrix $ A $ and of the vector
$ \vector {b} $ are intervals. Let $ \tilde {A} $ be any
point valued matrix such that $ \tilde {A}_{i,j} \in A_{i,j} $,
and let $ \tilde {\vector {b}} $ be any point valued vector with
$ \tilde {b}_i \in b_i $. Let $ \tilde {\vector {x}} $
be the solution to the point valued problem
$ \tilde {A} \tilde {\vector {x}} = \tilde {\vector {b}} $. Then, the meaning
of having an interval valued vector $ \vector {x} $ which solves Equation
(\ref{Interval_System}) is that it must hold that
$ \tilde {x}_i \in x_i $. That is, the solution to the interval problem
contains the solution to every possible point problem.
Having an interval answer does not guarantee that it
includes anything of interest, as we saw in the discussion above
of the Nordgren crack model. To achieve a meaningful inclusion
requires careful mathematical reasoning at all stages of algorithm
development and implementation.
For example, suppose that we have a code which computes a
numerical solution to a system of ordinary differential equations
using a Runge-Kutta algorithm. Suppose that we are
concerned about the accuracy of the computed solution, so we
convert the point arithmetic in the code to interval
arithmetic using calls to ACRITH routines. The resulting interval
answers are {\em useless\/} for two reasons:
\begin {enumerate}
\item They enclose the Runge-Kutta approximation to the solution,
not the solution itself. In order to enclose the solution,
we must extend the algorithm to include an inclusion of
the truncation error term.
\item They are hopelessly wide. In order to achieve the
desired {\em tight\/} inclusions, algorithms must be
interval algorithms, not naive interval versions of
point algorithms.
\end {enumerate}
Both of these reasons suggest that it is often necessary to develop
algorithms which are designed from the beginning as interval
algorithms.
As a practical matter, it may not be necessary or
cost-effective to develop an interval algorithm for an entire
problem. Instead, interval techniques can often be profitably
applied to small subproblems of a larger problem. For example, the
original algorithm may require the solution of a linear system, a
nonlinear system, or an optimization problem. If the accuracy or
reliability of one of these subproblems is suspected, an interval
solution of the subproblem is suggested. The result will not be an
inclusion for the solution of the entire problem, but the result
may provide increased confidence or insight.
The example given above of the nonlinear system from a Nordgren
crack model illustrates these points. There, we applied interval
techniques the subproblem of solving the nonlinear system, either
at one time step at a time, or for the entire time domain of
interest. We were very careful to identify what we were computing
an inclusion of. The use of interval techniques was valuable
because we gained insights which allowed us to improve performance
of our calculations.
\subsect {6.2. How do we develop interval algorithms?}
Good point algorithms rarely make good interval algorithms.
Hence, when developing interval algorithms, it is necessary to
discard much of the conventional wisdom of numerical analysis and
perform a fresh analysis of each problem. In what follows, we give
some useful hints.
The development of good interval algorithms begins with a
search of computer and written libraries for existing tools or
algorithms which can be applied. The ACRITH library contains many
useful problem solving routines.
Interval algorithms often involve computing a point
approximation, followed by computing either an interval inclusion
near the approximation or an interval inclusion of the error of the
approximation.
When developing an algorithm using such a mix of point and
interval valued objects, special care must be taken to keep track of
which objects are points and which are intervals. It is usually
helpful to view an interval as a primitive data object on which
operations are performed using calls to ACRITH routines. In
computer science jargon, intervals form an abstract data type.
Thinking of the two endpoints as separate objects often leads to
confusion. Fortran-SC \cite{Metz87a} supports interval as a
primitive data type at the language level.
Interval algorithms are developed to enclose mathematical
results. For example, if $ a \in A = [1, 2] $, then
$ a - a = 0 $, while $ A - A = [-1, 1] $. Similarly,
if $ B = [-1, 2] $, then $ B * B = [-2, 4] $, while
$ B^2 = [0, 4] $. Hence, equivalent mathematical expressions
are not necessarily equivalent interval expressions.
Fundamental tools for achieving a guaranteed inclusion use
interval arithmetic and must capture of all sources of errors
including modeling errors, approximation errors, truncation errors,
discretization errors, and roundoff errors. Differentiation
arithmetic \cite{Rall81a} is often helpful to capture derivatives
evaluated at unknown points which appear in error terms for many
algorithms. Differentiation arithmetic uses recurrence relations
for the fast, accurate generation of the terms of the Taylor series.
Achieving an inclusion is often a separate issue from
achieving a {\em tight\/} inclusion.
Mathematical ``tricks'' which are commonly used in good interval
algorithms to achieve inclusions which are tight include
\begin {itemize}
\item interval arithmetic,
\item formula + remainder,
\item subinterval adaptation,
\item monotonicity,
\item use of point values,
\item high order methods,
\item differentiation arithmetic,
\item intersection of multiple inclusions, and
\item contractive iteration.
\end {itemize}
In \cite{Corl88a}, Corliss illustrates these techniques using
several algorithms for computing bounds for the range of a function
on an interval.
\subsect {6.3. How do we develop interval models?}
Pursuit of an interval strategy often affects the way we build
the original mathematical models. In general, we want to
solve a problem as close as possible to the original one.
If we formulate problem $ P_1 $, do some approximation to get
problem $ P_2 $, do some further approximation to get problem
$ P_3 $, and finally solve several subproblems, we have many
sources of error which must be bounded in order to get a guaranteed
inclusion of the solution to the original problem. It is usually
better to solve problem $ P_1 $, if we can.
We cannot always solve $ P_1 $. Even when we can, we
may not be able to compute an inclusion. As a compromise, it may
be useful to find guaranteed inclusions of the solution to some
subproblems or of some approximate solution to the original
problem. In this case, be careful to understand clearly what the
answer is an inclusion of.
Pursuit of an interval strategy often encourages one to
develop models in terms of lower and upper bounds. This is
especially useful when details of the physical problem are
uncertain but can be shown to have little affect on the outcome.
\subsect {6.4. Is it worth the cost?}
Interval algorithms incur costs for learning an unfamiliar
approach, for programmer time, and for CPU time.
Interval techniques are not usually as well known among
scientists and engineers as point techniques, so there is a cost
associated with learning new approaches and new tools.
There are fewer ready-made interval programs in either computer
software libraries or in the literature. Further, an interval
algorithm is usually more difficult to write than a point algorithm
for the same problem. For these reasons, the design and
implementation of a complete integral algorithm may require 4 -- 8
times as much programmer time as the design and implementation of
a point algorithm. If the choice is between designing and writing
your own interval algorithm and using an existing high quality
point routine, the cost may be a factor of hundreds. Hopefully,
this will be less frequent as more high quality interval routines
are developed.
This cost should be balanced against the value of increased
insight provided by verified bounds for the computed answers.
An interval algorithm carries lower and upper bounds throughout
its calculations. Hence, it nearly always requires twice as
much CPU time as a corresponding point algorithm. In practice, a
good interval algorithm typically takes about 3 -- 5 times as much
CPU time as a good point algorithm. It is possible for an interval
algorithm to be faster than a point algorithm, especially when a
tolerance is requested, because the interval program can determine
exactly when the requested tolerance is met. It is also possible
for an interval algorithm to take much longer.
The increased CPU cost should be balanced against the cost
of repeated runs for simulation, with perturbed data, or in higher
precisions.
\beginsection {7. What should you DO?}
We recommend:
\begin {itemize}
\item Determine whether the ACRITH accurate scalar
product routines are faster or slower than the corresponding
DO loop on your machine. If they are faster, use them
whenever possible.
\item Use ACRITH accurate scalar product routines for
vector summations and scalar products.
\item Include the ACRITH library among the libraries you
customarily search when you are looking for existing
software to help solve your problem.
\item Consider older, simpler algorithms whose bad reputation is
due to an accumulation of roundoff errors which can be
minimized by an accurate scalar product.
\item Determine whether the potential benefits of
ACRITH's high accuracy tools justify your effort to learn
how to use them by applying them first to small problems to
gain experience in your own setting.
\item Learn to recognize problems for
which interval techniques should be considered because you would
like to know the accuracy of the answer you have computed.
\item Learn to recognize problems for
which interval techniques should be considered because the input
data or the parameters in the problem are uncertain.
\item Consider interval techniques as an alternative to
repeated simulation runs for sensitivity analysis.
\item Apply interval techniques to
small subproblems of larger, more complicated problems.
\end {itemize}
The following references are good places to start.
R. E. Moore, {\sl Methods and Applications of Interval
Analysis,\/} \cite{Moor79a} and G. Alefeld and J. Herzberger,
{\sl Introduction to Interval Computations,\/} \cite{Alef83a} are
good introductory surveys of interval methods.
K. Nickel, ed., {\sl Interval Mathematics, 1975,\/}
\cite{Nick75a}, {\sl Interval Mathematics, 1980,\/} \cite{Nick80a},
and {\sl Interval Mathematics, 1985,\/} \cite{Nick85a} are each
collections of papers presented at a prestigious conference held in
Freiburg.
R. E. Moore, ed., {\sl Reliability in Computing: The Role of
Interval Methods in Scientific Computing,\/} \cite{Moor88a} is a
collection of 22 research articles in the field.
The ACRITH User's Guide \cite{IBM86a} and the Pascal-SC User's
Manual \cite{Kuli87a} are excellent descriptions of two
commercially available products which make interval tools widely
accessible.
\beginsection {Acknowledgments}
The author wishes to thank a client whose wish to remain anonymous
prevents giving the appropriate credit for work done by several
of its scientists. Professor Edgar Kaucher suggested the matrix
reformulations in Section 2. The author also wishes to thank
Professors L. B. Rall and Gary S. Krenz for many helpful
discussions.
\begin {thebibliography}{99}
\bibitem {Alle74a}
Allen, D. M.
The relationship between variable selection and data
augmentation and a method for prediction,
{\sl Techonometrics,\/} {\bf 16} (1974), 125--127.
\bibitem {Alef83a}
Alefeld, G.; and Herzberger, J.
{\sl Introduction to Interval Computations,\/}
Academic Press, New York 1983.
\bibitem {Corl88a}
Corliss, George F.
How can you apply interval techniques in an industrial setting?
Technical Report No. 301, Department of Mathematics,
Statistics and Computer Science, Marquette University,
Milwaukee, WI 1988.
\bibitem {Delv87a}
Delves, L. M.; Ford, B.; and Hodgson, G. S.
The MAP 750 Ada Library Project,
{\sl NAG Newsletter,\/} {\bf 2} (1987), 29--38.
\bibitem {Hest52a}
Hestenes, M.; and Stiefel, E.
Methods of conjugate gradients for solving linear systems,
{\sl Nat. Bur. Standards J. Res.,\/}
{\bf 49} (1952), 409--436.
\bibitem {Hoag78a}
Hoaglin, David C.; and Welsch, Roy E.
The hat matrix in regression and ANOVA,
{\sl The American Statistician,\/}
{\bf 32} (1978) 1, 17--22.
\bibitem {IBM86a}
IBM.
{\sl High-Accuracy Arithmetic Subroutine Library (ACRITH),\/}
Program Description and User's Guide, SC 33--6164--2, 3rd Edition
1986.
\bibitem {Kuli81a}
Kulisch, Ulrich W.; and Miranker, Willard L.
{\sl Computer Arithmetic in Theory and Practice,\/}
Academic Press, New York 1981.
\bibitem {Kuli83a}
Kulisch, Ulrich W.; and Miranker, Willard L.
{\sl A New Approach to Scientific Computation,\/}
Academic Press, New York 1983.
\bibitem {Kuli87a}
Kulisch, Ulrich W. (ed.).
{\sl Pascal-SC: A PASCAL Extension for Scientific Computation,\/}
Information Manual and Floppy Disks,
Teubner, Stuttgart, and Wiley, New York 1987.
\bibitem {Kuli88a}
Kulisch, Ulrich W.; and Stetter, Hans J.
Automatic result verification.
In: Kulisch, Ulrich W.; and Stetter, Hans J. (eds.):
{\sl Scientific Computation with Automatic Result Verification,\/}
Springer, New York 1988, pp. 1 -- 8.
\bibitem {Metz87a}
Metzger, M.
FORTRAN-SC, A FORTRAN extension for engineering/scientific
computing with access to ACRITH.
In: Moore, Ramon E. (ed.):
{\sl Reliability in Computing: The Role of Interval Methods
in Scientific Computing,\/}
Academic Press, New York 1988, pp. 63--80.
\bibitem {Moor66a}
Moore, Ramon E.
{\sl Interval Analysis\/},
Prentice-Hall, Englewood Cliffs, NJ 1966.
\bibitem {Moor79a}
Moore, Ramon E.
{\sl Methods and Applications of Interval Analysis,\/}
SIAM, Philadelphia, PA 1979.
\bibitem {Moor88a}
Moore, Ramon E. (ed.).
{\sl Reliability in Computing: The Role of Interval Methods
in Scientific Computing,\/}
Academic Press, New York 1988.
\bibitem {Nick75a}
Nickel, Karl L. E. (ed.).
{\sl Interval Mathematics, 1975,\/}
Springer, New York 1975.
\bibitem {Nick80a}
Nickel, Karl L. E. (ed.).
{\sl Interval Mathematics, 1980,\/}
Academic Press, New York 1980.
\bibitem {Nick85a}
Nickel, Karl L. E. (ed.).
{\sl Interval Mathematics, 1985,\/}
Springer, New York 1985.
\bibitem {Nord72a}
Nordgren, R. P.
Propagation of vertical hydraulic fracture,
{\sl Society of Petroleum Engineers Journal\/}
{\bf 12} (1972) 4,
306--314.
\bibitem {Rall81a}
Rall, Louis B.
{\sl Automatic Differentiation: Techniques and Applications,\/}
Lecture Notes in Computer Science No. 120,
Springer, Berlin 1981.
\bibitem {Siem86a}
Siemens.
{\sl Arithmos, (BS 2000) Benutzerhandbuch,\/}
U2900--J--Z87--1, Siemens, GmbH 1986.
\end {thebibliography}
\end {document}
----- End Included Message -----
From owner-reliable_computing Sat Dec 23 09:31:03 1995
Received: by interval.usl.edu id AA15007
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 23 Dec 1995 03:03:04 -0600
Received: from c220.unimo.it by interval.usl.edu with SMTP id AA15001
(5.65c/IDA-1.4.4 for ); Sat, 23 Dec 1995 03:02:34 -0600
Received: from dsi.unimo.it (iago.dsi.unimo.it) by c220.unimo.it with ESMTP
(1.39.111.2/16.2) id AA285336294; Sat, 23 Dec 1995 09:58:14 -0100
Received: (from benedett@localhost) by dsi.unimo.it (8.6.11/8.6.9) id IAA00112; Sat, 23 Dec 1995 08:31:03 +0100
Date: Sat, 23 Dec 1995 08:31:03 +0100
From: Arrigo Benedetti
Message-Id: <199512230731.IAA00112 [at] dsi [dot] unimo.it>
To: georgec [at] boris [dot] mscs.mu.edu
Cc: reliable_computing [at] interval [dot] usl.edu
In-Reply-To: (georgec [at] boris [dot] mscs.mu.edu)
Subject: Re: Applications of intervals (long)
Sender: owner-reliable_computing
Precedence: bulk
Date: Fri, 22 Dec 95 15:33 CST
From: georgec [at] boris [dot] mscs.mu.edu (Dr. George F. Corliss MU MSCS)
X-Sun-Charset: US-ASCII
Sender: owner-reliable_computing [at] interval [dot] usl.edu
Precedence: bulk
Raj,
> I am looking for help in collecting following information to convince
> a group of people in using Interval Arithmetic for verified computing
> in problems where safety issues are important in the design of a
> physical system.
Here are some stories I know. Interval techniques are no "silver
bullet", but they CAN provide insight.
[omitted]
7. I headr a wonderful talk by Wolfram Klein at SCAN 95 in Wuppertal
about using interval techniques and automatic differentiation for
a circuit simulation problem.
[omitted]
Dear Prof. Corliss,
I am very interested in this point, as one of my interests is in the
application of interval methods to circuit design and simulation problems.
Could you please give me contact informations for Wolfram Klein, so I can
get in touch with him?
Thanks in advance,
-Arrigo Benedetti
--
Arrigo Benedetti e-mail: benedett [at] dsi [dot] unimo.it
University of Modena abenedetti [at] deis [dot] unibo.it
address: Via Vivaldi, 70 41100 MODENA - ITALY
phone: (home) + 39 59 224929 (office) +39 59 304057 (fax) +39 59 220727
http://deis12.cineca.it/~benedett/ <-- under construction !
From owner-reliable_computing Sat Dec 23 05:32:49 1995
Received: by interval.usl.edu id AA15335
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 23 Dec 1995 11:33:21 -0600
Received: by interval.usl.edu id AA15325
(5.65c/IDA-1.4.4 for reliable_computing [at] interval [dot] usl.edu); Sat, 23 Dec 1995 11:32:49 -0600
Date: Sat, 23 Dec 1995 11:32:49 -0600
From: "Kearfott R. Baker"
Message-Id: <199512231732.AA15325 [at] interval [dot] usl.edu>
To: georgec [at] boris [dot] mscs.mu.edu, benedett [at] dsi [dot] unimo.it
Subject: Re: Applications of intervals (long)
Cc: reliable_computing [at] interval [dot] usl.edu
Sender: owner-reliable_computing
Precedence: bulk
> Dear Prof. Corliss,
>
> I am very interested in this point, as one of my interests is in the
> application of interval methods to circuit design and simulation problems.
> Could you please give me contact informations for Wolfram Klein, so I can
> get in touch with him?
>
While we are on this topic, I might add that Kohshi Okumura
(kohshi [at] kuee [dot] kyoto-u.ac.jp) has applied interval methods very effectively
to circuit problems.
---------------------------------------------------------------
R. Baker Kearfott, rbk [at] usl [dot] edu (318) 482-5346 (fax)
(318) 482-5270 (work) (318) 981-9744 (home)
URL: ftp://interval.usl.edu/pub/interval_math/www/kearfott.html
Department of Mathematics, University of Southwestern Louisiana
---------------------------------------------------------------
From owner-reliable_computing Sat Dec 23 18:28:16 1995
Received: by interval.usl.edu id AA15511
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Sat, 23 Dec 1995 11:59:58 -0600
Received: from c220.unimo.it by interval.usl.edu with SMTP id AA15501
(5.65c/IDA-1.4.4 for ); Sat, 23 Dec 1995 11:59:38 -0600
Received: from dsi.unimo.it (iago.dsi.unimo.it) by c220.unimo.it with ESMTP
(1.39.111.2/16.2) id AA015148521; Sat, 23 Dec 1995 18:55:21 -0100
Received: (from benedett@localhost) by dsi.unimo.it (8.6.11/8.6.9) id RAA00117; Sat, 23 Dec 1995 17:28:16 +0100
Date: Sat, 23 Dec 1995 17:28:16 +0100
From: Arrigo Benedetti
Message-Id: <199512231628.RAA00117 [at] dsi [dot] unimo.it>
To: rbk5287 [at] interval [dot] usl.edu
Cc: georgec [at] boris [dot] mscs.mu.edu, reliable_computing [at] interval [dot] usl.edu
In-Reply-To: <199512231732.AA15325 [at] interval [dot] usl.edu> (rbk5287 [at] interval [dot] usl.edu)
Subject: Re: Applications of intervals (long)
Sender: owner-reliable_computing
Precedence: bulk
Date: Sat, 23 Dec 1995 11:32:49 -0600
From: "Kearfott R. Baker"
Cc: reliable_computing [at] interval [dot] usl.edu
> Dear Prof. Corliss,
>
> I am very interested in this point, as one of my interests is in the
> application of interval methods to circuit design and simulation problems.
> Could you please give me contact informations for Wolfram Klein, so I can
> get in touch with him?
>
While we are on this topic, I might add that Kohshi Okumura
(kohshi [at] kuee [dot] kyoto-u.ac.jp) has applied interval methods very effectively
to circuit problems.
Nice to hear from you again Prof. Baker Kearfott, and thank you very much
for this information. By the way, recently Prof. Neumaier, when asked
to comment a paper that we wrote recently, suggested to read your
papers on existence conditions for undetermined systems as
a way to overcome some of the problems that we have with an algorithm
for tracing solution curves of nonlinear circuits.
If you are interested, I can send you a postscript copy of our paper,
that will be presented at ISCAS'96 (IEEE International Symposium on
Circuits and Systems).
Let me give you my best wishes for a merry Xmas and happy New Year,
-Arrigo Benedetti
--
Arrigo Benedetti e-mail: benedett [at] dsi [dot] unimo.it
University of Modena abenedetti [at] deis [dot] unibo.it
address: Via Vivaldi, 70 41100 MODENA - ITALY
phone: (home) + 39 59 224929 (office) +39 59 304057 (fax) +39 59 220727
http://deis12.cineca.it/~benedett/ <-- under construction !
From owner-reliable_computing Tue Dec 26 03:35:31 1995
Received: by interval.usl.edu id AA17529
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Tue, 26 Dec 1995 13:50:28 -0600
Received: from mercury.Sun.COM by interval.usl.edu with SMTP id AA17523
(5.65c/IDA-1.4.4 for ); Tue, 26 Dec 1995 13:50:22 -0600
Received: from Eng.Sun.COM by mercury.Sun.COM (Sun.COM)
id LAA25954; Tue, 26 Dec 1995 11:49:29 -0800
Received: from roundoff.Eng.Sun.COM by Eng.Sun.COM (5.x/SMI-5.3)
id AA12951; Tue, 26 Dec 1995 11:49:26 -0800
Received: by roundoff.Eng.Sun.COM (5.x/SMI-SVR4)
id AA09085; Tue, 26 Dec 1995 11:35:31 -0800
Date: Tue, 26 Dec 1995 11:35:31 -0800
From: Douglas.Priest [at] eng [dot] sun.com (Douglas Priest)
Message-Id: <9512261935.AA09085 [at] roundoff [dot] Eng.Sun.COM>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Handling exceptions in interval operations
Sender: owner-reliable_computing
Precedence: bulk
I am looking for references which describe methods for dealing with
floating point exceptions, in particular IEEE 754 invalid operation
exceptions, in basic interval arithmetic operations. Any information
readers of this mailing list can provide would be greatly appreciated.
Thank you,
Douglas M. Priest
From owner-reliable_computing Fri Dec 29 13:23:02 1995
Received: by interval.usl.edu id AA04360
(5.65c/IDA-1.4.4 for reliable_computing-outgoing); Fri, 29 Dec 1995 21:23:09 -0600
Received: from cs.utep.edu by interval.usl.edu with SMTP id AA04354
(5.65c/IDA-1.4.4 for ); Fri, 29 Dec 1995 21:23:05 -0600
Received: from earth.cs.utep.edu by cs.utep.edu (4.1/SMI-4.1)
id AA02324; Fri, 29 Dec 95 20:23:02 MST
Date: Fri, 29 Dec 95 20:23:02 MST
From: vladik [at] cs [dot] utep.edu (Vladik Kreinovich)
Message-Id: <9512300323.AA02324 [at] cs [dot] utep.edu>
To: reliable_computing [at] interval [dot] usl.edu
Subject: Happy New Year
Sender: owner-reliable_computing
Precedence: bulk
* * * . *
* * . . . .
. . _ _ * * . * *
* . (*) (*) . . * . * .
* . | |_| | __ _ _ __ _ __ * _ _ . * .
* * | _ | / _' )( '_ \ ( '_ \ ( ) ( ) .
. . * |=| |=|(=(_|=||=(_)=)|=(_)=)|=\_/=| * *
* (_) (_) \__,_)| ,__/ | ,__/ \__ ( .
* | | | | ____) | * .
. * . * . (_) (_) (_____/ *
_ _ . * . . . _ . _ * * . _ *
* (*) (*) . * . . (*) (*) . * (*)
| \| | ____ _ _ _ \ \_/ / ____ __ _ _ __ | | *
* | \ | / __ \( ) ( ) ( ) . \ / / __ \ / _' )( '__)|_| .
. |=|\==|(=====/|=\_/=\_/=| |=| (=====/(=(_|=||=| =
(_) (_) \____) \___^___/ * (_) \____) \__,_)(_) (_) * .
* * . * . * . .
. * . . * * . * *