Patent ID: 9098460
Filing Date: 2015-08-04
Classification: G06F

Abstract:
1. A matrix calculation system for calculating funny matrix multiplication (FMM) of a matrix A and a matrix B the system comprising: a memory; a processor communicatively coupled to the memory, the processor configured to: store in the memory the matrix A in a column-major layout and store in the memory the matrix B in a row-major layout; sequentially calculate a permutation of indices {ai} in which values are arranged in a non-decreasing order with respect to each i-th row where i=1 to the number of rows of the matrix A; store a value, which is greater than a value sufficiently large that does not appear in actual processing as a value of a matrix, for C[i, j] with respect to each j-th column where j=1 to the number of columns of the matrix A in the i-th row, first, storing the values of C[i, j], which are i and j components of a matrix C which is a result of the FMM calculation, in a predetermined variable defined as a variable best, sequentially calculating best=min{best, A[i, ak]+B[ak, j]} while incrementing k by one from 1, wherein ak is the k-th element of the permutation of indices {ai}, and determining if k exceeds the number of rows of the matrix A and determining if A[i, ak] exceeds best/2, and updating C[i, j] according to C[i, j]=best in response to either determination being true; sequentially calculate a permutation of indices {bj} in which values are arranged in a non-decreasing order with respect to each j-th column where j=1 to the number of columns of the matrix B; and set the values of C[i, j], which are i and j components of the matrix C, in best, with respect to each j-th column where j=1 to the number of columns of the matrix B in the j-th column, sequentially calculate best=min{best, A[i, bk]+B[bk, j]} while incrementing k by one from 1, wherein bk is the k-th element of the permutation of indices {bj}, and update C[i, j] according to C[i, j]=best in response to k exceeding the number of columns of the matrix B or B[bk, j] exceeds best/2, wherein the processor calculates a value of variable best once, and then stops the calculating of a respective min{best, A[i, ak]+B[ak, j]}value and min{best, A[i, bk]+B[bk, j]} value on the basis of the best value to result in a faster calculation of the respective minimum value, thereby enabling increasing the speed of an FMM calculation process by the processor.