JP5856926B2 - Apparatus and method for calculating product of vector and matrix and program - Google Patents

Description

  The present invention relates to an apparatus, method, and program for calculating a product of a vector and a matrix, and in particular, a vector and a matrix for performing high-speed calculation of a product of a vector and a matrix, which are general operations in linear algebra. The present invention relates to a product calculation apparatus, method, and program.

  The calculation of a product of a vector and a matrix is a general operation used in various engineering fields, and its speed is required. There is a technique for performing a product operation with a vector at high speed by converting a sparse binary matrix into a data structure called a zero-suppressed binary decision graph (ZDD) and holding it (for example, Non-Patent Document 1). In addition, in order to calculate the product of a matrix and a vector, it is necessary to execute a procedure to convert a sparse binary matrix to ZDD, but in order to execute this procedure at high speed, ZDD's simplified rules (deletion / sharing) A method of obtaining an irreducible ZDD of a regular term by analyzing in which scene is applied and processing each column of the matrix once (for example, Non-Patent Document 2) has also been proposed.

Masanobu Nishino, Yoshihito Yasuda, Toru Kobayashi: "Calculation of efficient set expansion using ZDD", Transactions of the Japanese Society for Artificial Intelligence, Vol. 27, No. 2, pp. 22-27 (2012) Masanobu Nishino, Yoshihito Yasuda, Shinichi Tsuji, Ryoji Kataoka, "Acceleration of computation in matrix compression using ZDD" The 26th Annual Conference of the Japanese Society for Artificial Intelligence, 2012

  However, there are cases where the calculation can be executed at high speed by the matrix table using ZDD of Non-Patent Document 1 and cases where the calculation is not possible. In addition, it can be said that conversion to ZDD can be performed at high speed by the method of Non-Patent Document 2, but if the converted ZDD is never used many times, calculation may not be performed at high speed.

  The present invention has been made in view of the above points, and provides a vector-matrix product calculation apparatus, method, and program capable of always calculating a product of a binary matrix and a real vector at high speed. With the goal.

In order to solve the above problems, the present invention (Claim 1) is a vector-matrix product calculation device for calculating a product of a vector and a matrix in linear algebra,
A binary matrix input means for obtaining a binary matrix;
A vector input means for obtaining an N-dimensional real vector;
Whether the binary matrix is converted into a zero-suppressed binary decision graph (ZDD) or whether the binary matrix is directly calculated as a binary matrix without conversion, as the density of non-zero elements of the binary matrix increases. A determination means that takes a small value and makes a determination based on a score calculated using a function that takes a smaller value as the rank of the matrix is smaller;
If it is determined that the determination means converts to ZDD, the binary matrix is converted to ZDD, and stored in the storage means, ZDD construction means,
ZDD operation means for calculating a product of the N-dimensional real vector acquired by the vector input means and a ZDD-transformed binary matrix stored in the storage means;
When it is determined by the determination means that conversion to ZDD is not performed, matrix calculation means for calculating a product of a binary matrix not using ZDD and the N-dimensional real vector is included.

In the present invention (Claim 2), in the determination means,
The density of non-zero elements of the binary matrix is σ, the average number of calculations using one binary matrix for repeated operations is K, the rank of the matrix is rank, the real parameters are λ ₁ , λ ₂ , ZDD Λ ₁ MN is the time required, λ ₂ MN is the time required to multiply the normal binary matrix and the vector, and h ( σ, rank), and the function h assumes a smaller value as σ is larger, and a smaller value as rank is smaller.

によりスコアθを算出し、θ＜１の場合には、ZDDに変換すると判定する手段を含む。

To calculate a score θ, and if θ <1, determine to convert to ZDD.

  As described above, according to the present invention, it is possible to always calculate a product of a binary matrix and a real vector at high speed by determining whether to convert to ZDD based on the score function.

