Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions

DOI10.1080/01630563.2020.1859530MaRDI QIDQ4985174zbMATH OpenOpenAlexFDO

Authors Eric Evert, J. William Helton, Shiyuan Huang, Jiawang Nie

Publication date 22 April 2021

Published in Numerical Functional Analysis and Optimization (Search for Journal in Brave)

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

zbMATH Keywords

symmetric tensorsWaring problemsums of powersnoncommutative polynomialsmatrix variables

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Noncommutative function spaces (46L52) Waring's problem and variants (11P05) Rings arising from noncommutative algebraic geometry (16S38)

Abstract: This paper analyses a Waring type decomposition of a noncommuting (NC) polynomial $p$ with respect to the goal of evaluating $p$ efficiently on tuples of matrices. Such a decomposition can reduce the number of matrix multiplications needed to evaluate a noncommutative polynomial and is valuable when a single polynomial must be evaluated on many matrix tuples. In pursuit of this goal we examine a noncommutative analog of the classical Waring problem and various related decompositions. For example, we consider a "Waring decomposition" in which each product of linear terms is actually a power of a single linear NC polynomial or more generally a power of a homogeneous NC polynomial. We describe how NC polynomials compare to commutative ones with regard to these decompositions, describe a method for computing the NC decompositions and compare the effect of various decompositions on the speed of evaluation of generic NC polynomials.

Recommendations

• Non-commutative representations of families of k^2 commutative polynomials in 2k^2 commuting variables.
• Deterministic polynomial identity testing in non-commutative models
• Non-commutative circuits and the sum-of-squares problem
• Eigenvectors of tensors and algorithms for Waring decomposition
• scientific article; zbMATH DE number 2051167

Cites work

• scientific article; zbMATH DE number 773851 (Why is no real title available?)
• A counterexample to Comon's conjecture
• Convex Matrix Inequalities Versus Linear Matrix Inequalities
• Effective criteria for specific identifiability of tensors and forms
• Eigenvectors of tensors and algorithms for Waring decomposition
• Foundations of Free Noncommutative Function Theory
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Induction for secant varieties of Segre varieties
• On generic and maximal \(k\)-ranks of binary forms
• On the Waring problem for polynomial rings
• Optimization of polynomials in non-commuting variables
• Remarks on the symmetric rank of symmetric tensors
• Solving Matrix Inequalities whose Unknowns are Matrices
• Symmetric Tensors and Symmetric Tensor Rank
• The strict Waring problem for polynomial rings
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Varieties of sums of power
• Waring's problem for polynomials in two variables

This page was built for publication: Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions

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