Konstruktive Zerlegung von Matrixmultiplikationstensoren

Matrizen sind rechteckige Tabellen, in denen Zahlen stehen. Solche Zahlentabellen werden verwendet, um fundamentale Transformationen wie zum Beispiel Drehungen oder Stauchungen des Raumes zu beschreiben. Sie spielen deshalb eine wichtige Rolle in allen Bereichen der reinen und angewandten Mathematik. Mit Matrizen kann man rechnen. Zwei Matrizen miteinander zu multiplizieren bedeutet, dass man die entsprechenden Transformationen durch Hintereinanderausfuehrung miteinander kombiniert. Wenn zum Beispiel die erste Matrix einer Drehung und die zweite einer Stauchung entspricht, dann entspricht das Produkt dieser beiden Matrizen einer Transformation, bei der sowohl gedreht als auch gestaucht wird. Um das Produkt zweier Matrizen zu berechnen, muss man die Zahlen, aus denen sie bestehen, in einer bestimmten Weise miteinander verrechnen. Dabei ist eine Reihe von Additionen und Multiplikationen von Zahlen durchzufuehren. Der genaue Rechenaufwand haengt davon ab, wie gross die Matrizen sind, die man zu multiplizieren hat, also wie viele Zeilen und Spalten die Tabellen haben. Es ist klar, dass der Aufwand umso hoeher ist, je groesser die Matrizen sind. Aber wie der Rechenaufwand praezise von der Groesse der Matrizen ab, das weiss man nicht genau. Zwar kann man den Rechenaufwand fuer das klassische Multiplikationsverfahren leicht bestimmen, doch ist dieses Verfahren nicht die einzige Moeglichkeit, um das Produkt zweier Matrizen auszurechnen. Es gibt andere Verfahren, die zwar auf den ersten Blick etwas umstaendlicher aussehen, bei denen der Rechenaufwand aber tatsaechlich niedriger ist. Solche Verfahren sind nicht einfach zu finden. Deshalb weiss man auch nicht, ob die, die man kennt, schon die bestmoeglichen sind, oder ob es noch bessere gibt. Ziel des Projekts ist die Entwicklung von Methoden, mit denen effizientere Verfahren zur Multiplikation von Matrizen automatisch konstruiert werden koennen. Dabei werden Techniken aus verschiedenen Bereichen zum Einsatz kommen, etwa Suchmethoden fuer grosse Netwerke, Loesungsmethoden fuer boolsche Formeln, und verschiedene Algorithmen aus der Computeralgebra. Mit den neuen Methoden werden wir systematisch nach neuen und besseren Multiplikationsverfahren fuer Matrizen und aehnliche mathematische Objekte suchen. Wir hoffen dadurch besser zu verstehen, was die tatsaechliche rechnerische Schwierigkeit der Matrizenmultiplikation ist.