Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
Author:
- Kazuo MurotaKMKazuo Murota
- 1 December 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (6) , 1132-1161
Abstract
Let $A(t,x) = (A_{ij} (t,x))$ be a square matrix with $A_{ij}$ being a polynomial in t and x. This paper proposes an algorithm for computing the Puiseux (= fractional power) series solutions $x = x(t)$ to the equation ${\operatorname{det}}A(t, x) = 0$. The algorithm is based on an observation which links the Newton diagram (polygon) for det ${\operatorname{det}}A(t, x)$ with the perfect matchings of a bipartite graph associated with A. The algorithm is efficient, making full use of available fast network-type algorithms.
Keywords
This publication has 13 references indexed in Scilit:
- Critical initial imperfection of structuresInternational Journal of Solids and Structures, 1990
- Programming in Networks and Graphs1988
- Plane Algebraic Curves1986
- Parametric Combinatorial Computing and a Problem of Program Module DistributionJournal of the ACM, 1983
- Computer algebra symbolic and algebraic computationACM SIGSAM Bulletin, 1982
- Theoretical Properties of the Network Simplex MethodMathematics of Operations Research, 1979
- A network simplex methodMathematical Programming, 1976
- Mathematical Techniques for Efficient Record Segmentation in Large Shared DatabasesJournal of the ACM, 1976
- Iteration methods for finding all zeros of a polynomial simultaneouslyMathematics of Computation, 1973
- Linear Programming and Extensions1963