Faster Numerical Algorithms via Exception Handling

James W. Demmel and Xiaoye Li

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-728
February 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-728.pdf

An attractive paradigm for building fast numerical algorithms is the following: (1) try a fast but occasionally unstable algorithm, (2) test the accuracy of the computed answer, and (3) recompute the answer slowly and accurately in the unlikely event it is necessary. This is especially attractive on parallel machines where the fastest algorithms may be less stable than the best serial algorithms. Since unstable algorithms can overflow or cause other exceptions, exception handling is needed to implement this paradigm safely. To implement it efficiently, exception handling cannot be too slow. We illustrate this paradigm with numerical linear algebra algorithms from the LAPACK library.


BibTeX citation:

@techreport{Demmel:CSD-93-728,
    Author = {Demmel, James W. and Li, Xiaoye},
    Title = {Faster Numerical Algorithms via Exception Handling},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6031.html},
    Number = {UCB/CSD-93-728},
    Abstract = {An attractive paradigm for building fast numerical algorithms is the following: (1) try a fast but occasionally unstable algorithm, (2) test the accuracy of the computed answer, and (3) recompute the answer slowly and accurately in the unlikely event it is necessary. This is especially attractive on parallel machines where the fastest algorithms may be less stable than the best serial algorithms. Since unstable algorithms can overflow or cause other exceptions, exception handling is needed to implement this paradigm safely. To implement it efficiently, exception handling cannot be too slow. We illustrate this paradigm with numerical linear algebra algorithms from the LAPACK library.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Li, Xiaoye
%T Faster Numerical Algorithms via Exception Handling
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-728
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6031.html
%F Demmel:CSD-93-728