跳转至

算法原理概览

这一页用十分钟讲清 hsolve 怎样求特征值、为什么能保证一个不漏。推导细节、参数规则与实测在 方案说明,模块契约在设计文档。

要解的问题

有限元离散后的电磁本征问题是稀疏的厄密特征值问题:

\[ A x = \lambda B x, \qquad A = A^{\mathsf H},\quad B = B^{\mathsf H} \]
类型 形式 典型来源
HEP B = I,A 不定 已做质量矩阵变换的问题;光子晶体的 Bloch 问题(复厄密)
GHEP B 正定 谐振腔(curl-curl 刚度矩阵与质量矩阵)、Yee 网格
GHIEP B 不定 波导模式分析(Lee–Sun–Cendes 棱元-节点元混合公式,λ = −β²)

工程上关心的通常只是一小段谱:目标频率附近的十几个模、某个频段内的全部模,或最低的几个模。对应 hsolve 的 三类目标:σ 附近最近的 k 个、区间 [a, b] 内全部、代数最小或最大的 k 个。矩阵从不被稠密化。

位移反演:把想要的特征值变成最大的

取位移 σ,构造

\[ K(\sigma) = A - \sigma B, \qquad \mathrm{Op} = K(\sigma)^{-1} B, \qquad A x = \lambda B x \iff \mathrm{Op}\,x = \theta x,\quad \theta = \frac{1}{\lambda - \sigma}. \]

离 σ 越近的特征值,|θ| 越大,Krylov 方法对模最大的部分收敛最快。每作用一次 Op 就是一次线性方程组求解, 所以先分解 K(σ)。σ 落在谱内部时 K(σ) 必然不定,不能用 Cholesky;hsolve 用 MUMPS 的对称不定 LDLᵀ 分解 (Bunch–Kaufman 型 1×1 与 2×2 主元)。复厄密的 K 改为分解它的 2n 阶实对称嵌入:

\[ E = \begin{bmatrix} \operatorname{Re} K & -\operatorname{Im} K \\ \operatorname{Im} K & \operatorname{Re} K \end{bmatrix}, \qquad \operatorname{inertia}(K) = \tfrac{1}{2}\operatorname{inertia}(E). \]

一次符号分析服务所有位移:A ∪ B 的上三角并模式只算一次,任意 αA + βB 的值直接写进 MUMPS 的数组,完整的 K(σ) 从不单独存放。三维问题的填充约简排序默认用 hsolve 自研的多线程嵌套剖分(带分隔子的流精修),由确定性的 代价模型在 AMD、SCOTCH、METIS、PORD 等候选中选择。

块 Krylov-Schur:一次回代服务多列

B 正定时 Op 在 B 内积下自伴,用厚重启 Lanczos(厄密 Krylov-Schur),以 B 内积做两遍 Gram-Schmidt 重正交化; B 不定时用一般 Krylov-Schur(实 Schur 形,共轭对不拆开)。两者都以块模式运行:每步对 p 列做一次多右端回代, 一次扫过因子就服务 p 列,而回代受内存带宽限制,p 列的代价远小于 p 次单列回代。块宽 p ∈ {1, 2, 4, 8} 由确定的 规则按问题规模、需求个数和因子大小选出(不做计时探测,结果不随机器负载变化)。重数不超过 p 的特征值一轮就能 取全所有副本。

完备性证书:怎样知道没有漏

迭代法有一个根本的盲点:遇到重特征值(电磁问题中的简并模)时,单个起始向量张成的 Krylov 空间在精确算术下 只含特征子空间的一个方向。求解器可能少给一个副本、用下一个特征值顶替,并照样报告收敛。

B 正定时,Sylvester 惯性定理提供了独立的计数:LDLᵀ 分解中负主元的个数 ν₋(A − sB) 恰好等于小于 s 的特征值 个数。于是对目标窗口 (a, b):

