[评论线程足够长，可以转换为答案。]

我们承认大多数矩阵集合不包括物理上合理的右手边。如果我们想测试求解器的性能，我们必须生成要求解的问题 --- 要么是右手边要么是我们计算b 的解然后求解到一定精度。后者很方便，因为它可以让我们检查准确性。像未预处理的 GMRES 这样的求解器在残差的 2 范数中是最优的（在子空间上），因此误差的范数。例如，这是一个明显弱于误差 2 范数的范数，因此比较误差范数中的求解器确实很有用。$b$$x$$b \gets A x$$A y = b$$A^* A$

选择随机向量的危险

生成或的常用方法是从独立随机分布中提取。这是有缺陷的，因为这些随机向量几乎与与最小特征值相关的特征向量正交——正是减缓求解器收敛的模式。例如，如果您对 Neumann Laplacian（具有恒定的零空间）使用均值为 0 的高斯分布，则域的任何重要部分的平均值几乎为零，这意味着不会发生长程交互。在这种情况下，粗网格变得不必要，因为您只需将信息移动到足够远以使随机过程均质化。$x$$b$

如果您的分布与最低特征向量正交，则每个随机向量（或比较时都无关紧要，但如果接近于零，则将是甚至更小），您绘制的将具有与“有问题的模式”几乎正交的特性，从而人为地快速收敛。一个独立的随机分布将与大多数或所有这些“有问题的模式”（例如，弹性的平移和旋转）正交。$x$$b$$z$$z^T x$$z^T b = z^T A x$

这个错误会不时发布，因此值得提高认识。

一个修复

如果你对这个问题一无所知，那么调整随机分布以使其期望值在所有低能特征向量的方向上具有非零分量是不方便的——你必须解决一个昂贵的特征问题才能找到那些“坏”向量。相反，我会推荐以下临时程序：

1. 递归地平分图。
2. 在二等分树的每一层，从均值非零的随机分布中选择一个随机值。
3. 将向量定义为分配给包含它的所有部分的随机值之和（即，从树根开始的路径之和）。$x$

这很像基于小波的随机采样，并提供所有尺度的相关性。除了稀疏模式之外，它不需要任何关于 SPD 矩阵的特殊知识。

扩展和替代方案

[收集线下讨论的评论。]

• 迈克尔格兰特问“密集系统怎么样？” 我的回答：对于非结构化密集矩阵，我会设置阈值，因为这应该是局部性的某种度量。对于结构化密集矩阵（例如，矩阵），您已经有了层次结构。二等分/分区的细节并不那么重要。它需要做的就是提供不同尺度的相关性，这样分布就不会与有问题的特征向量正交。$H$

• Jack Poulson 建议使用“点源、平面波、波包和高斯随机向量”的组合。 我的回答：平面波和波包需要矩阵本身之外的一些额外知识。点源不适用于异构媒体问题，因为格林的功能可能几乎在所有地方都是局部的，但在非常选择的地方（例如，故障、电线）是全局的。随机点源激活远程耦合的机会很低，但它对实际系统很重要。上面的大部分答案是解释为什么从独立随机分布中提取的向量是不充分的。