Speaker
Description
We consider the problem of computing matrix polynomials $p(X)$, where $X$ is a large dense matrix, using as few matrix-matrix multiplications as possible. Our approach to this problem involves studying the set $\Pi^*_{2^m}$, defined as the set of polynomials computable with at most $m$ matrix-matrix multiplications, but with an arbitrary number of matrix additions and scaling operations. This set is characterized by a tabular parameterization. We derive equivalence transformations of the tabular parameterization, which can be used to identify and eliminate redundant parameters without changing the image space. This leads to two new scientific contributions: a) a precise determination of the dimension: $\dim\Pi^*_{2^m} = m^2$; b) a first minimal parameterization of the set. Using this parameterization, we develop new methods for constructing specific elements of $\Pi^*_{2^m}$. In addition, we use tools from computational algebraic geometry to determine the largest degree such that all polynomials of that degree belong to $\Pi^*_{2^m}$. We then use this knowledge to compute truncated Taylor polynomials of maximal degree for a given number of matrix-matrix multiplications. This talk is based on the preprint [Jarlebring and Lorentzon, arXiv:2504.01500, 2025]