Abstract: Spherical harmonic expansions are a widely used tool of applied mathematics.Based on the research of Rokhlin-Tygert's fast algorithm for spherical harmonic expansions(RT algorithm),the procedure for computing expansion coefficients of all orders of associated Legendre functions is established,while the RT algorithm is extended and consummated.Furthermore,the strategy of MPI parallelization of RT algorithm is developed,and its parallel algorithm is designed and implemented.Numerical results show that,the computation of RT algorithm grows violently with the lift of the highest Fourier wave number of triangular truncations;MPI parallelization can efficiently bring up the computing speed and improve the performance of the algorithm.However,the efficiency of parallelization could be limited by the cache size of multi-cores processors and the bandwidth of memory access.