It is a block diagram of the calculation apparatus in one embodiment of this invention. It is an example of the input binary matrix in one embodiment of this invention. 3 is a ZDD corresponding to the matrix of FIG. 2 and its computer representation in one embodiment of the present invention. It is a flowchart of the process of the calculation apparatus in one embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 shows a configuration of a computing device according to an embodiment of the present invention.

  The vector-matrix product calculation apparatus shown in FIG. 1 includes a binary matrix input unit 1, a determination processing unit 2, a ZDD construction unit 3, a ZDD operation unit 4, a vector input unit 5, a matrix operation unit 6, and an operation result output. Part 7.

  The binary matrix input unit 1 receives a binary matrix of M rows and N columns as an input. FIG. 2 shows an example of a binary matrix input.

  The determination processing unit 2 obtains the ratio of the non-zero component for the input binary matrix, and determines that the larger the non-zero ratio, the more compact the ZDD and the greater the conversion effect. Also, it is determined how many times the same matrix is reused. This is because the overhead of conversion can be compensated for overuse. A score function is set for a non-zero ratio and the number of times to be reused, and it is determined whether or not to convert to ZDD by comparing with a predetermined value.

  The ZDD constructing unit 3 converts the binary matrix into ZDD. For example, if the binary matrix of FIG. 2 is given as an input, it is converted to ZDD as shown in FIG.

  The ZDD operation unit 4 calculates the product of the binary matrix converted to ZDD and the N-dimensional real vector given from the vector input unit 5 and stores it in a memory (not shown).

The vector input unit 5 accepts an input of an N-dimensional real vector to be multiplied with the M-row / N-column binary matrix given from the binary matrix input unit 1 and outputs it to the ZDD operation unit 4 and the matrix operation unit 6. To do.

  The matrix calculation unit 6 calculates a product of a matrix and a vector that does not use ZDD, and stores it in a memory (not shown).

  The calculation result output unit 7 reads out and outputs the calculation results of the ZDD calculation unit 4 and the matrix calculation unit 6 from a memory (not shown).

  FIG. 4 is a flowchart of processing of the computing device according to the embodiment of the present invention.

  Step 1) The binary matrix input unit 1 receives a binary matrix.

  Step 2) In the determination processing unit 2, it is determined whether the binary matrix is converted to ZDD or not. In the conversion, the score θ is calculated by the following calculation formula and stored in a memory (not shown).

ここで、MNはM行N列、σは行列の非ゼロ要素の密度、Kは一つの二値行列を繰り返し演算に用いる平均の計算回数、そして、rankは行列の階数を表す。λ₁、λ₂は、事前に類似した行列で試行することによって得られる実数パラメータであり、λ₁MNはZDDの構築にかかる時間、λ₂MNは通常の二値行列とベクトルとの乗算にかかる時間を表すようにオペレータが決定し、入力する。h(σ，rank)は二値行列をZDDで表現したときに削減される計算時間の割合を表す関数とする。例えば、ZDDにすることで計算にかかる時間が半分になるなら、h(σ,rank)=0.5とする。関数ｈを
・σが大きい程小さな値をとる；
・rankが小さいほど小さな値をとる；
関数として定義する。

Here, MN is M rows and N columns, σ is the density of non-zero elements of the matrix, K is the average number of calculations using one binary matrix for repetitive operations, and rank is the rank of the matrix. λ ₁ and λ ₂ are real parameters obtained by trying with a similar matrix in advance, λ ₁ MN is the time taken to construct ZDD, λ ₂ MN is the multiplication of ordinary binary matrix and vector The operator decides and inputs such time. h (σ, rank) is a function representing the ratio of calculation time reduced when a binary matrix is expressed in ZDD. For example, if the calculation time is halved by using ZDD, h (σ, rank) = 0.5. Function h ・ The smaller the value of σ, the smaller the value;
・ The smaller the rank, the smaller the value;
Define as a function.

  Step 3) The determination processing unit 2 reads the score θ calculated in Step 2 from a memory (not shown), determines whether or not the score θ is smaller than 1, and if it is smaller, determines that the construction condition is satisfied. Migrate to If larger, the process proceeds to step 6 because the construction condition is not satisfied.

  Step 4) The binary matrix is converted into ZDD by the ZDD construction unit 3 and stored in a memory (not shown) as shown in FIG. For this process, the process described in “4. Construction of ZDD representing value matrix in 4.” of Non-Patent Document 2 is used.

  Step 5) The ZDD operation unit 4 calculates the product of the ZDD stored in the memory (not shown) in Step 4 and the N-dimensional real vector given from the vector input unit 5, and the calculation result output unit 7 Output to. The ZDD product is calculated using the processing described in “4. Matrix-Vector Multiplication Using ZDD” in Non-Patent Document 1.

  Step 6) If it is determined in step 3 that the construction condition is not satisfied, the matrix input from the binary matrix input unit 1 and the vector input from the vector input unit 5 are not converted to ZDD. Calculate the product of The calculation result is output from the calculation result output unit 7.

  The operations of the components of the computing device shown in FIG. 1 can be constructed as a program and installed in a computer used as the computing device to be executed or distributed via a network.

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

