ALGORITHMIC FAULT TOLERANCE USING THE LANCZOS METHOD

DANIEL L. BOLEY, RICHARD P. BRENT, GENE H. GOLUB, AND FRANKLIN T. LUK

Dedicated by Boley, Brent, and Luk, to their teacher Gene Golub on the occasion of his 15th birthday.

In memory of Jeffrey Speiser

Abstract

We consider the problem of algorithm-based fault tolerance, and make two contributions. First, we show how very general sequences of polynomials can be used to generate the checksums, so as to reduce the chance of numerical overflows. Second, we show how the Lanczos process can be applied in the error location and correction steps, so as to save on the amount of work and to facilitate actual hardware implementation.

Comments

Only the Abstract is given here. The full paper appeared as [1].

References

1. D. L. Boley, R. P. Brent, G. H. Golub and F. T. Luk, “Error correction via the Lanczos process”, SIAM J. on Matrix Analysis (Gene H. Golub birthday issue) 13 (1992), 312–332. rpb124.

(Boley) Dept of Computer Science, University of Minnesota, Minneapolis, MN 55455 E-mail address: boley@cs.umn.edu

(Brent) Computer Sciences Lab, Australian National University, Canberra, ACT 0200 E-mail address: rpb@cslab.anu.edu.au

(Golub) Department of Computer Science, Stanford University, Stanford, CA 94305 E-mail address: golub@na-net.stanford.edu

(Luk) School of Electrical Engineering, Cornell University, Ithaca, NY 14853 Current address: Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180 E-mail address: luk@cs.rpi.edu

1991 Mathematics Subject Classification. Primary 65F30; Secondary 65G99, 68M15. Key words and phrases. Lanczos process, fault tolerance, algorithmic fault tolerance, error location,

error correction, orthogonal polynomials, Krylov sequence, Reed-Muller code, overflow.

D. L. Boley was supported in part by the National Science Foundation under grant CCR-8813493, G. H. Golub by the Army Research Office under contract DAAL03-90-G-0105, and F. T. Luk by the Army Research Office under contract DAAL03-90-G-0104.

Received January 25, 1991; accepted July 30, 1991. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1992, SIAM. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb124a typeset using AMS-L^{A}TEX