MATRIX CALCULATION METHOD, PROGRAM, AND SYSTEM

• US 20120203815A1
• Filed: 02/01/2012
• Published: 08/09/2012
• Est. Priority Date: 02/04/2011
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yanagisawa, Hiroki
• Application Number:
  US13/363,421
• Publication Number:
  US 20120203815A1
• Time in Patent Office: Days
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

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.

Claims

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.