Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!olivea!tardis!tymix!uunet!mcsun!cernvax!chx400!urz.unibas.ch!koenig From: koenig@urz.unibas.ch Newsgroups: comp.arch Subject: Re: IEEE arithmetic (Goldberg paper) Message-ID: <1991Jun20.104919.1657@urz.unibas.ch> Date: 20 Jun 91 09:49:18 GMT References: <9106120054.AA19903@ucbvax.Berkeley.EDU> Organization: University of Basel, Switzerland Lines: 170 In article , 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" }