Hierarchical Load–Balancing for Parallel Fast Legendre Transforms
1997 (English)Conference paper (Refereed)
We present a parallel Fast Legendre Transform (FLT) based on the Driscol--Healy algorithm with computation complexity O(N log 2 N ). The parallel FLT is load-- balanced in a hierarchical fashion. We use a load--balanced FFT to deduce a load-- balanced parallel fast cosine transform, which in turn serves as a building block for the Legendre transform engine, from which the parallel FLT is constructed. We demonstrate how the arithmetic, memory and communication complexities of the parallel FLT are hierarchically derived via the complexity of its modular blocks. 1 Introduction Legendre transforms are ubiquitous in many disciplines of applied sciences, particularly spectral methods for the solution of partial differential equations . For applications of harmonic analysis on the 2--sphere S 2 , an efficient Legendre transform is as crucial to numeric computation as the fast Fourier transform (FFT) is to classical time--series analysis on R. This stems from the fact that harmonic ana...
Place, publisher, year, edition, pages
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-64550OAI: oai:DiVA.org:kth-64550DiVA: diva2:483119
Proc. 8th SIAM Conf. on Parallel Processing for Scientific Computation
NR 201408052012-01-242012-01-24Bibliographically approved