Faster calculated values ​​(quadratic form, metric matrix ...)

Question

I need to do a lot of form evaluations

X(:,i)' * A * X(:,i) i = 1...n 

where X (:, i) is a vector, and A is a symmetric matrix. Allegedly, I can either do this in a loop

 for i=1:n z(i) = X(:,i)' * A * X(:,i) end 

which is slow, or vectorize it as

 z = diag(X' * A * X) 

which unacceptably gives up RAM when X has many columns. I'm currently compromising

 Y = A * X for i=1:n z(i) = Y(:,i)' * X(:,i) end 

which is a bit faster / lighter but still seems unsatisfactory.

I was hoping there might be some kind of idiot or Matlab / scilab trick to achieve this result more efficiently?

Answer 1

Try this in MATLAB:

 z = sum(X.*(A*X)); 

This gives results equivalent to the Federico suggestion using the DOT function, but should work a little faster. This is because the DOT function internally calculates the result in the same way as I did above using SUM . However, the DOT also has additional checks of input arguments and additional calculations for cases when you are dealing with complex numbers that the extra overhead probably does not want or need.

A note on computational efficiency:

Despite the fact that the time difference is small between how quickly these two methods work, if you intend to perform the operation many times, it will begin to add up. To check the relative speeds, I created two 100-by-100 matrices of random values ​​and timed two methods for many runs to get the average execution time:

  METHOD AVERAGE EXECUTION TIME -------------------------------------------- Z = sum(X.*Y); 0.0002595 sec Z = dot(X,Y); 0.0003627 sec 

Using SUM instead of DOT therefore reduces the execution time of this operation by about 28% for matrices with about 10,000 elements. The larger the matrix, the negligible difference between the two methods will be.

To summarize, if this calculation presents a significant bottleneck in how fast your code works, I would go with a solution using SUM . Otherwise, any decision should be in order.

Answer 2

Try the following:

 z = dot(X, A*X) 

I don't have Matlab to test, but it works on Octave, so I expect Matlab to have a similar dot() function.

From Octave Help:

  -- Function File: dot (X, Y, DIM) Computes the dot product of two vectors. If X and Y are matrices, calculate the dot-product along the first non-singleton dimension. If the optional argument DIM is given, calculate the dot-product along this dimension. 

Answer 3

To complete the answer gnovice in Scilab will be

 z = sum(X .* Y, 1)'