A polynomial time algorithm for computing all minimal decompositions of a polynomial

DOI10.1145/2644288.2644292zbMATH Open1314.12002arXiv1107.0687OpenAlexW2033673492MaRDI QIDQ5255833FDOQ5255833

Raoul Blankertz

Publication date: 19 June 2015

Published in: ACM Communications in Computer Algebra (Search for Journal in Brave)

Abstract: This diploma thesis is concerned with functional decomposition $f=gcirch$ of polynomials. First an algorithm is described which computes decompositions in polynomial time. This algorithm was originally proposed by Zippel (1991). A bound for the number of minimal collisions is derived. Finally a proof of a conjecture in von zur Gathen, Giesbrecht & Ziegler (2010) is given, which states a classification for a special class of decomposable polynomials.

Full work available at URL: https://arxiv.org/abs/1107.0687

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cited In (7)

• Counting invariant subspaces and decompositions of additive polynomials
• Title not available (Why is that?)
• Interpolation by decomposable univariate polynomials
• A polynomial-time algorithm for computing low CP-rank decompositions
• Counting decomposable polynomials with integer coefficients
• Tame decompositions and collisions
• The Prouhet-Tarry-Escott problem, indecomposability of polynomials and Diophantine equations

This page was built for publication: A polynomial time algorithm for computing all minimal decompositions of a polynomial

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