matlab - 在matlab中进行三角矩阵向量乘法的最快方法？

Question

A是n*n上三角矩阵，x是n*1向量，有没有比A满的更快的方法在matlab中执行Ax，因为它应该需要n*(n+1)/2次乘法而不是n^2 次乘法。 谢谢!

Answer 1

我认为您无法提高性能，因为任何使用零的解决方案都会增加很多开销。提高性能的第一个想法是排除仅包含零的季度，我使用此函数做到了这一点:

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

这样就可以跳过 50% 的零乘法。

并将其与标准方式进行比较:

@(x,y)(x*y)

使用随机输入数据:

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

结果表明简单的乘法更快。

执行时间(平均)

                 @(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

总而言之，您正在执行 50% 无用的计算，但使用 MATLAB 非常高效的矩阵乘法实现。这可能是最好的选择。