Approximate GCD and its application to ill-conditioned algebraic equations (Q1184132)

Classical root-finding algorithms like Newton's method do not give satisfactory results in case of ill-conditioned equations, i.e. the case of multiple and/or close roots. In order to overcome these difficulties the authors establish two algorithms of approximate greatest common divisor (GCD), one for univariate polynomials and the other for multivariate polynomials. After describing the approximate GCD the authors modify the Euclidean algorithm for calculating the GCD. In order to solve ill-conditioned equations the approximate GCD method is combined with an approximate square-free decomposition algorithm. The resulting method is extended to the multivariate case and an algorithm for solving certain ill- conditioned systems of algebraic equations is established. At the end this hybrid approach is applied to some practical examples.