  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.
