Trsm和其他BLAS操作的时间复杂度是多少？

Question

我用cuBlas函数替换它的所有线性代数运算来加速一个模型。我希望得到模型的时间复杂度或失败值，以评估其在roofline模型中的性能。

该模型有两种操作：Gemm和Trsm。

我知道Gemm的失败是大约2*k*m*n从问题：如何计算调用cuBlas函数的MPI程序的触发器

标准的BLAS GEMM运算为C <-α* (A点B) +β*C，对于A (m×k)，B (k×n)和C (m×n)，A行和B列的每一个内积乘以α为2*k+1触发器，A点B中有m*n内积，在该点积中添加β*C的内积为m*n。当α和β均为非零时，模型总失败数为(2 *k+ 3) * (m * n)。

但是对于Trsm，我不知道它的计算复杂性。我找到的所有文档都说它是关于O(n^3)的，这还不够清楚，无法得到计算的复杂性。

衷心感谢您的回答！

Answer 1

但是对于Trsm，我不知道它的计算复杂性。我找到的所有文档都说它是关于O(n^3)的，这还不够清楚，无法得到计算的复杂性。

它是关于O(n^2)而不是O(n^3)。

TRSM根据矩阵的形式执行许多不同的实现，但是对于标准的B <- alpha * inv(A) dot B，其中B是(m×n)，而A是非单位的上三角矩阵，运算计数应该类似于n * (3/2*m + 1) n对角缩放运算加上所有非零行项的1/2 *3*m*n操作。

如果您想知道任何BLAS或LAPACK例程的引用实现的确切触发器计数，那么最明显的方法是检查参考串行码和计数浮点操作，无论是手工操作还是代码本身的检测。