Title :
A parallel algorithm for computing Fourier transforms on the star graph
Author :
Fragopoulou, Paraskevi ; Akl, Selim G.
Author_Institution :
Dept. of Comput. & Inf. Sci., Queen´´s Univ., Kingston, Ont., Canada
fDate :
5/1/1994 12:00:00 AM
Abstract :
The n-star graph, denoted by Sn, is one of the graph networks that have been recently proposed as attractive alternatives to the n-cube topology for interconnecting processors in parallel computers. We present a parallel algorithm for the computation of the Fourier transform on the star graph. The algorithm requires O(n2 ) multiply-add steps for an input sequence of n! elements, and is hence cost-optimal with respect to the sequential algorithm on which it is based. This is believed to be the first algorithm, and the only one to date, for the computation of the Fourier transform on the star graph
Keywords :
Fourier transforms; computational complexity; graph theory; multiprocessor interconnection networks; parallel algorithms; Fourier transforms; interconnecting processors; parallel algorithm; parallel computers; star graph; Computer networks; Concurrent computing; Cost function; Fast Fourier transforms; Fourier transforms; Helium; Hypercubes; Network topology; Parallel algorithms; Telecommunication computing;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
