Squarefree decomposition of univariate polynomials depending on a parameter. Application to the integration of parametric rational functions (Q5945288)

The problem of parametric squarefree decomposition arises in cylindrical algebraic decomposition, when dealing with multiplicities in polynomial system solving, and in symbolic integration of rational functions. NEWLINENEWLINENEWLINELet \(P\in \mathbb{K}[x] [y]\), where \(\mathbb{K}\) is a field of characteristic zero. The form of the squarefree decomposition of \(P\) depends on the value of \(x\), and computing it for indeterminate \(x\) using the usual univariate polynomial method is very expensive. Barnett's method [\textit{S. Barnett}, Proc. Camb. Philos. Soc. 70, 263--268 (1971; Zbl 0224.15018); \textit{L. González-Vega}, Linear Algebra Appl. 247, 185--202 (1996; Zbl 0866.12002)] provides a compact representation of the gcd of a finite family of univariate polynomials and allows the degrees of the factors in the squarefree decomposition to be computed using just Bezoutians, determinants and gcds, always in \(\mathbb{K}[x] [y]\). The actual squarefree factors can then be computed directly using linear algebra and division of polynomials with coefficients in \(\mathbb{K}(x)\). NEWLINENEWLINENEWLINELet \(\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 Bezoutian matrix \(\text{Bez}(P,Q)\) has elements \(b_{i,j}\), \(0\leq i,j\leq n-1\), defined by NEWLINE\[NEWLINE\frac {P(y)Q(x)- P(x)Q(y)} {y-x}= \sum_{i,j=0}^{n-1} b_{i,j} y^ix^jNEWLINE\]NEWLINE and the Bezoutian \(\text{bez}(P,Q)\) is its determinant. NEWLINENEWLINENEWLINEIf \(P,Q_j\in \mathbb{D}[y]\) with \(n= \deg(P)\) and \(\deg(Q_j)< n\) for all \(j=1,\dots, t\) then NEWLINE\[NEWLINE\deg (\gcd (P,Q_1,\dots, Q_t))= n-\text{rank} (B_P(Q_1,\dots, Q_t)),NEWLINE\]NEWLINE where NEWLINE\[NEWLINEB_P(Q_1,\dots, Q_t)= \begin{pmatrix} \text{Bez}(P,Q_1)\\ \vdots\\ \text{Bez}(P,Q_t) \end{pmatrix}.NEWLINE\]NEWLINE If \(c_1,\dots, c_n\) are the columns of the matrix \(B_P(Q_1,\dots, Q_t)\) and its rank is \(n-k\) then the last \(n-k\) columns \(c_{k+1},\dots, c_n\) are linearly independent and each \(c_i\), \(1\leq i\leq k\), can be written as a linear combination in the form NEWLINE\[NEWLINEc_{k-i}= \sum_{j=k+1}^n h_{k-i}^j c_j, \qquad i=0,\dots, k-1,NEWLINE\]NEWLINE where \(y^k+ h_k^{k+1} y^{k-1}+ h_{k-1}^{k+1} y^{k-2}+\cdots+ h_1^{k+1}\) is a gcd of \(P,Q_1,\dots, Q_t\). These results are proved in [\textit{G. Diaz-Toca} and \textit{L. González-Vega}, Barnett's theorem about the greatest common divisor of several univariate polynomials through Bezoutians (Preprint) (2000)]. Moreover, NEWLINE\[NEWLINE\text{rank} (B_P(Q_1,\dots, Q_t))= n-k\iff \text{Gram} (c_{k+1},\dots, c_n)\neq 0NEWLINE\]NEWLINE where Gram denotes the Gram determinant. NEWLINENEWLINENEWLINEThe squarefree decomposition of \(P\in \mathbb{D}[y]\) is \(P= \prod_{j=1}^t P_j^j\), where \(P_j\in \mathbb{D}[y]\) is squarefree and \(\gcd (P_j, \prod_{i\neq j}P_i)=1\) in \(\mathbb{F}[x]\). Let \(P^{(i)}\) be the \(i\)th derivative of \(P\). Then NEWLINE\[NEWLINEt=\min\{j\mid \text{rank}(B_P (P^{(1)},\dots, P^{(j)}))= n\}.NEWLINE\]NEWLINE Let \(R_i:= \gcd (P,P^{(1)},\dots, P^{(i)})\). Then the list of numbers NEWLINE\[NEWLINE{\mathbf {Shape}}(P):= [\deg(R_0)= \deg(P), \deg(R_1),\dots, \deg(R_t)]NEWLINE\]NEWLINE determines the structure of the squarefree decomposition of \(P\), since NEWLINE\[NEWLINE\deg(P_i)= \deg(R_{i-1})- 2\deg(R_i)+ \deg(R_{i+1}), \quad i\geq 1.NEWLINE\]NEWLINE The different squarefree decompositions of \(P\), depending on the values of \(x\), are obtained once the different shapes of \(P\) are determined. First, the matrices \(\text{Bez} (P,P^{(j)})\) are computed for \(j=1,\dots, n-1\), together with \(\text{bez}(P,P^{(1)})\). If \(x\in \overline{\mathbb{K}}\), the algebraic closure of \(\mathbb{K}\), then NEWLINE\[NEWLINE\text{bez} (P,P^{(1)})\neq 0\iff {\mathbf {Shape}}(P)= [n,0]\iff P\text{ squarefree}.NEWLINE\]NEWLINE Otherwise, when \(\text{bez} (P,P^{(1)})=0\), let \(D_0(x)\) be the squarefree part of \(\text{bez} (P,P^{(1)})\). Then the rank behaviour of \(B_P(P^{(1)})\) on the roots of \(D_0(x)\) leads to the factorization NEWLINE\[NEWLINED_0(x)= D_{m_1^1} D_{m_2^1}\cdots D_{m_{s_{[1]}}}^1,NEWLINE\]NEWLINE where \(m_i^1\) denotes \(\text{rank} (B_P(P^{(1)}))\), when \(D_{m_i^1}(x)= 0\), which implies NEWLINE\[NEWLINE{\mathbf {Shape}}(P)= [n,n-m_i^1,\dots].NEWLINE\]NEWLINE The rank behaviour of \(B_P(P^{(1)}, P^{(2)})\) on the roots of \(D_{m_i^1}(x)\) leads to the factorization NEWLINE\[NEWLINED_{m_i^1}(x)= \prod_{j=1}^{s_{[i,2]}} D_{m_i^1, m_{i,j}^2},NEWLINE\]NEWLINE where \(m_{i,j}^2\) denotes \(\text{rank} (B_P(P^{(1)}, P^{(2)}))\), when \(D_{m_i^1,m_{i,j}^2} (x)=0\), which implies \({\mathbf {Shape}} (P)= [n,n-m_i^1, n-m_{i,j}^2,\dots]\). This process is continued along every branch of the tree until \(\text{rank} (B_P(P^{(1)},\dots, P^{(t)}))=n\), which happens after at most \(n\) steps. NEWLINENEWLINENEWLINEEfficient methods are given for the parametric rank determination and the computation of the polynomials \(D_{m+j}(x)\). The complexity of the algorithm is analyzed and an example given, which is then applied to the integration of a rational function.