An Approximate Decomposition of a Multivariate Polynomial Based on Structured Low-Rank Approximation

A multivariate polynomial f is decomposable if f is a composition f=u∘ h , where u is a univariate polynomial of degree greater than one and h is a multivariate polynomial. We consider the problem of computing the nearest decomposable polynomial to a given multivariate polynomial with respect to the 2-norm. By using the relationship between the decomposability of a polynomial and the rank of a structured matrix corresponding to the polynomial, we reduce this problem to the structured low-rank approximation problem. Then we propose algorithms for computing an approximate decomposition of a multivariate polynomial based on the structured low-rank approximation problem.