我感到非常惊讶的是，您的讨论中没有提到条件反射或谱的形状，因为这将是迭代方法是否可以击败密集方法的决定性属性。

作为一个极端的例子，假设你的密集矩阵是单位矩阵的一些小扰动。然后大多数迭代方法将收敛于$O(1)$迭代，密集矩阵向量乘法是$O(n^2)$，所以求解成本为$O(n^2)$而不是$O(n^3)$. 显然有一大类条件良好的稠密矩阵可以进行类似的论证。他们是否出现在实践中是另一个问题......

根据我的经验，当我生成随机密集矩阵时，相对于 LU 或 QR 求解器，GMRES（以及 HPD 矩阵的 CG）的性能相当糟糕。然而，当只需要少量迭代时，迭代方法对于非常大的矩阵肯定会更快。

编辑：因为我被问及实验结果，我想我会展示一些 MATLAB 代码和一些时间，这会使这一点更清楚一点。下面生成一个随机$2000 \times 2000$具有从 [1,2] 均匀采样的特征值的真实密集 SPD 矩阵，并比较未预处理的 CG（精度为 6 位）和 Cholesky 求解器的时序。在我两岁的 iMac 上，CG 已经快了四倍。

    %
    % Compares CG and a dense Cholesky solve for a well-conditioned SPD matrix
    %
    n=2000;
    S=1;
    T=2;
    tol=1e-6;

    % Build an n x n dense SPD matrix with eigenvalues uniformly sampled from 
    % [S,T]
    D=diag(random('uniform',S,T,n,1));
    U=randn(n,n);
    [U,R]=qr(U);
    clear R;
    A=U*D*U';

    % Set up a random right-hand side
    b=randn(n,1);

    % Solve with CG to the specified tolerance, ensuring that the maximum
    % number of iterations is not reached
    fprintf(1,'Running CG...\n');
    tic; [x,flag,relres,iter]=pcg(A,b,tol,10*n); toc;
    iter

    % Solve using a Cholesky decomposition
    fprintf(1,'Running a Cholesky solver...\n');
    opts.LT=false; opts.UT=false; opts.UHESS=false;
    opts.SYM=true; opts.POSDEF=true;
    opts.RECT=false; opts.TRANSA=false;
    tic; x=linsolve(A,b,opts); toc;

我看到了以下结果：

正在运行 CG...经过的时间是 0.074933 秒。

迭代器 =

 8

运行 Cholesky 求解器...经过的时间是 0.279619 秒。

现在，如果$A$而是生成具有正态分布条目的矩阵作为对称乘积，例如，

    A=randn(n,n);
    A=A'*A;

那么情况对CG来说不是那么好。我看到了以下输出：

运行 CG...经过的时间是 28.568865 秒。

迭代器 =

    3892

条件编号为 1.0587e+09。

在大多数情况下，我知道 Krylov 方法用于密集问题的地方，算子是恒等式的低秩扰动（通过离散化连续统算子获得，这是恒等式的紧凑扰动）。这样的算子经常出现在边界积分方程中，作为第二类离散 Fredholm 积分算子。这些算子有一些极值特征值，但谱迅速衰减到恒等式，因此即使系统由于极值特征值而处于病态，Krylov 方法也可以非常有效。

对于这些问题，可能会使用一些快速方法（例如 FMM）来应用算子，但有时会使用密集求和（特别是对于 2D 问题）进行组合。如果边界和/或系数结构非常复杂，频谱的衰减可能不是特别快，在这种情况下，您可以考虑使用“第二类多重网格”。

在其他示例中，“密集”运算符可能作为 Schur 补码获得，在这种情况下，可能有一种无需组装即可应用它的快速方法，并且可通过近似交换子参数获得对预处理有用的近似值。

作为一般规则，Krylov 方法对于密集系统来说不是很好的通用方法，但如果您的问题具有可利用的结构，例如良好的调节、频谱衰减、快速应用或有效的预处理器，那么 Krylov 方法肯定是有用的。

CG 最初是因为您观察到的这种准确性损失而被放弃的。当它被用作近似求解器时，它得到了复兴。所以我不认为你想重新审视这个问题。预处理非常有用，至少是对角预处理。

迭代方法非常依赖于问题，所以我建议找到一个需要解决密集系统的应用程序，或者更好地转向稀疏系统，以集中您的研究。注意，Krylov 方法在过去 30 到 40 年中得到了广泛的研究，除非你有某种领导或专家顾问，否则在这里可能很难找到一个好的话题。应用程序的某些属性通常可以通过预处理来利用，这可以提供论文的内核。