Decomposition of ordinary difference polynomials (Q840708): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jsc.2009.04.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2159538607 / rank | |||
Normal rank |
Revision as of 22:21, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of ordinary difference polynomials |
scientific article |
Statements
Decomposition of ordinary difference polynomials (English)
0 references
14 September 2009
0 references
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.
0 references
functional decomposition
0 references
difference polynomial
0 references
difference operator
0 references
difference degree
0 references