METHOD AND SYSTEM FOR FAST TENSOR-VECTOR MULTIPLICATION

• US 20140181171A1
• Filed: 12/24/2012
• Published: 06/26/2014
• Est. Priority Date: 12/24/2012
• Status: Abandoned Application

• Current Assignee: Pavel Dourbal
• Original Assignee: Pavel Dourbal
• Inventors: Dourbal, Pavel
• Application Number:
  US13/726,367
• Publication Number:
  US 20140181171A1
• 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 method and a system for fast tensor-vector multiplication provide factoring an original tensor into a kernel and a commutator, multiplying the kernel obtained by the factoring of the original tensor, by the vector and thereby obtaining a matrix, and summating elements and sums of elements of the matrix as defined by the commutator obtained by the factoring of the original tensor, and thereby obtaining a resulting tensor which corresponds to a product of the original tensor and the vector.

Claims

1. A method for fast tensor-vector multiplication, comprising the steps of factoring an original tensor into a kernel and a commutator;

multiplying the kernel obtained by the factoring of the original tensor, by the vector and thereby obtaining a matrix; and

summating elements and sums of elements of the matrix as defined by the commutator obtained by the factoring of the original tensor, and thereby obtaining a resulting tensor which corresponds to a product of the original tensor and the vector.

2. The method according to claim 1, further comprising rounding elements of the original tensor to a desired precision and obtaining the original tensor with the rounded elements, wherein the factoring includes factoring the original tensor with the rounded elements into the kernel and the commutator.

3. The method according to claim 1, wherein the factoring of the original tensor includes factoring into the kernel which contains kernel elements that are different from one another, and wherein the multiplying includes multiplying the kernel which contains the different kernel elements.

4. The method according to claim 1, further comprising using as the commutator a commutator image in which indices of elements of the kernel are located at positions of corresponding elements of the original tensor.

5. The method according to claim 4, wherein the summating includes summating on a priority basis of those pairs of elements whose indices in the commutator image are encountered most often and thereby producing the sums when the pair is encountered for the first time, and using the obtained sum for all remaining similar pairs of elements.

6. The method according to claim 1, further comprising using a plurality of consecutive vectors shifted in a manner selected from the group consisting of cyclically and linearly;

and, for the cyclic shift, carrying out the multiplying by a first of the consecutive vectors and cyclic shift of the matrix for all subsequent shift positions, while, for the linear shift, carrying out the multiplying by a last appeared element of each of the consecutive vectors and linear shift of the matrix.

7. The method according to claim 1, further comprising using as the original tensor a tensor selected from the group consisting of a matrix and a vector.

8. The method according to claim 1, wherein elements of the tensor and the vector are elements selected from the group consisting of single bit values, integer numbers, fixed point numbers, floating point numbers, non-numeric literals, real numbers, imaginary numbers, complex numbers represented by pairs having one real and one imaginary components, complex numbers represented by pairs having one magnitude and one angle components, quaternion numbers, and combinations thereof.

9. The method according to claim 8, where operations with the tensor and the vector with elements being non-numeric literals are string operations selected from the group consisting of concatenation operations, string replacement operations, and combinations thereof.

10. The method according to claim 8, where operations with the tensor and the vector with elements being single bit values are logical operations and their logical inversions selected from the group consisting of logic conjunction operations, logic disjunction operations, modulo two addition operations, and combinations thereof.

12. A system as defined in claim 9, wherein the means for factoring the original tensor into the kernel and the commutator comprise a precision converter converting tensor elements to desired precision and a factorizing unit building the kernel and the commutator;

the means for multiplying the kernel by the vector comprise a multiplier set performing all component multiplication operations and a recirculator storing and moving results of the component multiplication operations; and

the means for summating the elements and the sums of the elements of the matrix comprise a reducer which builds a pattern set and adjusts pattern delays and number of channels, a summator set which performs all summating operations, an indexer and a positioner which define indices and positions of the elements or the sums of elements utilized in composing the resulting tensor, the recirculator storing and moving results of the summation operations, and a result extractor forming the resulting tensor.

11. A system for fast tensor-vector multiplication, comprising means for factoring an original tensor into a kernel and a commutator;

means for multiplying the kernel obtained by the factoring of the original tensor, by the vector and thereby obtaining a matrix; and

means for summating elements and sums of elements of the matrix as defined by the commutator obtained by the factoring of the original tensor, and thereby obtaining a resulting tensor which corresponds to a product of the original tensor and the vector.