Computing Verified Real Roots For Polynomial Systems And Its Implementation

Computing real roots of a polynomial system is a fundamental problem in computational real algebraic geometry. In scientific research and practical applications, many problems can be translated into computing exact real solutions for polynomial systems. Computing real roots of polynomial systems have played an important role in many areas, such as solving system of nonlinear constraints, program verification, engineering design, geometric modeling, robot motion planning, machine vision and so on. At present, exact polynomial system solving can be settled by symbolic computation method, interval computation method. However, the main bottleneck of symbolic computation is high complexity, which restricts the practical application in engineering. To deal with the limitation of symbolic computation, we present a hybrid symbolic-numeric computation method to attack this problem. In this thesis, we provide two methods for computing the verified real roots of the given polynomial system. The first one is based on the critical point method and the homotopy continuation method. The second one is based on the low-rank moment matrix completion method. In combination with these two methods, we present several verification algorithms to computing real roots of zero-dimensional, positive dimensional polynomial systems and semi-algebraic systems. Based on these theoretical results, we design and develop a Matlab toolbox software VerifyRealroot for computing real verified solutions of polynomial systems. To show the performance of this package, we call VerifyRealroot for computing verified solutions of a large set benchmark polynomial equations and semi-algebraic systems, and the performance is reported in tables. The main work in this thesis is carried out as follows:· Study how to apply critical point method, homotopy method and low-rank moment matrix completion method to compute real roots of zero-dimensional polynomial systems and positive-dimensional polynomial systems. · Provide four verification algorithms based on homotpy continuation method, critical point method and low-rank moment matrix completion method, including verifyrealroot0, verifyrealrootpc, verifyrealrootpm and verifyrealrootsas:VerifyrealrootO is a verification algorithm to deal with zero-dimensional polynomial systems; verifyrealrootpc based on homotopy method and critical point method, aims for finding at least one verified solution on each connected component of the algebraic variety defined by the given polynomial system; verifyrealrootpm and verifyrealrootsas, based on low-rank moment matrix completion method, compute at least one verified solution for positive-dimensional polynomial systems and semi-algebraic systems respectively.· Introduce a Matlab toolbox VerifyRealroot for computing verified real solutions of polynomial systems based on the methods mentioned above. First, we show the meanings of the input parameters, output parameters and main function of VerifyRealroot with its structure. Second, we elaborate the major functions and important auxiliary functions of the software, and emphasis the procedure of major verification functions. Finally, we show the configuration of VerifyRealroot, and illustrate its user guide.· Demonstrate on a large set of benchmark polynomial systems, that VerifyRealroot, by calling MMCRSolver method and homotopy continuation method, efficiently yield the verified real solutions.