Fault-tolerant systems for the computation of eigenvalues and singular values

The computations of eigenvalues and singular values are key to applications including signal and image processing. Since large amounts of computation are needed for these algorithms, and since many digital signal processing applications have real-time requirements, many different special-purpose processor array structures have been proposed to solve these two algorithms. This paper develops a new methodology to incorporate fault tolerance capability into processor arrays which have been proposed for these problems. In the first part of this paper, earlier techniques of algorithm-based fault tolerance are applied to QR factorization and QR iteration. This technique encodes input data at a high level by using the specific property of each algorithm and checks the output data before they leave the systems. In the second part of the paper, special properities of eigenvalues and singular values are used to achieve the error detection without encoding the input data. Fault location and reconfiguration are performed only after an erroneous signal has been detected. The introduced overhead is extremely low in terms of both hardware and time redundancy.