Study On Several Parallel Algorithms Of Symbolic Computation

Symbolic computation is generated from Mathematics and Computer Science field and has been an independent and developing research field.Unlike numeric computation,symbolic computation does the exact and precise mathematical calculations on computer so that it has been used in many different fields widely.However,doing the exact computation consumes much memory and CPU cost,symbolic computation has poor efficiency and perfermance for some large and complicated problems,it results in slow calculation and immediate expressions swell.So it is natural to find a quick way to accelerate the calculation performance.With the improvement of computer technology and progress in scientific research,parallel computers show more and more excellence and superiority.Through the cooperation of multiple processors in the parallel computer,parallel computation can accelerate the calculation and balance the memory load during the whole process.Hence,how to utilize and integrate parallel computation has become a hotspot of research in symbolic computation.In this thesis,we introduce parallel computation and symbolic computation,and mainly present several complex problems and their parallel solutions in symbolic computation.The main content of this thesis is follows:(1)Computing determinants of polynomial matrices is a basic and common mathematical operation.But for some large or complex polynomial matrices,it is difficult to get the determinant by expanding directly.We introduce the interpolation method,which converts the polynomial multiplication expansion into polynomial interpolation.By using the interpolation method,we solve the determinant of polynomial matrix into two steps.One is numerical calculation on interpolation point,and the other is solving linear equations.During the whole process,we use parallel computation to speed up the calculation.In the step of interpolation,we adopt coarse granularity to calculate the independent interpolation point on different computers with fewer communications between nodes.In the second step,we extend the Bj(?)rck-Pereyra algorithm of two variables to solve the equations of n variables.We distribute the serious loop of Bj(?)rck-Pereyra computation to several nodes so that we make the complexity of Bj(?)rck-Pereyra computation lower to O(rⁿ⁺¹/nc).We implement the parallel solution in MAPLE,and validate it by some examples from different areas.The result shows that parallel computation can not only quicken the calculation but also avoid the memory problem of immediate expression swell partly.(2)Automated inequality proving has been considered challenging in the area of automated reasoning for many years.We firstly extend the Successive Difference Substitution (SDS)into parallel mode with integrating parallel computation.By using multiple-level Master-Slave mode,we distribute the branches generated by difference substitution to different slave nodes.Each slave node calculates its own branches independently,while the master node collects the results together and finishes the proof.The efficicncy of parallel successive difference substitution is shown by several big inequalities.We also test the speedup of parallel computation for the VASC conjecture with seven variables.(3)The topological structure of difference substitution is studied in detail.We present the inequalites proved by difference substitution is a finitely generated cone and give the DevSubExp algorithm to calculate the extremal rays of difference substitution cone.Then we show the expansion of this cone by using difference substitution successively.Furthermore, we compare difference substitution with another algorithm Schur Partition,which can partition a ternary positive semi-definite homogeneous symmetric polynomial into a linear combination of five positive semi-definite bases.We show that for any ternary polynomials whose positive semi-definiteness can be proven by Schur Partition,it also can be proven by Difference Substitution.(4)Heilbronn problem for seven points.Heilbronn problem is a classic one in the discrete combinatorial geometry,while the Heilbronn problem for seven points has no whole result.In this thesis,we give a proper method with randomly Monte Carlo search method and interval analysis.Through randomly Monte Carlo search method,we put seven points in the unit square randomly and search the numeric optimal solution by the non-linear programming functions of MATLAB.Although the random search has uncertainty,we try to search million times and get the best results.This method is simple but can be extended for other similar geometry problems easily.Then we use symbolic computation and interval analysis to prove the optimal value and point-distribution graph.According to the problem of five and six points,we transfer the Heilbronn problem for seven points into 456427 non-linear optimization problems.We solve these problems by parallel computation on ten nodes.We give the result of Heilbronn problem for seven points in interval form.(5)Computer Algebra System(CAS)is a fundamental backbone for symbolic computation and automated reasoning.There are many excellent CASs,which can provide good interface and high performance computation for researchers.In this thesis,we firstly introduce the cluster task management software SGE and parallel message passing interface MPI. We also show several different ways to express mathematic symbols in computers.Then we discuss how to build a distributed and hybrid computing environment(HPPCAS)to realize the cooperation of different CASs and achieve higher performance through using external calling communication interface and integrating the parallel library and cluster management software.In HPPCAS,each job is submitted to a queue,asked computational resources by slot attribute and scheduled based on its ticket value,which denote the priority of job.Finally, we verify the efficiency of HPPCAS by the calculation of parallel successive difference substitution.From the above work,we can arrive the result that symbolic computation can benefit from parallel computation in the calculation process.Through parallel computation,it can balance the peak memory consumption to many nodes,alleviate the trouble of memory scarcity.It also distributes the calculative tasks to many nodes,and do calculation concurrently to improve the process quickly and easily.We think parallel computation will make symbolic computation more powerful and mightful.