The Research Of Hybrid Parallel Algorithm Based On Tridiagonal Systems Of Equations

Many large application fields such as science and engineering calculation are involved solving the typical structure of large-scale linear algebraic equations.And solving large linear equations can be used as the basis to solve the major problem of the corresponding fields.Nowadays the computational problems arising from the large project and scientific research become increasingly complicated,so the requirement of computing environment is becoming higher.If we want to solve the large or very large complex computing problems effectively and by using less time,it need to rely on the implementation of the parallel computing technology.In recent years,the further development of large-scale parallel computers and super computers provides a reliable guarantee for effectively solving the large or very large complex computing problems.Based on the OpenMP parallel programming environment,this paper studies the parallel solution of the tridiagonal linear equations.So far,for the parallel so lution of linear equations with the typical structure,the existing methods include the block partition algorithm,the cyclic reduction algorithm and the improved algorithms of the above algorithms,etc.The partition and cyclic reduction algorithms are ba sed on the divide-and-conquer method,and they also made significant research results in parallel environment rising in recent years.An optimized parallel algorithm is proposed to solve the problem occurred in the process of complicated backward substitution of cyclic reduction during solving tridiagonal linear systems.Adopting a hybrid parallel model,this algorithm combines the cyclic reduction method and the partition method.This hybrid algorithm has simple backward substitution on parallel computers comparing with the cyclic reduction method.In this paper,the operation count and execution time are obtained to evaluate performance and make comparison for these methods.On the basis of results of these measured parameters,the hybrid parallel algorithm using the hybrid approach with a multi-threading implementation achieves better efficiency than the other parallel methods,i.e.,the cyclic reduction and the partition methods.In particular,the approach involved in this paper has the least scalar ope ration count and the shortest execution time on a multi-core computer when the size of equations meets some dimension threshold.In the process of solving large tridiagonal systems,t he hybrid parallel algorithm improves the performance of the cyclic reduc tion and partition methods by 19.2% and 13.2% respectively.In addition,in order to further explore the performance of the hybrid parallel algorithm,this paper adds iterations of the elimination process of the hybrid algorithm,and analysis and implements the performance of multi-iterations hybrid parallel algorithms.By comparing the single-iteration and multi-iterations hybrid parallel algorithms,it is found that increasing iteration steps of the cyclic reduction method does not affect the performance of the hybrid parallel algorithm very much.