Etd

Fast Matrix Multiplication by Group Algebras

Public

Downloadable Content

open in viewer

Based on Cohn and Umans’ group-theoretic method, we embed matrix multiplication into several group algebras, including those of cyclic groups, dihedral groups, special linear groups and Frobenius groups. We prove that SL2(Fp) and PSL2(Fp) can realize the matrix tensor ⟨p, p, p⟩, i.e. it is possible to encode p × p matrix multiplication in the group algebra of such a group. We also find the lower bound for the order of an abelian group realizing ⟨n, n, n⟩ is n3. For Frobenius groups of the form Cq Cp, where p and q are primes, we find that the smallest admissible value of q must be in the range p4/3 ≤ q ≤ p2 − 2p + 3. We also develop an algorithm to find the smallest q for a given prime p.

Creator
Contributors
Degree
Unit
Publisher
Language
  • English
Identifier
  • etd-012318-234642
Keyword
Advisor
Defense date
Year
  • 2018
Date created
  • 2018-01-23
Resource type
Rights statement

Relations

In Collection:

Items

Items

Permanent link to this page: https://digital.wpi.edu/show/sn009x89n