Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases (Q2576217)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases |
scientific article |
Statements
Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases (English)
0 references
27 December 2005
0 references
Let \(\mathbb{D}\) be a domain, \(\mathbb{F}\) its quotient field, \(P(y),Q(y)\in\mathbb{D}[y]\) and \( n = \max\{\deg(P ), \deg(Q)\}\). The Bézout matrix associated to \(P(y)\) and \(Q(y)\) is the matrix: \[ \text{Bez}(P,Q) = \left( \begin{matrix} c_{0,0} & \cdots & c_{0,n-1} \\ \vdots & & \vdots \\ c_{n-1,0} & \cdots & c_{n-1,n-1} \end{matrix} \right), \] where the \(c_{i,j}\)'s are defined as \[ \frac{P(y)Q(x)-P(x)Q(y)}{y-x} =\sum_{i,j=0}^{n-1} c_{i,j} y^ix^j. \] The Bézoutian associated to \(P(y)\) and \(Q(y)\) is the determinant of the matrix \(\text{Bez}(P,Q)\). \textit{S. Barnett}'s method [Proc. Camb. Philos. Soc. 70, 263--268 (1971; Zbl 0224.15018); cf. also \textit{L. González-Vega}, Linear Algebra Appl. 247, 185--202 (1996; Zbl 0866.12002)] through Bézoutians is a linear algebra method allowing to compute the degree of the greatest common divisor (GCD) of several univariate polynomials in a very compact way, providing also an easy parametrization of this GCD when the considered polynomials involve parameters. The paper under review describes how to parameterize the GCD of several polynomials when their coefficients depend on a parameter. The efficacy of the method is also shown. If the parameter belongs to the field of real numbers, the GCD is obtained. If the parameter is not real, then \textit{K. Mulmuley}'s algorithm [Combinatorica 7, 101--104 (1987; Zbl 0635.65040)] is combined with Barnett's method. The second aim of the paper is to consider the well-studied problem of computing the approximate GCD with limited accuracy for several univariate polynomials using Barnett's method through Bézoutians and the singular value decomposition of matrices.
0 references
Barnett's method
0 references
Bézout matrix
0 references
approximate GCD problem for several polynomials
0 references
determinant
0 references
singular value decomposition
0 references
0 references
0 references