🚀 go-pugleaf

In article <KHB.91Jun11185538@chiba.Eng.Sun.COM>, khb@chiba.Eng.Sun.COM (Keith Bierman fpgroup) writes:
> 
> In article <9106120054.AA19903@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
> 
>    instructions into the IEEE standard and they have been implemented
>    in hardware in many machines.  Interval arithmetic still hasn't
>    gotten off the ground.  How long are we expected to wait until
>    concluding it's not going to fly.
> 
> Until vendors (other than apple and sun) provide hooks that people can
> actually use. Had such hooks been part of _any_ language standard, I
> suspect folks with such interests would have merrily coded up systems.
> 
>        3. The real problem with interval arithmetic is not that it's
>    slow but that on real applications its error estimates are gener-
>    ally so pessimistic as to be useless.
> 
> At last, something we agree on! But I confess that I have not used it
> extensively, so I am prepared to believe that it may have utility I am
> not personally cognizant of. Interval techniques will have to be
> deployed in large quantities before it can be counted out

Obviously, these discussions are about the *naive* approach to interval
arithmetic, replacing all floating-point numbers by intervals and re-
placing all floating-point operations of an algorithm by interval 
operations. - In consequence, a huge inflation occurs, if the number
of operations increases, because dependent quantities are handled like
independent quantities.

A simple example:  With X being an interval,  X - X  is not equal to 
zero(in general), but yields an interval, which lies symmetrically 
around zero and has a diameter twice as great as that of X. This is
because the resulting interval must include all differences between 
any two values out of X at interval subtraction. The second operand is
independently chosen from the first.

Hence, interval arithmetic must be applied to special algorithms for
achieving highly accurate results. Since more than one decade, mathe-
maticians at the University of Karlsruhe (Germany) designed such methods,
which are based on fixed point theorems (Brouwer) and yield highly
accurate verified solutions - even in ill-conditioned cases.

Example: The Hilbert matrix of dimension 14 has the condition number 
1.85e+19. The inverse of that matrix can be computed with maximum accuracy
(all components are intervals without any floating-point number between 
the lower and the upper bound!) using the IEEE double extended format and
an implementation of the scalarproduct with maximum accuracy. Furthermore
the algorithm yields not only the optimal verified enclosure of the solu-
tion, but proves its existence and its uniqueness, too.

Stefan Koenig

--------------------------------------------------------------------------

Here are some references for details.

@ARTICLE{BRUG87,
	AUTHOR = "G. Bohlender and L.B. Rall and Chr. Ullrich and J. Wolff von 
		Gudenberg ",
	TITLE     = "{PASCAL-SC: A Computer Language for Scientific 
		Computation}",
	JOURNAL = "Perspectives in computing",
	VOLUME = "17",
	YEAR       = "1987",
	NOTE	= "Orlando"}

@INPROCEEDINGS{Bohl90,
	AUTHOR = {G. Bohlender},
	TITLE     = "{What do we need beyond IEEE Arithmetic?}",
	BOOKTITLE = "{Computer Arithmetic and Self-Validating Numerical Methods}",
	PUBLISHER = "Academic Press",
	EDITOR = "{Chr. Ullrich}",
	ADDRESS = "Boston",
	YEAR       = "1990"}

@ARTICLE{FSH88,
	AUTHOR = {H.C. Fischer and G. Schuhmacher and R. Haggenm{\"u}ller},
	TITLE     = "{Evaluation of Arithmetic Expression with  Guaranteed High
		Accuracy}",
	JOURNAL = "Computing, Suppl.",
	VOLUME = "6",
	PAGES	= "149--158",
	YEAR       = "1988",
	NOTE	= "Springer, Wien"}

@BOOK{KM84,
	AUTHOR = "E. Kaucher and W.L. Miranker:",
	TITLE     = "{Self-Validating Numerics for Function Space Problems}",
	PUBLISHER = "Academic Press",
	ADDRESS = "New York",
	YEAR           = "1984"}

@BOOK{KM81,
	AUTHOR = "U. Kulisch and W.L. Miranker",
	TITLE     = "{Computer Arithmetic in Theory and Practice}",
	PUBLISHER = "Academic Press",
	ADDRESS = "New York",
	YEAR           = "1981"}

@BOOK{KM83,
	EDITOR = "U. Kulisch and W.L. Miranker",
	TITLE     = "{A New Approach to Scientific Computation}",
	PUBLISHER = "Academic Press",
	ADDRESS = "New York",
	YEAR           = "1983"}

@ARTICLE{KS88,
	AUTHOR = "U. Kulisch and H.J. Stetter",
	TITLE     = "{Scientific Computation with Automatic Result 
		Verification}",
	JOURNAL = "Computing Supplementum",
	VOLUME = "6",
	YEAR       = "1988",
	NOTE   =  "Springer, Wien"}

@INPROCEEDINGS{Kauc85,
	AUTHOR =	"E. Kaucher",
	TITLE =		"Self-Validating Methods for Special Differential-Equation-Problems",
	BOOKTITLE =	"11th IMACS World Congress on System Simulation and Scientific Computation",
	YEAR =		"1985",
	PAGES =		"115",
	ORGANIZATION =	"IMACS",
	ADDRESS =	"Oslo, Norway"	}

@INPROCEEDINGS{Rall85,
	AUTHOR =	"L.B. Rall",
	TITLE =		"Computable Bounds for Solutions of Integral Equations",
	BOOKTITLE =	"11th IMACS World Congress on System Simulation and Scientific Computation",
	YEAR =		"1985",
	PAGES =		"119",
	ORGANIZATION =	"IMACS",
	ADDRESS =	"Oslo, Norway"	}

@INPROCEEDINGS{Rump82,
	AUTHOR =	"S.M. Rump",
	TITLE =		"Solving Algebraic Problems with High Accuracy",
	BOOKTITLE =	"10th IMACS World Congress on System Simulation and Scientific Computation",
	YEAR =		"1982",
	PAGES =		"389",
	ORGANIZATION =	"IMACS",
	ADDRESS =	"Montreal, Canada"	}


@INPROCEEDINGS{Mark89,
	AUTHOR =	"S. Markov",
	TITLE =		"Least-square Approximation under Interval Data",
	BOOKTITLE =	"International Symposium on Computer Arithmetic and Self-Validating Numerical Methods",
	YEAR =		"1989",
	PAGES =		"",
	ORGANIZATION =	"IMACS-GAMM-GI",
	ADDRESS =	"Basel, Switzerland"	}

@INPROCEEDINGS{Lohn89,
	AUTHOR =	"R. Lohner",
	TITLE =		"Computing Enclosures for the Solution of Nonlinear Parameter Dependent Systems 
				and Ordinary Boundary Value Problems",
	BOOKTITLE =	"International Symposium on Computer Arithmetic and Self-Validating Numerical Methods",
	YEAR =		"1989",
	PAGES =		"",
	ORGANIZATION =	"IMACS-GAMM-GI",
	ADDRESS =	"Basel, Switzerland"	}

@INPROCEEDINGS{Corl89,
	AUTHOR =	"G.F. Corliss",
	TITLE =		"How Can You Apply Interval Techniques in an Industrial Setting?",
	BOOKTITLE =	"International Symposium on Computer Arithmetic and Self-Validating Numerical Methods",
	YEAR =		"1989",
	PAGES =		"",
	ORGANIZATION =	"IMACS-GAMM-GI",
	ADDRESS =	"Basel, Switzerland"	}