Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions

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.

31 pages, includes table of contents

References in corpus (5)

• Eigenvectors of tensors and algorithms for Waring decomposition
• Effective criteria for specific identifiability of tensors and forms
• On the Waring problem for polynomial rings
• On generic and maximal k-ranks of binary forms
• Horner Systems: How to efficiently evaluate non-commutative polynomials (by matrices)