A nearly optimal algorithm to decompose binary forms

DOI10.1016/J.JSC.2020.06.002MaRDI QIDQ1994885zbMATH OpenOpenAlexFDO

Authors Matías R. Bender, Jean-Charles Faugère, Ludovic Perret, Elias P. Tsigaridas

Publication date 18 February 2021

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

binary forms

Mathematics Subject Classification ID

Forms of degree higher than two (11E76) Secant varieties, tensor rank, varieties of sums of powers (14N07) Computational aspects in algebraic geometry (14Q99) Multilinear algebra, tensor calculus (15A69) Symbolic computation and algebraic computation (68W30)

Abstract: Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. It is equivalent to Waring's problem for homogeneous polynomials, that is to write a homogeneous polynomial in n variables of degree D as a sum of D-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We focus on decomposing binary forms, a problem that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. Under this formulation, the problem finds its roots in invariant theory where the decompositions are known as canonical forms. In this context many different algorithms were proposed. We introduce a superfast algorithm that improves the previous approaches with results from structured linear algebra. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have at least quadratic complexity bounds. Our algorithm computes a symbolic decomposition in $O(M(D)log(D))$ arithmetic operations, where $M(D)$ is the complexity of multiplying two polynomials of degree D. It is deterministic when the decomposition is unique. When the decomposition is not unique, our algorithm is randomized. We present a Monte Carlo version of it and we show how to modify it to a Las Vegas one, within the same complexity. From the symbolic decomposition, we approximate the terms of the decomposition with an error of $$epsilon$$ , in $O(Dlo{g}^2(D)(lo{g}^2(D)+log($epsilon$)))$ arithmetic operations. We use results from Kaltofen and Yagati (1989) to bound the size of the representation of the coefficients involved in the decomposition and we bound the algebraic degree of the problem by min(rank, D -- rank + 1). We show that this bound can be tight. When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, $O_{bit}(Dell+D^4+D^3$ au$)$ bit operations, where ${\displaystyle }$ au${\displaystyle }$ is the maximum bitsize of the coefficients and $2^{--ell}$ is the relative error of the terms in the decomposition.

Review text

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.

Recommendations

• Semialgebraic sets and real binary forms decompositions
• The Waring rank of binary binomial forms
• On the rank of a binary form
• A superfast randomized algorithm to decompose binary forms
• Binary decompositions and varieties of sums of binaries

Cites work

• A superfast randomized algorithm to decompose binary forms
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Algebraic Computations of Scaled Padé Fractions
• Algebraic methods for Toeplitz-like matrices and operators
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Binary forms with three different relative ranks
• Computing symmetric rank for symmetric tensors
• Decomposition of quantics in sums of powers of linear forms
• Eigenvectors of tensors and algorithms for Waring decomposition
• Homogeneous polynomial solutions to constant coefficient PDE's
• Homotopy techniques for tensor decomposition and perfect identifiability
• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 4163086 (Why is no real title available?)
• scientific article; zbMATH DE number 3957242 (Why is no real title available?)
• Interpolation of shifted-lacunary polynomials
• Modern computer algebra
• Monomials as sums of powers: the real binary case
• Nearly optimal computations with structured matrices
• Numerical methods for roots of polynomials. II
• On computing the canonical form for a binary form of odd degree
• On the Length of Binary Forms
• On the rank of a binary form
• Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
• Some new canonical forms for polynomials
• Sums of even powers of real linear forms
• Symmetric tensor decomposition
• Symmetric Tensors and Symmetric Tensor Rank
• Symmetric tensors: rank, Strassen's conjecture and \(e\)-computability
• Tensor decomposition and homotopy continuation
• The algebraic degree of geometric optimization problems
• The algebraic degree of semidefinite programming
• The Euclidean distance degree of an algebraic variety
• The invariant theory of binary forms
• Typical real ranks of binary forms
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Waring loci and the Strassen conjecture
• Waring's problem for binary forms

Cited in

(7)

• On computing the canonical form for a binary form of odd degree
• Semialgebraic sets and real binary forms decompositions
• A superfast randomized algorithm to decompose binary forms
• Efficient prediction algorithms for binary decomposition techniques
• A linear algebra method to decompose forms whose length is lower than the number of variables into weighted sum of squares
• Decomposition Algorithms for Tensors and Polynomials
• Derandomization and absolute reconstruction for sums of powers of linear forms

This page was built for publication: A nearly optimal algorithm to decompose binary forms

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