Method for operating a digital computer to reduce the computational complexity associated with dot products between large vectors
AssigneeOcean Logic Pty Ltd
InventorVincenzo Liguori
Life of this patent
Estimating the term…
Abstract
The present invention includes a method for operating a data processing system to compute an approximation to a scalar product between first and second vectors in which each vector is characterized by N components. The method includes replacing the first vector by a third vector that is a pyramid integer vector characterized by N components and an integer K equal to the sum of the absolute values of the N components, and computing a scalar product of the third vector with the second vector to provide the approximation to the scalar product between the first and second vectors. Computing the scalar product of the second and third vectors can be carried out by K additions followed by one floating point multiply.
Claims7
A method for operating a data processing system to compute an approximation to a scalar product between first and second vectors characterized by N components, each component being characterized by an absolute value, said method comprising:
- providing a repeated add multiplier;
- replacing said first vector by a constant times a third vector that is a pyramid integer vector characterized by N components, each component of said pyramid integer vector being characterized by an absolute value and an integer K equal to a sum of said absolute values of said N components;
- and
- computing a scalar product of said third vector with said second vector utilizing said repeated add multiplier to provide said approximation to said scalar product between said first and second vectors.
A digital filter that filters a digital signal through a finite impulse filter having N taps, each tap being characterized by a tap value, said filter comprising:
- a port that receives one of said tap values, wherein said tap value is an integer;
- and
- a repeated add multiplier that multiplies one of said digital signal values by said one of said tap values by repeatedly adding or subtracting said one of said digital signal values into an accumulator K times, where K is equal to said tap value and said tap value is an integer.
Dependencies are inferred from the claim text.