A nearly optimal algorithm to decompose binary forms (Q1994885)

The authors propose and discuss a new algorithm for the Waring decomposition of a binary form \(f(x,y)\) of degree \(d\), over a field \(K\), as a (minimal) sum of powers of linear forms \(f=\sum_{j=1}^r \lambda_j(\alpha_jx+\beta_jy)^d\), where \(\lambda_j\)'s, \(\alpha_j\)'s, and \(\beta_j\)'s sit in the algebraic closure of \(K\). The algorithm is based on algebraic properties of Hankel matrices. The computational complexity is bounded by \(O(m(d)\log(d))\), where \(m(d)\) is complexity of multiplying two polynomials of degree \(d\). The algorithm is deterministic when the decomposition is unique, a property that can be tested by the algorithm without increasing the asymptotical complexity. If the decomposition is not unique, the algorithm makes choices, and the authors present bounds for the number of bad choices that it could make. For forms \(f(x,y)\) with integer coefficients, the authors extimate the number of bit operations required by the new algorithm.