更快的投影范数(二次形，度量矩阵...)样式计算 [英] Faster projected-norm (quadratic-form, metric-matrix...) style computations

问题描述

我需要对表格进行很多评估

I need to perform lots of evaluations of the form

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

其中X(:，i)是一个向量，A是一个对称矩阵.表面上，我可以循环执行此操作

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)

当X的列很多时，浪费RAM是不可接受的.目前，我正在妥协

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.

我希望可能会有一些matlab/scilab习惯用法或技巧来更有效地实现此结果?

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

推荐答案

在MATLAB中尝试一下:

Try this in MATLAB:

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

给出的结果等同于 Federico的建议使用功能 DOT ，但是应该运行得更快.这是因为 DOT 函数在内部计算结果与我上面使用 SUM 的方式相同功能.但是， DOT 也具有附加的输入参数检查和如果您要处理复数，则需要额外的计算，这可能是您不需要或不需要的额外开销.

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.

关于计算效率的说明:

尽管两种方法运行的时间之间的时间差很小，但是如果要执行操作很多次，它将开始累加.为了测试相对速度，我创建了两个100 x 100随机值矩阵，并对这两种方法进行了多次计时，以得出平均执行时间:

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

使用 SUM 代替 DOT 因此，该操作的执行时间减少了约28％适用于约10,000个元素的矩阵.矩阵越大，两种方法之间的差异就越小.

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.

这篇关于更快的投影范数(二次形，度量矩阵...)样式计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！