Some Fast Algorithms For Solving Polynomial Systems And Computing Minimal Polynomials Of Polynomial Matrices

Solving polynomial systems is a classical problem, while finding all the solutions of polynomials systems is hard and important problem in computer algebra and computa-tional mathematics. Homotopy continuation method is the primary numerical algorithm to solve polynomial systems. In the stability problem, we often need to compute the charac-teristic polynomial or the minimal polynomial of a matrix which sometimes is a polynomial matrix. Computing the characteristic polynomial or the minimal polynomial of a polyno-mial matrix is a basic problem in computer algebra, but it lacks of effective algorithms. In this dissertation, we do some researches on homotopy method for solving polynomial systems, finding the minimal m-Bezout number, and computing the minimal polynomials of polynomial matrices. The main contributions include:1. We proposed a hybrid divide-and-conquer method for solving deficient polynomial systems. In this homotopy, start system consists of two parts:one part is random product homotopy while the other part is coefficient-parameter homotopy, and by some criteria, start systems can be constructed automatically. The start systems can be decomposed into some subsystems which consist of several groups of subsystems with the same support. Running the same process with eliminations and reductions, we can decrease the dimensions, total degrees and BKK bounds of each group of subsystems, and then getting all the solutions by a polyhedral homotopy and some coefficient-parameter homotopy. At last, every isolated solution of the target system can be reached by some path originating at the solutions of start systems which derive from the solutions of those subsystems. The hybrid homotopy method is a homotopy with divide and conquer, and a symbolic-numerical algorithm. Numerical test shows it is efficient.2. The homotopy for solving polynomial systems, which is based on m-Bezout theorem, has to follow the m-Bezout number of curves. Different way of partitioning the unknowns produces different m-Bezout number. It is desired to find a partition whose m-Bezout number is the smallest one among all possible partitions. But finding the optimal partition is a NP-hard problem. We present two problem-specific genetic algorithms and two heuristic algorithms to find it. The tests show our algorithms is efficient.3. By using a random vector and randomly shifting, a Cay ley-Hamilton Theorem based method with some conditions for computing the characteristic polynomial of a polynomial matrix is converted into a algorithm without any conditions for computing the minimal polynomial of a polynomial matrix, and we show it is probability1algorithm. In the case that coefficients of entries of the given polynomial matrix are all integers and that the algorithm is performed in exact computation, by using the modular technique, a parallelized version is proposed. Comparisons with other algorithms in both theoretical complexity analysis and computational tests are given to show its effectiveness.