Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar?

It feels to me that there should be some exploit to do that. After all we will multiply two vectors elementwise in N steps. The original problem is simpler as it's only scalar by vector. Shouldn't we be able to use the sparsness in our advantage?


You seem to be focused on only one operand, the scalar. You can't get away from the fact that the other operand, the vector, contains $N$ elements and each of them need to be multiplied by the scalar. So, in general, there's nothing sparse about that. It just so happens that each of $N$ elements must get multiplied by the same number.

  • $\begingroup$ Fair enough. In principle I am interested in convolution. When we convolve 2 vectors through FFT we get O(N log(N)), whereas naivly it would be O(N^2). The speed comes from the fact that the neighbouring elements of convolution share many multiplications. I felt that sparseness in general allows for speed. Is there any good relationship between the two? $\endgroup$ – neuronich Feb 7 '15 at 0:04
  • $\begingroup$ I believe the speedup you're seeing is due to the fact that FFT is a divide and conquer algorithm which isn't affected by the sparsity of the data per se. Sparseness can be leveraged when you can use compact data structures. i.e. non-zero terms only in sparse matrices. $\endgroup$ – Logan Mayfield Feb 7 '15 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.