For computing the greatest common divisor (GCD) of a given set of multivariate polynomials, in general we use one of modular algorithms to avoid any growth in the coefficient polynomials in the intermediate expressions. However, for computing approximate GCD of polynomials with a priori errors of their coefficients, it is difficult to use such modular algorithms since any resulting approximate GCD computed in one variable may have perturbations depending on the evaluation point and may not be an image of the same desired approximate GCD. This fact means we have to compute it as given multivariate polynomials, and operate with large matrices whose size is exponential in the number of variables. In this paper, we present a new modular algorithm called “SLRA interpolation” that can be used for computing approximate GCD of several multivariate polynomials. Our algorithms use the multidimensional FFT and SLRA (structured low-rank approximation) of non-square block diagonal matrices. This interpolation technique may reduce the time-complexity for one iteration in the computation of approximate GCD especially for the sparse case.

For the given pair of univariate polynomials generated by empirical data hence with a priori error on their coefficients, computing their greatest common divisor can be done by several known approximate GCD algorithms that are usually for polynomials represented by the power polynomial basis (power form). Recently, there are studies on approximate GCD of polynomials represented by not the power polynomial basis, and especially the Bernstein polynomial basis (Bernstein form) is one of them. we are interested in computing approximate GCD of polynomials in the power form but their perturbation is measured by the Euclidean norm of perturbation in the Bernstein form, and we introduce its applications for computing a reduced rational function, the rational function approximation and Padé approximation to get a better approximation in L2-norm on [0, 1].

Computing the greatest common divisor (GCD) of polynomials can be done by computing the Grobner basis instead of the well-known Euclidean algorithm, studied by Gianni and Trager in 1985, and Sasaki and Suzuki in 1992. In this paper, we extend their theories to polynomials with parameters. That is the theory of parametric greatest common divisors by means of comprehensive Grobner systems (CGS). Moreover, this can be considered as an indirect extension of known parametric GCD algorithms to those for several multivariate polynomials with parameters.

There are several preliminary definitions for a Gröbner basis with inexact input since computing such a basis is one of the challenging problems in symbolic-numeric computations for several decades. A structured Gröbner basis is such a basis defined from the data mining point of view: how to extract a meaningful result from the given inexact input when the amount of noise is not small or we do not have enough information about the input. However, the known algorithm needs a suitable (unknown) information on terms required for a variant of the Buchberger algorithm. In this paper, we introduce an improved version of the algorithm that does not need any extra information in advance.

Let F(x, u) be a given bivariate polynomial and ε be a small positive number. We consider the approximate factorization of F: find polynomials G, H and ΔF such that F = GH + ΔF and ‖ΔF‖ / ‖F‖= ε, where ‖P‖ denotes 2-norm of polynomial P. At first, we introduce a relation between the irreducibility of F and the singular value of a certain matrix. By this relation and an upper bound of variations of the power-series roots of a bivariate polynomial, we give an algorithm for an absolute irreducibility test of a polynomial whose coefficients are perturbed within a given tolerance. In addition, we give a lower bound for a tolerance of the approximate factorization of a given bivariate polynomial. The lower bound is the necessary magnitude of perturbations which make a given polynomial reducible.