  By viewing non-commutative polynomials, that is, elements in free associative
algebras, in terms of linear representations, we generalize Horner's rule to
the non-commutative (multivariate) setting. We introduce the concept of Horner
systems (which has parallels to that of companion matrices), discuss their
construction and show how they enable the efficient evaluation of
non-commutative polynomials by matrices.
