Speaker
Description
We study the set $\Pi^*_{{2^m}}$, which is the set of polynomials that can be evaluated as a matrix polynomial (in the sense of [Higham, 2008]) using exactly $m$ matrix-matrix multiplications, with no restrictions on the number of scalar multiplications or matrix additions. Based on a tabular parameterization for this set we develop algebraic transformations that preserve the computed polynomial while simplifying the parameterization. These transformations lead to a new upper bound $\dim(\Pi^*_{2m}) \leq m^2$, which numerical evidence suggests is sharp. Our results provide, to our knowledge, the first minimal parameterization of this type of polynomial evaluation schemes. Additionally, we use computational tools to investigate the inclusion problem: for a given $m$, determine the largest degree $d$ such that all degree-$d$ polynomials are in $\Pi^*_{2^m}$. We report new inclusion bounds and provide reproducible numerical experiments demonstrating, for example, using only 6 multiplications we can compute the Taylor expansion of the exponential to degree 30, improving on known methods. Our approach is constructive in the sense that we do provide a concrete iterative method with a given initialilization to compute the matrix polynomial for a given polynomial.
Joint work with Gustaf Lorentzon, KTH Royal Institute of Technology
