Polynomial decomposition algorithms
From MaRDI portal
Publication:5893804
A polynomial \(f\) over a commutative ring is said to be decomposable if it has a non-trivial functional decomposition \(f=g\circ h\). Previous algorithms to check decomposability were exponential-time in the worst case and only worked over fields of characteristic 0. The present author describes an \(O(n^2r)\)-algorithm, where \(n\) and \(r\) are degrees of \(f\) and \(g\). The algorithm works over arbitrary commutative rings.
Recommendations
Cites work
- Composite Polynomials with Coefficients in an Arbitrary Field of Characteristic Zero
- Fast Algorithms for Manipulating Formal Power Series
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast Parallel Matrix Inversion Algorithms
- scientific article; zbMATH DE number 3942888 (Why is no real title available?)
- scientific article; zbMATH DE number 4035723 (Why is no real title available?)
- scientific article; zbMATH DE number 3406187 (Why is no real title available?)
- On the invariance of chains of fields
- Polynomial decomposition algorithms
- Polynomial Substitutions
- Prime and composite polynomials
- Solvability by radicals is in polynomial time
Cited in
(45)- Computational problems in the theory of finite fields
- The inverse of an automorphism in polynomial time
- A test for additive decomposability of irreducibles over a finite field
- \(\sqrt{2}+\sqrt{3}\): Four different views
- On the decomposition of \(x^d + a_ex^e +\dots +a_1x +a_0\)
- Sparse shifts for univariate polynomials
- Counting invariant subspaces and decompositions of additive polynomials
- Normal form for Ritt's second theorem
- Compositions and collisions at degree \(p^2\)
- On the decomposition of rational functions
- Counting decomposable polynomials with integer coefficients
- A recombination algorithm for the decomposition of multivariate rational functions
- Two questions on polynomial decomposition
- Polynomial decompositions in polynomial time
- scientific article; zbMATH DE number 2125607 (Why is no real title available?)
- scientific article; zbMATH DE number 5957430 (Why is no real title available?)
- Algorithms for the Polar Decomposition
- A short proof for the open quadrant problem
- scientific article; zbMATH DE number 4199450 (Why is no real title available?)
- scientific article; zbMATH DE number 4208240 (Why is no real title available?)
- Algebraic Condition for Decomposition of Large-Scale Linear Dynamic Systems
- scientific article; zbMATH DE number 4154575 (Why is no real title available?)
- Decomposition of polynomials and approximate roots
- Universal decomposition algebra
- Algorithms for the Functional Decomposition of Laurent Polynomials
- scientific article; zbMATH DE number 4101330 (Why is no real title available?)
- Algebraic computation of resolvents without extraneous powers
- Identification of Hammerstein–Wiener models with hysteresis front nonlinearities
- Algorithmic Polynomials
- Algorithmic polynomials
- Algorithms for computing triangular decompositions of polynomial systems
- A polynomial time algorithm for computing all minimal decompositions of a polynomial
- Counting decomposable univariate polynomials
- Polynomial decomposition algorithms
- Tame decompositions and collisions
- Interpolation by decomposable univariate polynomials
- An approximate decomposition of a multivariate polynomial and its application
- An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography
- Redactable blockchains and polynomial equations
- Functional decomposition of polynomials: the tame case
- Functional decomposition of polynomials: the wild case
- An algorithm for the decomposition of differential polynomials in the general case
- Decomposition of ordinary difference polynomials
- Decomposition of ordinary differential polynomials
- Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem
This page was built for publication: Polynomial decomposition algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5893804)
