scientific article; zbMATH DE number 1254264

From MaRDI portal
Publication:4227312





Let \(K\) be a field of characteristic 0 and \(L:K[x]\to K[x]\) an endomorphism of the \(K\)-linear space of univariate polynomials over \(K\). We consider the following commputational tasks concerning \(L\): T1. Homogeneous equation \(Ly=0\): Compute a basis of \(\text{Ker} L\) in \(K[x]\). T2. Inhomogeneous equation \(Lu=f\): Given \(f\in K[x]\), compute a basis of the affine space \(L^{-1}(f)\) in \(K[x]\). T3. Parametric inhomogeneous equation \(Ly= \sum^m_{i=1} \lambda_i f_i\): Given \(f_1,f_2, \dots,f_m \in K[x]\), compute a basis of \(\text{Ker} L'\) where \(L':(K[x] \oplus K^m)\to K[x]\) and \(L':(y, \lambda) \mapsto Ly-\sum^m_{i=1} \lambda_if_i\), for \(y\in K[x]\), \(\lambda\in K^m\). Many problems and algorithms in differential and difference algebra contain these tasks as subproblems which, however conceptually simple, often account for a fair share of the overall computing time. We consider three types of linear operators: differential, difference, and \(q\)-difference operators, all with polynomial coefficients. To find polynomial solutions of an equation of the form \(Ly=f\), it is natural to proceed in two steps: 1. Compute a degree bound \(N\) for polynomial solutions of the equation. 2. Given \(N\), compute polynomial solution(s) of degree(s) \(\leq N\). Our main contribution is to step 2 of the above procedure. Usually, it is carried out by means of undetermined coefficients: expand \(y(x)\) with respect to the usual power basis \((x^n)^\infty_{n=0}\) and substitute this expression into the equation, obtaining a triangular system of linear algebraic equations for \(c_i\)'s. Then there is a one-to-one correspondence between solutions of this system and those of the original equation. The problem with the method of undetermined coefficients is that the number of unknown coefficients, \(N+1\) (respectively \(N+m+1\) in the parametric case), is often much larger than the order of the equation, \(r\). We show that by using appropriate polynomial bases, the resulting linear system has a band-diagonal matrix which represents a recurrence for the unknown coefficients. After taking full advantage of this recurrence, the remaining linear system that needs to be solved is of size corresponding to the band-width of the matrix. For the entire collection see [Zbl 0903.00080].




Cited in
(40)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4227312)