Patent ID: 7792894

Claim:
One or more computer-readable storage media comprising computer-executable instructions for performing a method for producing a data matrix representing the product of two data matrices in a computer system and thereby providing a performance benefit over direct entry-multiplication techniques measured in processing cycles of the computer system, the method comprising: receiving first and second data matrices into a computer-readable storage medium; selecting a first, second, and third subset out of a selected group satisfying a triple product property; indexing the received first matrix according to the elements of the first and second subsets; indexing the received second matrix according to the elements of the second and third subsets; creating a first representation of the first received data matrix and a second representation of the second received data matrix in a form of elements of a group algebra based on the selected group by creating formal sums of elements from the selected group with coefficients taken from entries of the received data matrices, wherein: entries of the received data matrices are coefficients of respective elements of a formal sum; and entries from the received data matrices are paired with products of the inverse of a respective element corresponding to a first index of the entry and a respective element corresponding to a second index of the entry; computing the product of the first and second representations in the group algebra; and producing a result data matrix into a computer-readable storage medium by retrieving coefficients of the product in the group algebra.