\[ \#\{\lambda_i \in (a, b)\} = \nu_-(A - bB) - \nu_-(A - aB). \]

hsolve 把窗口端点放在谱隙的中点,用这个计数核对「应该有几个」,再用秩揭示的 Rayleigh–Ritz 数出「找到了几个」 互相 B 正交的特征向量(同一个向量算两次只计一次,重复的向量凑不满证书)。两者不等,就以已收敛的向量为收缩块 重跑,直到相等。两数相等时,窗口内的特征值一个不漏——这是可以复核的证明,而不是收敛判据上的推测。

证书的代价是每轮两次额外的分解。hsolve 另有两种更便宜的检验,由 certificate 配置选择:

方法 做法 保证
exact(默认) 窗口两端的双精度 Sylvester 计数 计数精确(假定 LDLᵀ 向后稳定)
randomized 在已有的 σ 处分解上,从高斯起始块做固定步数的块 Lanczos,检查补空间里没有落在半径内的特征值 严格的失败概率上界,默认不超过 1e-12;只在 B 的条件数有证明时下结论
auto 按本次运行实测的分解与回代时间,在能认证的方法中选最便宜的,包括带 10 倍余量的单精度计数 同所选方法

report.json 的 certificate 对象写明最终采用的方法、结论是否严格、失败概率上界和一段文字陈述,见 结果解读与诊断。

不定 B:波导问题

波导的 B 不定,惯性计数不再等于特征值个数,理论上还可能出现复特征值。hsolve 用一般 Krylov-Schur 得到 Op 的 Schur 基,在各次运行的 Schur 基的并上解投影后的小型不定铅笔,一次精修全部候选;按问题尺度与残差双重判据区分真正的 复特征值。节点自由度带来的大维数零空间由单边位移排除:hsolve 数出 A 的零主元得到零空间维数,把位移放在零带两侧, 零空间落在不需要的一侧,从不进入结果。这类问题没有完备性证书,报告中明确写「证书不可用」,而不是给出没有 依据的结论。

谱切片与两端目标

区间目标的端点与所有切点都是同一次分析上的精确惯性计数,所以每一片都知道自己含有几个特征值;每片在中心放位移、 收敛恰好那么多个特征对、单独认证,各片结果去重后合并。计数分不开的簇整体留在一片里。片的大小由代价模型给出, 内存只需放下输出与一片的工作集,特征值个数没有上限。代数最小或最大的 k 个先用惯性搜索确定窗口端点,再在端点 做单边运行。

近奇异位移与稠密簇

σ 恰好落在特征值上时,MUMPS 的零主元检测判定奇异,hsolve 把 σ 微扰一次。σ 落在比检测阈值还密的簇里时,移开 σ 会改变「最近」的集合,hsolve 改为在 σ 处关闭零主元检测直接分解:保留下来的极小主元恰好放大所需的近零空间方向, 相当于逆迭代。证书端点仍放在谱隙中点计数。

验收:真实残差与后向误差

每个返回的特征对都在原问题上重新计算残差,以后向误差验收:

\[ \eta = \frac{\lVert A x - \lambda B x \rVert_2}{\left(\lVert A \rVert_2 + |\lambda|\,\lVert B \rVert_2\right)\lVert x \rVert_2} \le \mathrm{tol}. \]

其中的矩阵 2-范数用 Lanczos 的最大 Ritz 值估计,它是真实范数的下界,因此算出的 η 偏大,验收偏保守。未达标的 特征对做残差修正迭代。全部特征对达标、且证书通过(适用时),success 才为真,命令行退出码为 0。

代价从哪里来

设因子条目数为 L、所需特征对为 k。总时间约为

\[ T \approx T_{\text{analysis}} + \left(1 + 2_{[\text{证书}]}\right) T_{\text{factor}} + N_{\text{solve}}\, T_{\text{solve}} + O(n m^2 \cdot \text{重启次数}), \]

其中分解时间与 k 无关,回代 T_solve = O(L) 且受内存带宽限制(块模式下一次扫过因子服务 p 列)。三维问题里分解占 主导,二维与低填充问题里回代与正交化的比重更大。各阶段的复杂度表见方案说明 §3。

进一步阅读

  • 方案说明:问题与求解边界(§1)、算法原理(§2)、复杂度(§3)、预处理与排序(§4)、收敛性(§5)、 并行方案(§6)、故障场景(§7)、安全设计(§8)。
  • 设计文档:各模块的接口契约与数值约定。
  • 并行方案:多线程、多进程与 GPU 卸载的分工。