Computationally efficient Matrix-Vector multiplication

Hello All,

I have come across a problem of multiplying a matrix and a vector in a most efficient way possible. Instead of using N^2 operations, may be use N operations of (nlogn)^2 or something like that. I have seen and worked with some loops for making it fast and efficient which is in the link given below.

https://www.mathworks.com/matlabcentral/answers/7039-how-to-multiply-a-vector-with-each-column-of-a-matrix-most-efficiently.

But I am looking for some more options or ideas if anyone has to make it more efficient and reduce the number of operations as much as possible. Whereas, the above link only deals with making the operation fast multiplying each element in a loop but what would be the best way to reduce the number of operations. Ideas and suggestions or any help is welcome.

[Adam]

What version of Matlab are you using? If you have R2016b you can simply multiply them together:

result = myMatrix .* myVector;

In prior versions I would just use bsxfun, but if I was really bothered about speed I would run all the alternatives and time them, including repmat and a for loop and any other ideas I might have.

[Rahul Thakur]

I am using Matlab 2010 currently. And, yes I am thinking of reducing the operations or increasing the overall speed by any method where loop is the most preferred one I see as I am working with large matrices. Could you tell me about the usage of bsxfun or any example or link for it?

Answer 1

[James Tursa]

I am not following your suggestion. The link in question refers to an element-wise multiplication, which results in N^2 unique individual multiply results. You can't reduce this. For large sizes you can potentially speed the overall process up by multi-threading and optimizing how you access memory, but you can't change the fact that you need to do N^2 individual multiplies to get the NxN result. E.g., one of these depending on what you actually want:

result = bsxfun(@times,myMatrix,myVector);

or

result = bsxfun(@times,myMatrix,myVector.');

[Rahul Thakur]

Hello James,

Yes, that is what I also wrote but I wasn't clear (my bad) may be. The link I gave tells us to fast the overall operation by different methods using but the number of operations are same.

I was wondering is there a way or reducing the number of operations too as I am not an expert of Matlab but can work and deal with it though. I was researching for the above said problem and I found a research paper which discusses reducing the operation from N^2 to only N. The paper is: FAST MULTIRESOLUTION ALGORITHMS FOR MATRIX-VECTOR MULTIPLICATION by AMI HARTEN AND ITAI YAD-SHALOM. It can be found on google or I can attach it if you like. But I am not sure how to implement it and that's why I came on this page if any of the expert has dealt with this problem or have any idea of how to tackle or implement that algorithm.

Secondly, could you tell me or provide with some example or links on how to access the memory differently or using multi-threads just to speed up the overall process as you suggested if operations are not reduced.

Regards, Rahul

[James Tursa]

This article is almost certainly referring to a matrix multiply, not an element-by-element multiply. Completely different problem than the link in your post. For a matrix multiply, yes there are things you can do to speed things up by reordering the operations and multi-threading etc. You can do this for a variety of linear algebra operations, not just matrix multiply. In fact, companies have developed highly optimized libraries of code just for this purpose called BLAS and LAPACK, and MATLAB uses them in the background for linear algebra operations. E.g.,

a = rand(1000);  % arbitrary 1000x1000 matrix
b = rand(1000);  % arbitraty 1000x1000 matrix
c = a * b;  % matrix multiply

For the matrix multiply * operation, MATLAB actually calls a BLAS library function (dgemm) to do the work. Efficient memory access patterns and multi-threading are already built in to this library. This BLAS library also contains routines for matrix*vector multiplication (dgemv) ... again optimized for efficient memory access and multi-threaded.

So from a practical standpoint, you are not going to be able to write anything yourself that will beat this BLAS library for speed ... certainly not at the m-file level.

[Rahul Thakur]

Hello James,

I understand that and totally agree with you. But going more into the detail of my problem let me rephrase or put it like this.

I have a vector x and from that vector I am generating a Vandermonde Matrix V by inbuilt Matlab function vander(x). After this if I need to multiply this V*x which gives me a variable Q such that. Q=V*x. So, to multiply this equation and get Q in the fastest way (n log^2 n or n log n) and not just normal way (N^2).

For this what would be the best way to do the above operation Q=V*x in least computations. I have researched and found that there are two algorithms which deal with multiplying Vandermonder matrix to a vector in (n log n) computations. The algorithms are DIVIDE AND CONQUER and NEWTONS ITERATIVE algorithm. I read about the divide and conquer algorithm and it works in a similar manner as of dividing the matrix in two even and odd matrix and perfrom rest of the operation.

Do you have any idea about this? Or, if you are familiar with the Vandermonde matrix multiplication with a vector in an efficient way.

Thanks.