hi all,
suppose I have A that is numpy ndarray of floats, with shape n x n.
I want to obtain dot(A, b), b is vector of length n and norm(b)=1, but instead of exact multiplication I want to approximate b as a vector [+/- 2^m0, ± 2^m1, ± 2^m2 ,,, ± 2^m_n], m_i are integers, and then invoke left_shift(vector_m) for rows of A.
So, what is the simplest way to do it, without cycles of course? Or it cannot be implemented w/o cycles with current numpy version?
Thank you in advance, D.
On Wed, May 20, 2009 at 14:24, dmitrey dmitrey.kroshko@scipy.org wrote:
hi all,
suppose I have A that is numpy ndarray of floats, with shape n x n.
I want to obtain dot(A, b), b is vector of length n and norm(b)=1, but instead of exact multiplication I want to approximate b as a vector [+/- 2^m0, ± 2^m1, ± 2^m2 ,,, ± 2^m_n], m_i are integers, and then invoke left_shift(vector_m) for rows of A.
You don't shift floats. You only shift integers. For floats, multiplying by an integer power of 2 should be fast because of the floating point representation (the exponent just gets incremented or decremented), so just do the multiplication.
So, what is the simplest way to do it, without cycles of course? Or it cannot be implemented w/o cycles with current numpy version?
It might help if you showed us an example of an actual b vector decomposed the way you describe. Your description is ambiguous.
On May 20, 10:34 pm, Robert Kern robert.k...@gmail.com wrote:
On Wed, May 20, 2009 at 14:24, dmitrey dmitrey.kros...@scipy.org wrote:
hi all,
suppose I have A that is numpy ndarray of floats, with shape n x n.
I want to obtain dot(A, b), b is vector of length n and norm(b)=1, but instead of exact multiplication I want to approximate b as a vector [+/- 2^m0, ± 2^m1, ± 2^m2 ,,, ± 2^m_n], m_i are integers, and then invoke left_shift(vector_m) for rows of A.
You don't shift floats. You only shift integers. For floats, multiplying by an integer power of 2 should be fast because of the floating point representation (the exponent just gets incremented or decremented), so just do the multiplication.
So, what is the simplest way to do it, without cycles of course? Or it cannot be implemented w/o cycles with current numpy version?
It might help if you showed us an example of an actual b vector decomposed the way you describe. Your description is ambiguous.
-- Robert Kern
For the task involved (I intend to try using it for speed up ralg solver) it doesn't matter essentially (using ceil, floor or round), but for example let m_i is floor(log2(b_i)) for b_i > 1e-15, ceil(log2(-b_i)) for b_i < - 1e-15, for - 1e-15 <= b_i <= 1e-15 - don't modify the elements of A related to the b_i at all.
D.
On Wed, May 20, 2009 at 14:46, dmitrey dmitrey.kroshko@scipy.org wrote:
On May 20, 10:34 pm, Robert Kern robert.k...@gmail.com wrote:
On Wed, May 20, 2009 at 14:24, dmitrey dmitrey.kros...@scipy.org wrote:
hi all,
suppose I have A that is numpy ndarray of floats, with shape n x n.
I want to obtain dot(A, b), b is vector of length n and norm(b)=1, but instead of exact multiplication I want to approximate b as a vector [+/- 2^m0, ± 2^m1, ± 2^m2 ,,, ± 2^m_n], m_i are integers, and then invoke left_shift(vector_m) for rows of A.
You don't shift floats. You only shift integers. For floats, multiplying by an integer power of 2 should be fast because of the floating point representation (the exponent just gets incremented or decremented), so just do the multiplication.
So, what is the simplest way to do it, without cycles of course? Or it cannot be implemented w/o cycles with current numpy version?
It might help if you showed us an example of an actual b vector decomposed the way you describe. Your description is ambiguous.
-- Robert Kern
For the task involved (I intend to try using it for speed up ralg solver) it doesn't matter essentially (using ceil, floor or round), but for example let m_i is floor(log2(b_i)) for b_i > 1e-15, ceil(log2(-b_i)) for b_i < - 1e-15, for - 1e-15 <= b_i <= 1e-15 - don't modify the elements of A related to the b_i at all.
I strongly suspect that a plain dot(A, b) will be faster than doing all of that. With a little bit of work with frexp() and ldexp(), you could probably do those floor(log2())'s cheaply, but ultimately, you will still need to do a dot(A, b_prime) at the end. There is no bit-shift operation available for floats (anywhere, not just numpy); you have to form the float corresponding to +-2**m and multiply. If you had many A-matrices and a static b-vector, you might see a tiny improvement because all of the b_prime elements were exactly of the form +-2**m, but I doubt it.