CODEWITHSUNDEEP
matlabmatrix
george andrew
george andrew

Reputation: 471

fastest way to do triangular matrix vector multiplication in matlab?

A is n*n upper triangular matrix,x is n*1 vector, is there any faster way to do Ax in matlab than A is full, since it should need n*(n+1)/2 multiplications rather than n^2 multiplications. Thanks!

Upvotes: 2

Views: 1738

Answers (1)

Daniel
Daniel

Reputation: 36710

I don't think you can improve the performance because any solution making use of the zeros adds to much overhead. The first idea to increase the performance would be to exclude the quarter containing only zeros, I did this using this function:

@(x,y)[x(1:end/2,1:end/2)*y(1:end/2);x(end/2+1:end,:)*y]

This way 50% of the multiplications by zero are skipped.

And compared it to the standard way:

@(x,y)(x*y)

Using random input data:

@(n)triu(rand(n))
@(n)rand(n,1)

The results show that simply multiplication is faster.

enter image description here

Exection Times (mean)

                 @(x,y)(x*y)    @(x,y)[x(1:end/2,1:end/2)*y(1:end/2);x(end/2+1:end,:)*y]
           2        0.000015        0.000027
          10        0.000015        0.000028
         100        0.000023        0.000041
        1000        0.000454        0.003433
        2000        0.003002        0.014185
        3000        0.006505        0.032233
        4000        0.011401        0.057172
        5000        0.018567        0.089489
       10000        0.076099        0.351794

To summarize, you are doing 50% useless calculations, but with MATLAB's very efficient implementation of matrix multiplication. It is probably the best option.

Upvotes: 2

Related Questions