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.