Hendrik Orem

Harvey Mudd College Mathematics 2009

mugshot
Final Thesis: Matrix Multiplication via Group Actions
Thesis Proposal: Algebraic Methods for Fast Matrix Multiplication
Thesis Advisor: Prof. Michael Orrison
Second Reader: Prof. Nicholas Pippenger

Group Theory and Matrix Multiplication Algorithms

A 2003 paper by Henry Cohn and Chris Umans showed that methods from the representation theory of finite groups can be applied to fast matrix multiplication. In particular, they developed a method for embedding matrices in the group algebra of a finite group G, so that one can apply a Fourier transform and perform matrix multiplication in the group's frequency domain. For some choices of group and embedding, this can yield algorithms for multiplying n by n matrices in fewer than n3 field multiplications.

My work focuses on techniques for constructing efficient group algebra embeddings based on group actions; this occurs primarily through semi-direct product groups and an understanding of their actions on certain trees. I am also interested in studying such algorithms derived from matrix groups over finite fields, indexing so as to compute the output in a subgroup consisting of entries from one subfield while depositing the unwanted additional terms in the group algebra multiplication in another subfield, and in extensions of this algorithm to partial matrix multiplication (which I worked on in the Summer of 2008 with the Applied Representation Theory Group).