Title :
A Parallel Version of the Lindsey-Fox algorithm for factoring High Degree Polynomials in Signal Processing
Author :
Burrus, C. Sidney ; Fox, James ; Sitton, Gary ; Treitel, Sven
Author_Institution :
Polynomial Club, Rice Univ., Houston, TX
Abstract :
The Lindsey-Fox algorithm is a very efficient procedure for factoring very high degree polynomials that are reasonably well conditioned. It conducts a grid search by evaluating the polynomial using the fast Fourier transform (FFT) of the coefficients. The structure of the algorithm is such that it is easily implemented on a parallel computer. We present results of implementations on an AMD cluster and on a Cray XD1. The highest degree random coefficient polynomial factored so far is of 4 million
Keywords :
fast Fourier transforms; polynomials; signal processing; AMD cluster; Cray XD1; FFT; Lindsey-Fox algorithm; fast Fourier transform; grid search; high degree polynomials; parallel computer; signal processing; Approximation algorithms; Clustering algorithms; Concurrent computing; Fast Fourier transforms; Packaging; Polynomials; Robustness; Signal processing algorithms; Speech; Testing;
Conference_Titel :
Digital Signal Processing Workshop, 12th - Signal Processing Education Workshop, 4th
Conference_Location :
Teton National Park, WY
Print_ISBN :
1-4244-3534-3
Electronic_ISBN :
1-4244-0535-1
DOI :
10.1109/DSPWS.2006.265415