1 Binary Matrix Input Unit 2 Judgment Processing Unit 3 ZDD Construction Unit 4 ZDD Operation Unit 5 Vector Input Unit 6 Matrix Operation Unit 7 Operation Result Output Unit

Claims (5)

A binary matrix input means for obtaining a binary matrix;
A vector input means for obtaining an N-dimensional real vector;
Whether or not to convert the binary matrix into a zero-suppressed binary decision graph (ZDD), a function that takes a smaller value as the density of non-zero elements of the binary matrix is larger and takes a smaller value as the rank of the matrix is smaller Determining means for determining based on the score calculated using
And ZDD construction unit when it is determined that the conversion into ZDD, that converts the binary matrix ZDD by the determination means,
And ZDD calculating means for calculating the product of the previous SL Z DD and obtained the N-dimensional real vectors in the vector input unit,
A matrix calculation means for calculating a product of the binary matrix and the N-dimensional real vector when it is determined not to convert to ZDD by the determination means;
A device for calculating a product of a vector and a matrix, characterized by comprising: The determination means includes

Where σ is the density of non-zero elements of the binary matrix, K is the number of computations repeatedly using one binary matrix for computation, rank is the rank of the matrix, and λ ₁ is obtained by trial from λ ₁ MN. The real parameter determined to be the ZDD construction time, λ ₂ is the real parameter determined to be the time required for λ ₂ MN to multiply the binary matrix obtained by the trial and the vector, h ( (σ, rank) is a function that takes a smaller value as σ increases and a smaller value as rank decreases,
To calculate the score θ, and if θ <1, it is determined to convert to ZDD .
The apparatus for calculating a product of a vector and a matrix according to claim 1. Computer
A binary matrix input step for obtaining a binary matrix;
A vector input step for obtaining an N-dimensional real vector ;
Whether to convert the pre-Symbol binary matrix Zero-suppressed binary decision diagram (ZDD), as taking a small value density of non-zero elements of the binary matrix is large, takes a smaller value the rank of the matrix is small A determination step for determining based on a score calculated using a function;
If it is determined that converts the ZDD in the determination step, and ZDD construction step that converts the binary matrix ZDD,
And ZDD calculation step of calculating a product of said N-dimensional real vectors obtained in the previous SL vector input step and before Symbol Z DD,
If it is determined that no conversion before Symbol decision step ZDD, a matrix calculating step of calculating the product of the N-dimensional real vector and the binary matrix,
A method of calculating a product of a vector and a matrix, characterized in that The determination step includes

Where σ is the density of non-zero elements of the binary matrix, K is the number of computations repeatedly using one binary matrix for computation, rank is the rank of the matrix, and λ ₁ is obtained by trial from λ ₁ MN. The real parameter determined to be the ZDD construction time, λ ₂ is the real parameter determined to be the time required for λ ₂ MN to multiply the binary matrix obtained by the trial and the vector, h ( (σ, rank) is a function that takes a smaller value as σ increases and a smaller value as rank decreases,
4. The method of calculating a product of a vector and a matrix according to claim 3, wherein the score θ is calculated by the following equation, and when θ <1, it is determined to convert to ZDD. Computer
Calculation program for causing to function as each means as set forth in claim 1 or 2.

Images