Parallel Computing, 18 (1992), pp. 649-659.
Ömer Egecioglu and Cetin K. Koc
A Parallel Algorithm for Generating Discrete Orthogonal Polynomials
Abstract.
A parallel algorithm that makes use of the classical three-term recursion
formula to construct an orthogonal family of polynomials with respect to
a discrete inner product is proposed. The algorithm requires O(Nlog N)
parallel arithmetic steps on a distributed-memory multiprocessor with
N+1 processors to construct the polynomials p_i(x) for
0 <= i <= N. If hypercube topology is assumed, the algorithm
can be implemented with the additional overhead of O(Nlog N)
routing steps. In this case the implementation is quite simple, requiring
only scalar single node broadcast and accumulation procedures together with
a Gray code mapping. The limited processor version of the algorithm requires
O({N^2}/p + Nlog p) arithmetic and O(Nlog p) routing steps on a
hypercube with p <= N+1 nodes. We present some experimental results
obtained on an Intel cube.
omer@cs.ucsb.edu