James W. Demmel and Nicholas J. Higham

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-584
July 1990

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-584.pdf

Block algorithms are becoming increasingly popular in matrix computations. Since their basic unit of data is a submatrix rather than a scalar they have a higher level of granularity than point algorithms, and this makes them well-suited to high-performance computers. The numerical stability of the block algorithms in the new linear algebra program library LAPACK is investigated here. It is shown that these algorithms have backward error analyses in which the backward error bounds are commensurate with the error bounds for the underlying level 3 BLAS (BLAS3). One implication is that the block algorithms are as stable as the corresponding point algorithms when conventional BLAS3 are used. A second implication is that the use of BLAS3 based on fast matrix multiplication techniques affects the stability only insofar as it increases the constant terms in the normwise backward error bounds. For linear equation solvers employing LU factorization it is shown that fixed precision iterative refinement helps to mitigate the effect of the larger error constants. The analysis is illustrated with the aid of numerical examples.

BibTeX citation:

@techreport{Demmel:CSD-90-584,
    Author = {Demmel, James W. and Higham, Nicholas J.},
    Title = {Stability of Block Algorithms with Fast Level 3 BLAS},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5472.html},
    Number = {UCB/CSD-90-584},
    Abstract = {Block algorithms are becoming increasingly popular in matrix computations. Since their basic unit of data is a submatrix rather than a scalar they have a higher level of granularity than point algorithms, and this makes them well-suited to high-performance computers. The numerical stability of the block algorithms in the new linear algebra program library LAPACK is investigated here. It is shown that these algorithms have backward error analyses in which the backward error bounds are commensurate with the error bounds for the underlying level 3 BLAS (BLAS3). One implication is that the block algorithms are as stable as the corresponding point algorithms when conventional BLAS3 are used. A second implication is that the use of BLAS3 based on fast matrix multiplication techniques affects the stability only insofar as it increases the constant terms in the normwise backward error bounds. For linear equation solvers employing LU factorization it is shown that fixed precision iterative refinement helps to mitigate the effect of the larger error constants. The analysis is illustrated with the aid of numerical examples.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Higham, Nicholas J.
%T Stability of Block Algorithms with Fast Level 3 BLAS
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-584
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5472.html
%F Demmel:CSD-90-584