Fault-tolerant algorithm for Fast Fourier Transform on hypercubes

摘要

Consider an input sequence of 2~n data and an n-dimensional hypercube, H_n, with n-1 faulty nodes. This short paper presents an efficient fault-tolerant algorithm for Fast Fourier Transform (FFT) with these 2~n data on the faulty H_n in 9n-15 communication steps and O(n) computation steps. To the best of our knowledge, this is the first time that such a fault-tolerant algorithm for FFT on hypercubes is proposed in the literature.