Return to search

Fast Matrix Multiplication via Group Actions

Recent work has shown that fast matrix multiplication algorithms can be constructed by embedding the two input matrices into a group algebra, applying a generalized discrete Fourier transform, and performing the multiplication in the Fourier basis. Developing an embedding that yields a matrix multiplication algorithm with running time faster than naive matrix multiplication leads to interesting combinatorial problems in group theory. The crux of such an embedding, after a group G has been chosen, lies in finding a triple of subsets of G that satisfy a certain algebraic relation. I show how the process of finding such subsets can in some cases be greatly simplified by considering the action of the group G on an appropriate set X. In particular, I focus on groups acting on regularly branching trees.

Identiferoai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1224
Date01 May 2009
CreatorsOrem, Hendrik
PublisherScholarship @ Claremont
Source SetsClaremont Colleges
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceHMC Senior Theses

Page generated in 0.0025 seconds