Faster projected-norm (quadratic-form, metric-matrix...) style computations

Question

I need to perform lots of evaluations of the form

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

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

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

which is slow, or vectorise it as

z = diag(X' * A * X)

which wastes RAM unacceptably when X has a lot of columns. Currently I am compromising on

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

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

I was hoping there might be some matlab/scilab idiom or trick to achieve this result more efficiently?

Answer 1

Try this:

z = dot(X, A*X)

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

From Octave's 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 2

Try this in MATLAB:

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

This gives results equivalent to Federico's suggestion using the function DOT, but should run slightly faster. This is because the DOT function internally computes the result the same way as I did above using the SUM function. However, DOT also has additional input argument checks and extra computation for cases where you are dealing with complex numbers, which is extra overhead you probably don't want or need.

A note on computational efficiency:

Even though the time difference is small between how fast the two methods run, if you are going to be performing the operation many times over it's going to start to add up. To test the relative speeds, I created two 100-by-100 matrices of random values and timed the two methods over many runs to get an 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 around 10,000 elements. The larger the matrices, the more negligible this difference will be between the two methods.

To summarize, if this computation represents a significant bottleneck in how fast your code is running, I'd go with the solution using SUM. Otherwise, either solution should be fine.

Answer 3

For completeness, gnovice's answer in Scilab would be

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