Computational Problems From Multi-homogeneous Homotopy Continuation Method

Finding all isolated solutions of a polynomial system of equations has great valuein mathematics and strong background in applications. It is very common in many?elds of science and engineering, such as theoretical physics, large scale power sys-tems, mechanical engineering, automaton and chemical engineering. The size of prob-lem that can be solved by the best either numerical or symbolic method, however, isonly about 15. Huge gap exists up to many practical applications. Homotopy continuation method is an effective numerical approach. But mostof problems arising in practice are sparse and de?cient so that too much time maybe wasted by the classical continuation. Multi-homogeneous homotopy continuationmethod improves the classical method by using the optimal homogeneous structure ofthe system. However, determining the optimal homogeneous structure are essentiallytwo NP-hard problems. One is ?nding a variable partition with the minimal multi-homogeneous Be′zout number, and the other is the computation for a given variablepartition. Owing to the insurmountable complexity, approximation methods are naturalconsiderations. All deterministic approximation methods have to make exhaustive search in cer-tain extents. This heavily limits the size of computable problems. Randomized algo-rithm is introduced in this thesis. Two randomized algorithms with global convergenceare proposed. One is randomized ?ssion method. It can ?nd the exact or a good ap-proximation solution with a high probability. The other is multi-nested method which?nds the optimal k-partition. It brings favorite ?exibilities in practical computation. Aheuristic method for ?nding the optimal variable partition is also constructed based onthe idea of backward greedy. Comparisons of different deterministic search methodsare given. The kernel problem for determining Be′zout number of a given variable partitionis the computation or estimation of a permanent. Hybrid algorithms for general sparsematrix are given. Our methods are faster at least 50 times than the best classical algo-rithm for a class of molecular chemistry problems, which clearly shows the ef?ciencyof the methods. By introducing a concept "random path", the Rasmussen's approxi-mation algorithm is polished up, and a novel upper bound for the permanent of (0,1)- – II –英 文 摘 要matrices is also obtained. Generation of pseudo-random numbers is at the heart of randomized computation.A class of random number generators based on the Weyl Sequence is proposed. Thetheoretical analysis and statistical tests show the ef?ciency and the potential of the newmethods. Combinatorial optimization, combinatorial counting, randomized algorithms andstatistical computing, are intensively used in this thesis. It improves the ef?ciency of themulti-homogeneous homotopy continuation method. The holistic algorithm frameworkwith global convergence also establishes a sound foundation for further research works.