A High-Performance Algorithm Of Solving Nonlinear Algebraic Equations For Real Roots Based On Branch And Bound Method

Solving nonlinear algebraic equations is a classic mathematics problem,and common in scientific researches and engineering applications.There are many numeric,symbolic and numeric-symbolic methods of solving(real)solutions.Unluckily,these methods are constrained by some factors,e.g.high complexity,slow serial calculation,and the notorious intermediate expression expansion.In recent years,devices based on GPGPU and other many-core device has realized lots of large-scale,high-concurrency algorithms.In this paper,based on the branch and bound method and interval arithmetic,we present an efficient algorithm to get potential real solutions for nonlinear algebraic equation with integer or floating-point number coefficients in GPGPU environment.The details are as follows.First,on the issues of limited ranges variables,we use branch and bound method based on GPGPU to searching the solution space globally and using interval evaluation remove infeasible configurations(not contain zero)and output the remains.Second,we implement the Hansen-Sengupta method on GPGPU,remove infeasible configurations.The method can generate a tighter box for roots of input function.Moreover,demonstrate the backtracking process of feasible configurations,and isolate the real roots of algebraic equations.The experiments show that our method can solve many nonlinear algebraic equations,and the results are accurate and efficient compared to traditional serial methods,and avoids the notorious problem of intermediate expression expansion.we use interval replace number and use rounding down the lower bound and rounding up the upper bound,to ensure computation correctness.Hansen-Sengupta method is used to determine the existence of the roots and reduce the solution space.The backtracking algorithm can isolate finite real roots.Therefore,our algorithm is right and complete.Additionally,the nonlinear algebraic equations studied in this paper have finite real solution,and the initial ranges of variables are limited.So the algorithm will stop when the interval width of feasible configurations meets the desired goal.