我编写的一些迭代矩阵算法（CG、GMRES 等）表现得相当有趣。他们收敛到正确的答案，但运行时间异常长。我正在找出原因。
我认为的第一步是找出方法的算法复杂性。例如，我需要知道 CG 是否确实像预期的那样采用并且类似。
如何找出这些方法的确切算法复杂度？（我正在寻找某种方法来获得算法的确切界限，例如）。
甚至在此之前，这是提高性能的有效第一步吗？
到目前为止，我专注于单核性能（这本身就很糟糕）。
我也在考虑尝试确定内存访问。是否有任何免费软件（不一定是开源）可以让我在一个漂亮的 GUI 中这样做？我使用 VTune 进行并行，但它对串行没有用。
我试过谷歌搜索，但所有算法问题最终都出现在计算的搜索/排序部分，这与迭代矩阵算法完全不同。
我已经尝试解决从 1 到 1000 的矩阵大小的算法，绘制该大小所花费的平均时间图并曲线拟合它（二次）。但我似乎没有通过这个。
编辑：为了清楚起见，我想验证算法在实践中的复杂性是否与理论预测的相同。我想验证我的算法 Matrix-Vector 确实是。
此外，我不介意了解每次迭代的复杂性。
您拥有代码，因此为浮点运算的数量实现了一个全局计数器，并在每次函数调用时递增计数器。没有办法绕过计数操作。您可以使用类似的全局计数器来测量内存访问次数。
要获得性能估计，请测量单次迭代的时间以获得 FLOP/TIME。然后，您可以将 FLOP/TIME 与您的处理器峰值性能进行比较。当然，您可以对数据移动的总数（以字节为单位）执行相同的操作。
具有计数触发器功能的软件是 PETSc，请参阅他们的文档以获取函数PetscLogFlops和PetscGetFlops。该文档提供了很好的示例代码和源代码链接。
有关在当前 CPU 上接近峰值 FLOPS 性能所涉及的内容的指导性讨论，请参阅此线程。
有关书籍参考，您可以查看算法简介的第 3 章。
可以计算迭代求解器的迭代复杂度（例如操作数），但这可能会因为编译器的魔力而波动。但是，计数对发生的事情有很好的印象，您可以自己完成（或让代码计算）。
总运行的复杂性分析将是困难的，因为成本测量在某种程度上是任意的，而且更重要的是，例如共轭梯度的总运行时间将取决于矩阵的光谱特性。
从看看那里最好的开始，请参阅：BLAS / LAPACK / ARPACK / UMFPACK / Trilinos / PETSc（按复杂程度的粗略顺序）这些都依赖于高度特定于处理器的缓存优化操作，因此几乎可以预期的快。（这些都是 c/c++/fortran 怪物，这是有原因的！）
我认为这与您之前关于自制线性代数求解器的问题有关，并且我想重申，您自己的实现虽然是宝贵的学习经验，但几乎肯定会变慢。根据我的经验，如果你在这些代码的性能的一个因素（即 1/2）之内，你就做得很好！
在您验证算法的正确性后，导致性能大幅下降的主要是内存的意外分配/复制/释放。快速运行Valgrind可能会对此有所帮助。除此之外，请确保您没有存储中间产品或做额外的工作！
最后，值得注意的是，迭代方法在给定特定输入的情况下表现得十分有限。首先确保您的实现在给定具有明确定义的执行路径的某些类型的已知输入的情况下表现适当。一个示例可能是求解对角线或拉普拉斯矩阵，其中中间产品具有易于图形交互的形式。