Decomposition of ordinary difference polynomials
type: Item
instance of: scholarly article
title: Decomposition of ordinary difference polynomials
zbMATH Open document ID: 1180.12006
author: Mingbo Zhang
author: Xiao-Shan Gao
published in: Journal of Symbolic Computation
publication date: 2009-09-14T00:00:00Z
review text: This article presents an algorithm for decomposition of nonlinear ordinary difference polynomials. It is a generalization of \textit{D. Kozen} and \textit{S. Landau} [J. Symb. Comput. 7, No. 5, 445--456 (1989; Zbl 0691.68030)] to ordinary difference polynomials. The algorithm works in several steps. First, the problem is reduced to decomposition of a homogeneous difference polynomial. Next, this is reduced to decomposing the linear left decomposition factors of another homogeneous difference polynomial. Finally, these are computed using decomposition of linear difference polynomials. This whole procedure computes the right decomposition factors; it is easy to find the left factors corresponding to them. The final algorithm is exponential due to combinatorial selections in the algorithm. The authors point out that the complexity of decomposing linear difference polynomials is also exponential, and that their algorithm for the non-linear case is quite effective practically. Also, this algorithm does not introduce parameters and works in the coefficient field of the input. There exists an algorithm for differential (as opposed to difference) polynomials by the same authors [\textit{X.-S. Gao} and \textit{M. Zhang}, Appl. Algebra Eng. Commun. Comput. 19, No. 1, 1--25 (2008; Zbl 1180.12004)] which, according to them, is quite different from the one presented here, due to the different properties of differential and difference operators.
reviewed by: David Sevilla
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 12H10
zbMATH DE Number: 5603612
zbMATH Keywords: functional decomposition
zbMATH Keywords: difference polynomial
zbMATH Keywords: difference operator
zbMATH Keywords: difference degree
describes a project that uses: Maple
MaRDI profile type: Publication
full work available at URL: j.jsc.2009.04.001
OpenAlex ID: W2159538607
cites work: On Ore rings, linear operators and factorization
cites work: An introduction to pseudo-linear algebra
cites work: Q3714165
cites work: Q5334359
cites work: Q4234261
cites work: Decomposition of differential polynomials with constant coefficients
cites work: Decomposition of ordinary differential polynomials
cites work: Q4660658
cites work: Polynomial decomposition algorithms
cites work: Q4232487
cites work: Associative differential operations
cites work: Q4488096
cites work: Liouvillian Solutions of n-th Order Homogeneous Linear Differential Equations
cites work: An algorithm for solving parametric linear systems
cites work: An algorithm for nonparametric decomposition of differential polynomials
cites work: Q4790565
cites work: Functional decomposition of polynomials: the tame case
DOI: 10.1016/J.JSC.2009.04.001
Recommended article: An algorithm for finding all polynomial solutions of nonlinear difference equations
Recommended article: On Detecting Solutions of Polynomial Nonlinear Difference Equations
Recommended article: Decomposition of ordinary differential polynomials
Recommended article: Rational solutions of linear difference equations: universal denominators and denominator bounds
Recommended article: An algorithm for the decomposition of differential polynomials in the general case
Recommended article: A characteristic set method for ordinary difference polynomial systems
Recommended article: Q4227312
Recommended article: On Polynomial Solutions of Linear Partial Differential and (q-)Difference Equations
Recommended article: Q4227311
Recommended article: Decomposition of differential polynomials with constant coefficients
description: scientific article; zbMATH DE number 5603612