Efficient Evaluation of Noncommutative Polynomials Using Tensor and Noncommutative Waring Decompositions. (7th December 2020)

• Record Type: Journal Article
• Authors: Evert, Eric; Helton, J. William; Huang, Shiyuan; Nie, Jiawang
• Is Part Of: Numerical functional analysis and optimization. Volume 42:Number 1(2021)
• Page Start: 39
• Page End: 68
• Publication Date: 2020-12-07
• Subjects: Noncommutative polynomials -- matrix variables -- sums of powers -- symmetric tensors -- Waring problem; Primary 11P05 -- 46L52 -- Secondary 15A69 -- 47A56; Functional analysis -- Periodicals; Numerical analysis -- Periodicals; Mathematical optimization -- Periodicals; Numerical Analysis, Computer-Assisted; 515.705
• DOI: 10.1080/01630563.2020.1859530
• Languages: English
• ISSNs: 0163-0563

Abstract

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.