Efficient Evaluation of Noncommutative Polynomials Using Tensor and Noncommutative Waring Decompositions

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 n...