更快的投影范数（二次形式、度量矩阵...）式计算

发布于 2024-08-27 21:46:50 字数 465 浏览 12 评论 0原文

我需要执行大量的计算，

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

其中 X(:,i) 是向量，A 是对称矩阵。循环中执行此操作

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

表面上，我可以在一个缓慢的

z = diag(X' * A * X)

，也可以将其矢量化，因为当 X 有很多列时，这会不可接受地浪费 RAM。目前我正在妥协

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

哪个更快/更轻，但似乎仍然不满意。

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

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

堇色安年 2024-09-03 21:46:50

在 MATLAB 中尝试一下：

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

这给出的结果相当于 Federico的建议使用函数DOT ，但应该跑得稍快一些。这是因为 DOT 函数在内部计算结果与我上面使用 SUM 的方式相同功能。但是，DOT 还具有额外的输入参数检查和在处理复数的情况下进行额外的计算，这是您可能不想要或不需要的额外开销。

关于计算效率的说明：

尽管两种方法运行速度之间的时间差异很小，但如果您要执行操作很多次，开始加起来。为了测试相对速度，我创建了两个 100×100 的随机值矩阵，并在多次运行中对这两种方法进行计时，以获得平均执行时间：

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

使用 SUM 而不是 DOT 将此操作的执行时间减少了大约 28%。矩阵越大，两种方法之间的差异就越可以忽略不计。

总而言之，如果此计算代表代码运行速度的重大瓶颈，我会使用 SUM。否则，任何一个解决方案都应该没问题。

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.

回复收藏 0 原文

半边脸i 2024-09-03 21:46:50

试试这个：

z = dot(X, A*X)

我这里没有 Matlab 来测试，但它可以在 Octave 上运行，所以我希望 Matlab 有一个类似的 dot() 函数。

来自八度的帮助：

  -- 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.

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.

回复收藏 0 原文