Matrix calculation method, program, and system

Abstract

A matrix calculation method and system for calculating funny matrix multiplication (FMM) of a matrix A and a matrix B, including: sequentially calculating 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; storing a value, which is greater than expected 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; sequentially calculating 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 setting the values of C[i, j], which are i and j components of the matrix C.

1 . A matrix calculation method for calculating funny matrix multiplication (FMM) of a matrix A and a matrix B, by processing of a computer, the method comprising the steps of:
 sequentially calculating 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;   storing a value, which is greater than expected 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 (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 updating C[i, j] according to C[i, j]=best in response to k exceeding the number of rows of the matrix A or A[i, ak] exceeds best/2;   sequentially calculating 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   setting the values of C[i, j], which are i and j components of the matrix C, to 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 calculating 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 updating 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.   
     
     
         2 . The method according to  claim 1 , wherein:
 the matrix A is stored in a column-major layout and the matrix B is stored in a row-major layout; and   in the step of updating C[i, j] according to C[i, j]=best in response to A[i, ak]>best/2 and the step of updating C[i, j] according to C[i, j]=best in response to B[bk, j]>best/2, divided portions with loops integrated are executed in parallel by using an SIMD instruction.   
     
     
         3 . The method according to  claim 1 , wherein each of the matrices A, B, and C is a square matrix of n×n. 
     
     
         4 . A computer readable article of manufacture tangibly embodying non-transitory computer readable instructions which, when executed, cause a computer to carry out the steps of a method for calculating funny matrix multiplication (FMM) of a matrix A and a matrix B, the method comprising the steps of:
 sequentially calculating 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;   storing a value, which is greater than expected 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 (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 updating C[i, j] according to C[i, j]=best in response to k exceeding the number of rows of the matrix A or A[i, ak] exceeds best/2;   sequentially calculating 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   setting the values of C[i, j], which are i and j components of the matrix C, to 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 calculating 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 updating 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.   
     
     
         5 . The article of manufacture according to  claim 4 , wherein:
 the matrix A is stored in a column-major layout and the matrix B is stored in a row-major layout; and   in the step of updating C[i, j] according to C[i, j]=best in response to A[i, ak]>best/2 and the step of updating C[i, j] according to C[i, j]=best in response to B[bk, j]>best/2, divided portions with loops integrated are executed in parallel by using an SIMD instruction.   
     
     
         6 . The article of manufacture according to  claim 4 , wherein each of the matrices A, B, and C is a square matrix of n×n. 
     
     
         7 . A matrix calculation system for calculating funny matrix multiplication (FMM) of a matrix A and a matrix B, by processing of a computer, the system comprising:
 means for sequentially calculating 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;   means for storing a value, which is greater than expected 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 (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 updating C[i, j] according to C[i, j]=best in response to k exceeding the number of rows of the matrix A or A[i, ak] exceeds best/2;   means for sequentially calculating 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   means for setting the values of C[i, j], which are i and j components of the matrix C, to 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 calculating 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 updating 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.   
     
     
         8 . The system according to  claim 7 , wherein:
 the matrix A is stored in a column-major layout and the matrix B is stored in a row-major layout; and   the means for updating C[i, j] according to C[i, j]=best in response to A[i, ak]>best/2 and the means for updating C[i, j] according to C[i, j]=best in response to B[bk, j]>best/2 execute divided portions with loops integrated in parallel by using an SIMD instruction.   
     
     
         9 . The system according to  claim 7 , wherein each of the matrices A, B, and C is a square matrix of n×n.