We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomised algorithm for the following problem: If a homogeneous polynomial f ? K[x(1), ..., x(n)] (where K ? C) of d...
详细信息
We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomised algorithm for the following problem: If a homogeneous polynomial f ? K[x(1), ..., x(n)] (where K ? C) of degree d is given as a blackbox, decide whether it can be written as a linear combination of d-th powers of linearly independent complex linear forms. The main novel features of the algorithm are:? For d = 3, we improve by a factor of n on the running time from the algorithm in Koiran & Skomra (2021). The price to be paid for this improvement is that the algorithm now has two-sided error.? For d > 3, we provide the first randomised blackbox algorithm for this problem that runs in time poly(n, d) (in an algebraic model where only arithmetic operations and equality tests are allowed). A previous algorithm for this problem due to Kayal (2011) as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorisation subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unit-cost RAM or the Turing machine this approach does not yield polynomial time algorithms.? For d > 3, when f has rational coefficients (i.e. K = Q), the running time of the blackbox algorithm is polynomial in n, d and the maximal bit size of any coefficient of f. This yields the first algorithm for this problem over C with polynomial running time in the bit model of *** results are true even when we replace C by R. We view the problem as a tensor decomposition problem and use linear algebraic methods such as checking the simultaneous diagonalisability of the slices of a tensor. The number of such slices is exponential in d. But surprisingly, we show that after a random change of variables, computing just 3 special slices is enough. We also show that our approach can be extended to the computation of the actual decomposition. In forthcoming work we plan to extend these results to o
暂无评论