Constructive Decomposition of Matrix Multiplication Tensors

Matrices are rectangular tables containing numbers. Such tables of numbers are used to describe fundamental transformations of space like rotations or stretchings. They hence play an important role in all areas of pure and applied mathematics. It is possible to compute with matrices. To compute the product of two matrices means that the corresponding transformations are combined into a single transformation by applying one after the other. For example, if one matrix corresponds to a rotation and the other to a stretching, then the product of these two matrices amounts to a transformation which at the same time rotates and stretches. In order to compute the product of two matrices, certain computations have to be carried out on the the numbers they consist of. This process requires various additions and multiplications of numbers. The number of operations depends on the size of the matrices to be multiplied, i.e., on how many rows and columns the tables have. It is clear that the amount of work is larger when we have larger matrices. But it is not known precisely how the amount of work depends exactly on the size of the matrices. It is easy to determine the amount of work for the classical matrix multiplication method, but this method is not the only way to compute the product of two matrices. There are other methods, which at first glance seem to be more complicated, but which in fact require less computational work. Such methods are not easy to find. Therefore, it is also not known whether those we know are already the best possible methods or if there are even better ones. A goal of the project is the development of methods by which more efficient methods for multiplying matrices can be constructed automatically. To this end, we will employ techniques originating from various different areas, including search methods for large networks, methods for solving boolean formulas, and various algorithms from computer algebra. With these new methods we will systematically search for new and better multiplication methods for matrices and related mathematical objects. We hope that this will contribute to a better understanding of the real difficulty of matrix multiplication.