Ora*_*ran 3 algorithm complexity-theory matrix sparse-matrix eigen
我想表达两种算法的计算复杂度：稀疏矩阵稀疏向量乘法和稀疏矩阵稀疏矩阵乘法，如在 Eigen 或 Cusparse 中实现的，使用 CSR 表示。
我知道这取决于几个参数，尤其是每个元素中非零值的数量。
但是，我无法找到详细说明此类算法复杂性并使用 O( ) 符号表示的出版物。
说你是乘A*B用A一m*k用矩阵a每列非零，和B一个k*n与矩阵b每列非零。那么，操作次数（*和+）为：
2*n*b*a
因为对于每个的n列B，我们必须通过环路b的列A对于其中相应的元件B是非零，然后乘法累加各个a非零。如果正确实施，如在本征或Cusparse，我们有整整三个嵌套循环n，b和a迭代，复杂性是这样O(a*b*n)。