Applications of Polyhedral Homotopy Continuation Methods to Topology. Takayuki Gunji (Tokyo Inst. of Tech.) Contents Polyhedral Homotopy Continuation Methods Numerical examples Applications to Topology Introduction Find all isolated solutions of polynomial systems. Polynomial systems come from various fields in science and engineering •Inverse kinematics of robot manipulators. •Equilibrium states. •Geometric intersection problems. •Formula construction. Introduction Grobner Basis Using Mathematica It takes long time Linear Homotopy Polyhedral Homotopy PHCpack by J.Verschelde(1999) PHoM by Gunji at al.(2002) Parallel Implementation Isolated solutions. are isolated solutions y 4 3 2 1 x O 1 2 3 4 Isolated solutions. aren’t isolated solutions y 4 3 2 1 x O 1 2 3 4 The number of solutions. Cyclic_n problem. N Num. N Num 10 34,940 12 367,488 11 184,756 13 2,704,156 Homotopy continuation method. The original system Step 1 Constructing homotopy systems such that and that can be solved easily Step 2 Solving Homotopy continuation method. Step 3 Tracing homotopy paths. Solutions of the original system Solutions of Linear homotopy Can be solved easily! Polyhedral homotopy Same as Binomial system Can be solved by Euclidean algorithm. General position Example are solutions of this system. General position Example If , this system doesn’t have a continuous solution When are randomly chosen, this case doesn’t happen with probability 1 (the measure of this case happening is 0) General position Step 1 : P’(x)=0 solves by using polyhedral homotopy Step 2: Find solutions of P(x)=0 by using this system Polyhedral Homotopy D.N.Bernshtein “The number of roots of a system of equations” , Functional Analysis and Appl. 9 (1975) B.Huber and B.Sturmfels “A Polyhedral method for solving sparse polynomial systems” , Mathematics of Computation 64 (1995) T.Y.Li “Solving polynomial systems by polyhedral homotopies” , Taiwan Journal of Mathematics 3 (1999) Polynomial system Constructing homotopy systems Solving binomial systems Tracing homotopy paths Verifying solutions All isolated solutions Constructing homotopy systems The original system Randomly chosen multiply to each terms Constructing homotopy systems Constructing homotopy systems Divided by Constructing homotopy systems Find all satisfying the property that. Each equation, exactly 2 of power of t are 0. Ex Constructing homotopy systems Find all satisfying the property that. Each equation, exactly 2 of power of t are 0. Constructing homotopy systems All of solutions. Tracing homotopy path Using Predictor Corrector Method Predictor step : tangent of path (increase of t) Corrector step : Newton Method Corrector step Predictor step Tracing homotopy path Taylor series Predictor step Corrector step Polynomial system Constructing homotopy systems Solving binomial systems Tracing homotopy paths Verifying solutions All isolated solutions Parallel Computing Independent! Path 4 Path 1 Path 2 Path 3 Path 5 Parallel Computing Client and server model. Server 1 Master problem sub problem Server 2 sub problem sub problem Client Server 3 sub problem sub problem Server 4 PHoM (Polyhedral Homotopy Continuation Methods) Single CPU version OS : Linux (gcc) http://www.is.titech.ac.jp/~kojima/PHoM/ Numerical examples Isolated solutions Linear Homotopy : the number of tracing path is 4. Polyhedral Homotopy : the number of tracing path is 2. Numerical examples Cyclic_n problem. Numerical examples problem Num. Time cyc_10 34,940 5mins cyc_11 184,756 30mins cyc_12 367,488 4hours cyc_13 2,704,156 15hours The number of solutions Athlon 1200MHz 1GB(or2GB)x32CPU Some applications to Topology Representation space of a fundamental group in SL(2,C). Computation of Reidemeister torsion Joint works with Teruaki Kitano. Representation into SL(2,C) M: closed oriented 3-dimensional manifold 1 (M ) its fundamental group of M : SL(2,C) an irreducible representation of the set of conjugacy classes of SL(2,C)irreducible representations. is an algebraic variety over C Problem: Determine in Figure-eight knot case u, v | wu vw Fundamental group of an exterior of figureeight knot 2 generators and 1 relation w uv u v 1 1 l v uvu u vuv 1 1 1 1 meridian u and longitude l. Irreducible representation Consider an irreducible representation into SL(2,C) Write images as follows : SL(2,C) U (u),V (v), L (l ) Corresponding matrices We consider conjugacy classes , then we may put U and V as follows 1 2 1 2 1 x x 4 x x 4 0 V 2 U 2 1 2 1 2 0 x x 4 y x x 4 2 2 Representation space From the relation wu=vw in the group, we obtain the following polynomial. f(x, y) y - 5y x y 5 - x 0 2 2 2 Dehn surgery along a knot Put a relation in the fundamental group. L is a corresponding matrix of a longitude l. l v uvu u vuv 1 1 1 1 •The above relation gives one another polynomial g(x,y)=0 as a defining equation. Apply the Homotopy Continuation Methods This system of polynomial equations f=g=0 describe conjugacy classes of representations, that is, each solution is a corresponding one conjugacy class of representations. We solve some case by using the polyhedral homotopy continuation methods. Reidemeister torsion Reidemeister torsion is a topological invariant of 3-manifolds with a representation parameterized by x and y. 2(1 x) (M ) 2 2 4 2 2 3 4x y x y x y Example 1 : (p,q)=(1,1) f(x, y) y - 5y x y 5 - x 0 2 2 2 g ( x, y) 2x3 y 2 x3 y 2xy3 8xy2 4xy x 2 0 Example 1 : (p,q)=(1,1) Re(x) Im(x) Re(y) Im(y) R-torsion 0.55495 0 3.2469 0 0.615894 -0.80193 0 1.5549 0 1.28627 2.2469 0 0.19806 0 10.1011 Example 2 : (p,q)=(1,2) f(x, y) y - 5y x y 5 - x 0 2 2 2 g ( x, y) x y 2x y 8x y x y 7 4 5 5 5 4 3 6 8x y x y 16x y 2x y 4xy 3 5 5 2 3 16xy 8xy x 2 0 2 4 3 3 Example 2 : (p,q)=(1,2) Re(x) Im(x) Re(y) Im(y) R-torsion -2.13472 -0.02096 0.276827 0.587152 2.98851+0.563057i -2.13472 0.020964 0.276827 -0.58715 2.98851-0.563057i 0.953386 0 1.74036 0 0.0250711 0.31267 0 3.50266 0 2.86831 -0.84722 0 2.69078 0 1.20196 0 0.102616 0 42.1263 0 0 3.80094 2.23869 -0.38809 1.40993
© Copyright 2024 ExpyDoc
