Faster matrix multiplication via sparse decomposition

Abstract

A system comprising: at least one hardware processor; and a non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by said at least one hardware processor to: receive a first matrix and a second matrix, compute a first transformation of said first matrix, to obtain a transformed said first matrix, compute a second transformation of said second matrix, to obtain a transformed said second matrix, apply a bilinear computation to said transformed first matrix and said transformed second matrix, thereby producing a transformed multiplied matrix; and apply a third transformation to said transformed multiplied matrix, to obtain a product of said first and second matrices, wherein at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension.

1 . A system comprising:
 at least one hardware processor; and   a non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by said at least one hardware processor to:
 receive a first matrix and a second matrix, 
 compute a first transformation of said first matrix, to obtain a transformed said first matrix, 
 compute a second transformation of said second matrix, to obtain a transformed said second matrix, 
 apply a bilinear computation to said transformed first matrix and said transformed second matrix, thereby producing a transformed multiplied matrix; and 
 apply a third transformation to said transformed multiplied matrix, to obtain a product of said first and second matrices, 
 wherein at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension. 
   
     
     
         2 . The system of  claim 1 , wherein said non-homomorphic transformation is a decomposition. 
     
     
         3 . The system of  claim 2 , wherein said decomposition is a full decomposition. 
     
     
         4 . The system of  claim 1 , wherein said program instructions are further executable to select which at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension. 
     
     
         5 . The system of  claim 4 , wherein said selecting is based, at least in part, on a dimension of each of said first and second matrices. 
     
     
         6 . The system of  claim 2 , wherein said decomposition comprises a set of fast recursive transformations. 
     
     
         7 . The system of  claim 2 , wherein said decomposition is determined by solving at least one sparsification problem. 
     
     
         8 . The system of  claim 7 , wherein said program instructions are further executable to use (i) a first encoding matrix for said first transformation, (ii) a second encoding matrix for said second transformation, and (iii) a decoding matrix for said third transformation, wherein said at least one sparsification problem is at least one from the group consisting of: sparsification of said first encoding matrix, sparsification of said second encoding matrix, and sparsification of said decoding matrix. 
     
     
         9 . The system of  claim 8 , wherein solving said at least one sparsification problem comprises simultaneously solving three sparsification problems, one for each of:
 said first encoding matrix, said second encoding matrix, and said decoding matrix.   
     
     
         10 . A method comprising:
 receiving a first matrix and a second matrix;   computing a first transformation of said first matrix, to obtain a transformed said first matrix;   computing a second transformation of said second matrix, to obtain a transformed said second matrix;   applying a bilinear computation to said transformed first matrix and said transformed second matrix, thereby producing a transformed multiplied matrix; and   applying a third transformation to said transformed multiplied matrix, to obtain a product of said first and second matrices,   wherein at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension.   
     
     
         11 . The method of  claim 10 , wherein said non-homomorphic transformation is a decomposition. 
     
     
         12 . The method of  claim 11 , wherein said decomposition is a full decomposition. 
     
     
         13 . The method of  claim 10 , further comprising selecting which at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension. 
     
     
         14 . The method of  claim 13 , wherein said selecting is based, at least in part, on a dimension of each of said first and second matrices. 
     
     
         15 . The method of  claim 11 , wherein said decomposition comprises a set of fast recursive transformations. 
     
     
         16 . The method of  claim 11 , wherein said decomposition is determined by solving at least one sparsification problem. 
     
     
         17 . The method of  claim 16 , further comprising using (i) a first encoding matrix for said first transformation, (ii) a second encoding matrix for said second transformation, and (iii) a decoding matrix for said third transformation, wherein said at least one sparsification problem is at least one from the group consisting of: sparsification of said first encoding matrix, sparsification of said second encoding matrix, and sparsification of said decoding matrix. 
     
     
         18 . The method of  claim 17 , wherein solving said at least one sparsification problem comprises simultaneously solving three sparsification problems, one for each of: said first encoding matrix, said second encoding matrix, and said decoding matrix. 
     
     
         19 . The method of  claim 10 , wherein a leading coefficient of an arithmetic complexity of said bilinear computation is 2. 
     
     
         20 . A computer program product comprising a non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by at least one hardware processor to:
 receive a first matrix and a second matrix;   compute a first transformation of said first matrix, to obtain a transformed said first matrix;   compute a second transformation of said second matrix, to obtain a transformed said second matrix;   apply a bilinear computation to said transformed first matrix and said transformed second matrix, thereby producing a transformed multiplied matrix; and   apply a third transformation to said transformed multiplied matrix, to obtain a product of said first and second matrices,   wherein at least one of said first, second, and third transformations is a non-homomorphic transformation into a linear space of any intermediate dimension.   
     
     
         21 .- 41 . (canceled)