A Study Of Fast Algorithm For Spherical Harmonic Expansions Based On Butterfly Procedure

The spectral model possesses the characteristics of high efficiency and compatibility of long-time global integration.It is used in business application in most of weather forecast centers all over the world.Spherical harmonic transform,including Fourier transform and Legendre transform,is the key computational process of spectral model.The computational complexity of Fourier transform is O(NlogN).However,traditional Legendre transform has very high computational complexity,which is up to O(N2).With the rapid development of society and people's living standards,it puts forward higher requirements for the accuracy of meteorology forecasts.Low-resolution numerical weather prediction model can't meet the needs of modern production and living nowadays.Therefore,it's urgently to improve the model resolution,the accuracy and timeliness of numerical weather prediction.However,in high-resolution numerical weather prediction model,due to its high time complexity,spectral transform has become a performance bottleneck of high resolution spectral model.Therefore,we study fast spherical harmonic expansions algorithms in this paper.Spherical harmonic expansions have been widely used and is a well understood tool in applied mathematics;they are encountered,inter alia,in weather and climate modeling,in the representation of gravitational,topographic,and magnetic data in geophysics,in the numerical solution of certain partial differential equations,etc.In this paper,we studied fast spherical harmonic expansions algorithm proposed by Tygert in 2010.The main contributions are listed as follows:(1)We provide a comprehensive overview of spherical harmonic expansions.The application prospect of the fast spherical harmonic expansions algorithm based on Butterfly scheme is pointed out as well.Matrix interpolation decomposition technique,which is used in Butterfly scheme,is a kind of matrix approximate decomposition technique.By using multi-level matrix interpolation decomposition technique,Butterfly algorithm reduces the computational complexity of Legendre transform from O(N2)to O(NlogN).(2)We have studied and realized fast spherical harmonic expansions based on butterfly algorithm,and improved the algorithm proposed by Tygert in 2010 by applying Butterfly algorithm directly to Legendre transform process.In addition,we fixed some errors in Tygert's algorithm.(3)We have designed and realized the parallelism of fast algorithms for spherical harmonic expansions presented in this paper.Based on the computational complexity of our fast algorithm,we designed a load balancing policy,which contributing to good experimental results.The experimental results shows that our parallel algorithm has a high speedup and parallel efficiency.