跳转至

hsolve 方案说明文档

面向电磁谐振与微波器件仿真的大规模非正定厄密稀疏矩阵特征值求解方案 (交付物 a;版本:方法、求解边界与 §6、§9.1 的实测按 P9 集成(分支 p9int:main c822126 + P9 的自研嵌套剖分、 MUMPS 块参数与自编 MUMPS 作默认构建)的代码;§9.2 起为更早阶段的记录。实现细节契约见 docs/DESIGN.md, 最终实测见 results/p9_measurements.md,各阶段实测见 results/p*_*.md,SLEPc 调优与公平对比见 results/baseline_tuning.md、results/baseline_tuning_p16.md、results/cmp-p9-1e6-profiles.json)


1. 问题、目标与求解边界

1.1 问题类型

类型 形式 电磁背景
HEP A x = λ x,A 厄密不定 已做质量矩阵变换的本征问题;光子晶体 Bloch 问题(复厄密)
GHEP A x = λ B x,B 厄密正定 谐振腔(curl-curl 刚度 / 质量),Yee 网格
GHIEP A x = λ B x,B 厄密不定 波导模式分析(Lee–Sun–Cendes 棱元-节点元混合公式,λ = −β²)

例如 10 mm 方波导在 50 GHz 下,广义谱的 18 个负特征值正是 18 个传播模(TE 12 个 + TM 6 个),零特征值是 节点自由度对应的非物理零空间。

求解目标:σ 附近最近的 k 个(默认)、区间 [a, b] 内全部、代数最小 / 最大的 k 个。 接口:命令行 hsolve(npz/npy/mtx 文件进,npy 出)与进程内 Python 接口 hsolve.solve(scipy 稀疏 / numpy 矩阵进,numpy 出,docs/PYTHON.md),二者走同一条求解路径、同一份配置格式。

1.2 求解边界(能处理 / 不能处理)

能处理 说明
实对称、复厄密(A、B 任一为复数) 复厄密经实对称嵌入统一走 LDLᵀ
A 不定;B 正定或不定 B 正定性自动判定,先免分解:对角 B 看符号;O(nnz) 筛查(严格对角占优且对角为正即正定、有对角元 ≤ 0 即不定);B 的范数估计 Lanczos 出现负 Ritz 值即不定(波导的 B 由此判定);其余先试不完全 Cholesky + Gershgorin 的严格正定证明(带舍入界,预算为一次 B 分解的一半),仍未定才分解 B 读 Sylvester 惯性
σ 位于谱内部、贴近特征值、精确落在特征值上、落在稠密簇内 见 §2.5
精确重特征值、零附近密集谱 惯性证书 + 收缩重跑(B 正定时可证明完备);零模可用 zero_filter_tol 按惯性切除(§2.7)
区间内任意多个特征值 谱切片(§2.7),每片单独认证;只受内存预算限制(n×m 输出须放得下),无个数上限
代数最小 / 最大 k 个(B 正定或 B = I) 惯性搜索定窗口 + 单边位移(§2.7)
GHIEP 的零空间(波导节点自由度) 单边位移放置,零簇从不进入结果(§2.7)
分解内存超预算 预估后自动转 out-of-core;仍超则拒绝并报告估计值,绝不盲目分解;块 Krylov 的基放不下时块宽自动减半
百万阶 GHIEP 后处理只留 Schur 基、分块投影、精修前释放分解:wg-square-1e6 峰值 2.89 → 1.77 GB(§2.4)
不能处理 / 有条件 处理方式
非厄密矩阵(如复对称 PML) 输入检查直接拒绝(NotHermitian),不给错误答案
GHIEP 的完备性证明 Sylvester 惯性对不定 B 不计数,报告中明确注明「证书不可用」
GHIEP 的区间 / 代数最小最大目标 同理需要计数,拒绝(Unsupported);GHIEP 只支持 σ 附近最近 k 个
GHIEP 中把精确多重的零簇本身作为目标 单向量 Krylov 无法保证取全副本;由单边位移放置排除,零簇不被需要(§2.7)
内存不足以放下双精度因子 单精度 / BLR 需显式配置(带迭代修正);JD + 单精度因子的回退已实测、尚未接入 driver(§2.8)

2. 算法原理

2.1 位移反演 + Krylov-Schur(主路径)

K(σ) = A − σB,Op = K⁻¹B,A x = λBx ⇔ Op x = θx,θ = 1/(λ−σ):离 σ 最近的特征值变为模最大, Krylov 方法对模最大部分收敛最快。B 正定时 Op 在 B 内积下自伴,用厚重启 Lanczos(厄密 Krylov-Schur), 全 CGS2 重正交化(B 内积,按需重算 B·w,不存 B·V 以省内存;DGKS 判据在第一遍已足够时跳过第二遍), 已收敛对在耦合降到工作精度时锁定。正交化与内积核手写、在固定行块上归约,任意线程数下逐位相同。 B 不定时用一般 Krylov-Schur(实 Schur 形 + dtrsen 重排,共轭对永不拆开)。

两种 Krylov-Schur 都以块模式运行(P4 起为默认):每步一次 p 列的多右端回代——一次扫过因子服务 p 列,回代占一次算子作用的 80–100%,p = 16 时每列代价只有 p = 1 的 1/4–1/9(4 线程,六个 1e5 测例)。 块宽按确定的规则选(不做计时探测,结果不随机器负载变化):HEP/GHEP 的 nearest 运行由块宽规则(P5c)在 p ∈ {1, 2, 4, 8} 中选——在 16 线程下标定的每步代价模型(p 列回代按 σ 处分解的因子条目与规模,加块正交化) 乘实测的块步数比,取最小者,需求 ≥ 8 对时至少 4(重特征值在运行前看不见,而它们让更宽的块划算);从 4 加宽到 8 须有 10% 的模型收益(模型在没有 BLAS hook 时标定,hook 让窄块回代更便宜),且只在因子留出的内存 放得下其基时才用(分析前只预留 p = 4 的基,分解优先);切片与 单边运行需求 ≥ 8 对时 p = 4,否则 1;GHIEP n ≥ 2e4 且需求 ≥ 4 对的运行 p = 2,否则 1(零簇旁的单边运行每块都会 带回 p 个零簇方向,p = 4 最多慢 1.5 倍)。重数 ≤ p 的特征值一轮取全副本。块步的正交化先试单投影快路径 (行块化块 CGS + 块内两次 Cholesky-QR),病态的块与 deflation 块旁的步才用两遍核。

2.2 对称不定分解与复厄密实嵌入

现有工具卡在「只能处理正定矩阵」——本质是用了 Cholesky。K(σ) 在谱内部必然不定,我们用 MUMPS 的对称不定 LDLᵀ(Bunch–Kaufman 型 2×2 主元)。MUMPS 的复数 SYM=2 是复对称而非厄密,因此复厄密 K 改为分解其实对称嵌入 E = [[Re K, −Im K],[Im K, Re K]](2n 阶):求解 E[Re x; Im x] = [Re b; Im b],且 inertia(K) = inertia(E)/2; 浮点运算量与内存与复数 LU 相当,同时得到惯性。

一个分析服务所有分解:ShiftedPencil 只存 A ∪ B 的上三角并模式索引(另加每行 1 字节),αA+βB 的值 逐行归并、直接写入 MUMPS 数组,任意位移 K(σ)、B 本身、A 本身、证书端点与切片计数都复用同一次符号 分析,完整 K 从不物化(n = 1e6 波导:铅笔 33 MB,P2 带散射映射时 112 MB)。

数值分解的吞吐(P9,results/p9_factspeed.md):1e6 三维测例在 16 核内存内时,整次运行是同一主元顺序上的 三次数值 LDLᵀ(σ 处的主分解与证书的两次只计惯性分解)。剖析表明一次分解只达到槽内 DGEMM 峰值的 40–43%,受 socket 的内存带宽限制(4 → 16 线程只快 1.84 倍):L0 子树层占 27–29% 时间而只有 13–14% flops,其上完全求和部分 的尾随更新是秩 128 的 dgemm(350 GFlop/s,对秩 ≥ 512 的 585–620)。因此 hsolve 给 MUMPS 更宽的块参数——满秩面板宽 KEEP(420) = 256、贡献块更新的行块 KEEP(58/57) = 2000/4000,以及我们给 MUMPS 打的补丁 (patches/mumps-5.8.2-l0-blocking.patch)在 L0 层下另用的面板宽与条带 KEEP(498/499) = 128/64——只改分块、不改 选主元与运算,惯性计数与默认参数下逐个相同(单元测试按已知装配树断言各条路径)。每次分解快 5–6%,加补丁后一次 计数 1.073–1.079 倍。P9 集成起默认构建由仓库内的 MUMPS 5.8.2 官方源码包(third_party/mumps/,CeCILL-C)打上 该补丁编译(可移植编译选项,构建一次后缓存复用),命令行与 Python 模块都链接它;HS_MUMPS=env 改用环境的 conda-forge MUMPS,运行时 HS_MUMPS_BLOCKING=mumps 恢复 MUMPS 自己的块参数。实测为负、未采用:线程绑定与等待策略、 关透明大页、移动或关掉 L0 层、更多合并、-O3 / AVX2 / AVX-512 重编 MUMPS(1.000–1.005 倍且不可移植)、GEMMT。

2.3 完备性证书(「不漏根」)

B 正定时,Sylvester 惯性定理给出 ν₋(A − sB) = 小于 s 的特征值个数(LDLᵀ 负主元数)。对目标窗口 [a, b] (Nearest:a ≤ σ−r、b ≥ σ+r,r 为找到的 k 个中最远距离,端点推到谱隙中点;Smallest/Largest 单侧; Interval 为用户区间):

count_inertia = ν₋(A − bB) − ν₋(A − aB),与找到的互相 B 正交的特征向量数比较。

不等则以已收敛向量为收缩块重跑,直到相等——结果是可证明完整的。「找到的个数」由秩揭示的 Rayleigh–Ritz (丢弃 B-Gram 矩阵中的相关方向)得出,同一向量算两次也只算一个,重复向量不可能凑满证书。实测(§9)对照组 SLEPc 在 3/15 个测例上漏掉重特征值副本而无任何告警,hsolve 全部正确。 代价:每轮证书两次计数分解(certificate = exact,默认)。P4 起在三维填充的测例上由只计惯性、复用主元 顺序的 InertiaCounter 计数(代价模型判定划算时;计数前释放主因子,两者从不同时驻留):4 线程实测比在主 分解对象上计数省 5–13% 的证书时间、峰值内存低 2–7%。但 P4 时证书仍占真实三维 1e5 测例总时间的 30–40% (1.2–2.0 s),是 hsolve 在这些测例上慢于 SLEPc 的主因(§9)——下面更便宜的检验即为此而来。

更便宜的完备性检验(src/verify,P5 接入 driver,配置 certificate = exact | randomized | auto | off): - 随机排除检验(randomized):在已持有的 σ 处分解上,以已找到的向量作收缩、从高斯起始块做固定步数的块 Lanczos,若补空间上没有 |θ| ≥ 1/r' 的 Ritz 值即通过;由 Weyl 不等式、Chebyshev 多项式界与高斯起始分量的 Beta 分布得到严格的失败概率上界(默认 ≤ 1e-12,步数在运行前由该上界确定)。只在 B 的条件数有证明时 (B = I、对角、对角占优)运行;一般 B 的条件数只能估计,通过只是筛查结果——此时改由精确计数出证书, 筛查结果从不作为结论报告。不能下结论(谱隙太窄、计划超出内存预算)时也改用精确计数。 - 单精度计数(exact_single):B = I 或对角 B 时,单精度 LDLᵀ 计数是被 O(c·g·u_s·‖K‖₁) 扰动矩阵的精确 惯性,端点离每个已找到的特征值都超过该扰动时可认证。唯一的假设是单精度分解的后向误差界 c·g(MUMPS 阈值 选主没有先验增长界),一次实测违反了默认值 1e3(误数处至少 2.96e3),因此 driver 要求 10 倍余量,计数多于 找到数或与 σ 处的精确计数矛盾时先用双精度复核。 - auto:用本次运行实测的分解与回代时间预测三种方法的代价,选能认证且最便宜者(随机检验须快 1.2 倍)。 16 线程实测中它在分解贵且谱隙宽的三维测例上选随机检验(syn-mem27-46、syn-mem125-46、yee-pec-cube-32), 在 yee-pec-cube-16 上选单精度计数,窄谱隙(yee-pec-box-1e5)与廉价分解上保留精确计数。 任何检验发现缺对都触发收缩重跑;选中的对少于 k 时,即使检验通过也重跑(检验只覆盖已找到的对)。报告写明 最终方法、是否严格、失败概率与文字陈述。区间与两端目标的计数点就是切点与位移,总是精确计数。

2.4 不定 B(GHIEP)

一般 Krylov-Schur 得到 Op 的 Schur 基(实数时为实向量,与 Ritz 向量同张成;近实的共轭对——如零簇的 ±1e-16i 噪声对——由此还原成实向量);各次运行的 Schur 基取并集、正交化,在其上解投影后的小型不定铅笔 (LU + Schur),一次精修全部候选。

内存与速度(P4):Ritz 向量当即丢弃,只留 Schur 基;投影矩阵 WᴴAW、WᴴBW 按 8 列一块形成(不物化 n×m 的 AW、BW);候选 4 个一批精修、以系数保存,结果向量只为选中的对形成;精修前释放分解。wg-square-1e6 (n ≈ 1e6,2 线程,排序固定为 SCOTCH)峰值内存 2886 → 1766 MB,后处理 3.50 → 1.29 s;加上块运行 (p = 2)总时间 37.2 → 25.0 s(2 次运行)。 wg-square-1e5 2.33 → 1.84 s,wg-halfslab-1e5 3.49 → 2.58 s(同一会话交错,中位数)。 实/复分类按问题尺度与残差双重判据:|Im λ| > complex_tol·max(|λ|, scale) 且 实投影对的后向误差不达标而 复对达标,才判为真复特征值,单独输出(不影响实特征对的格式)。

2.5 近奇异与稠密簇位移

  • σ 精确落在特征值上:MUMPS 零主元检测(ICNTL(24)=1 且 CNTL(3)>0——实测 CNTL(3)=0 时 3600 阶精确奇异矩阵 也会「成功」分解)判定奇异 → σ 微扰 1e-8·max(scale, |σ|),只一次(孤立特征值此时已在检测阈值之外 约 1e3 倍)。
  • σ 落在比检测阈值更密的簇内(σ 处的零主元多于一个特征值的份,或扰动后的位移仍被判奇异):移开 σ 会改变 「最近」的集合,因此在 σ 处关闭零主元检测直接分解(P5c 起先看零主元数:扰动后的位移是否被判奇异取决于 主元顺序,METIS / SCOTCH / 自研嵌套剖分的因子曾漏判,使位移移出簇外、证书次次重跑)——保留的极小主元恰好 放大所需的近零空间方向(等价逆迭代)。证书端点在同一谱隙中点先做有检测的计数,失败再做无检测计数 (向后稳定的 LDLᵀ 对距端点 ≫ eps·‖K‖ 的特征值计数精确)。
  • 实测:σ=0 落在 1000 个间距 1e-9 的零簇中心,取最近 20 个,绝对误差 ~1e-17,证书通过(§9)。P2 在微扰 一次失败后还会再做一次 10 倍扰动,在 syn-zero-cluster-real-1e5 上把位移推到所需半径的 5 倍处(证书数出 166 个、 找到 21 个,再做 147 对的收缩重跑);改为一次扰动后直接回退到簇内无检测分解:32.9 s、10 次分解、549 次回代 → 2.6–3.5 s、6 次分解、65 次回代,对精确参考误差 8.7e-17。

2.6 精修、验证与补救

HEP/GHEP 在原问题上做秩揭示的 Rayleigh–Ritz(B-Gram 特征分解后在剩余的 B-正交基上解投影铅笔),GHIEP 用 §2.4 的投影铅笔。每个特征对计算真实残差 ‖Ax − λBx‖₂、相对残差与后向误差 η(§5.2)。不达标者做残差修正迭代 x ← x − K̃⁻¹(A − ρB)x(ρ 为 Rayleigh 商;对任意近似分解 K̃ 其不动点都是精确特征对)。

2.7 谱切片与单边目标(区间、代数最小 / 最大、零模排除)

  • 谱切片(区间目标,B 正定或 B = I):窗口端点与所有切点都是同一次分析上的精确 Sylvester 计数,每片 因此知道自己含几个特征值;每片在中心放位移、收敛恰好该数目个特征对、单独认证(缺则收缩重跑),各片结果 按 B-Gram 秩去重后合并,全局证书逐窗口核对。切点由计数插值(带 Illinois 修正的试位法)找到;计数分不开 的簇(重特征值)整体留在一片内,切点放在旁边谱隙的中点。片大小由代价模型(分解、回代、基正交化的 时间,在本机标定)给出,可用 slice_size 覆盖;内存只需容纳 n×m 输出和一片的工作集,特征值个数没有 上限(P2 的上限 max(2000, n/2) 已取消)。实测(2 线程,对精确参考):yee-pec-box-1e4 区间 [1000, 2000] 内 1075 个(每个二重):单位移 49.8 s / 0.89 GiB → 自动 19 片 11.1 s / 0.20 GiB,最大相对误差 2.2e-15; yee-pec-box-1e5 区间内 499 个:单位移 213 s,片大小 64 / 128 时 155 / 150 s。
  • 单边位移:谱端的片(片外一侧没有特征值)或紧邻零带的片不用中心位移,而在片端放位移、只求一侧 (SmallestAlgebraic:位移以下;LargestAlgebraic:以上),并直接复用该端点计数时的分解。
  • 代数最小 / 最大 k 个:窗口 (−∞, U] / [L, +∞) 的端点由惯性搜索确定(以谱两端的 Ritz 估计为种子, 多算几对比再做一次计数便宜时停止细化),再在端点做单边运行;B 正定的广义问题也适用(P2 为 Unsupported)。 实测:ss-qa8fk-qa8fm(GHEP)最小 10 个 11.0 s、最大 10 个 14.4 s,证书通过;syn-lap3d-aniso-1e5 最小 10 个 10.8 s(P2 的「在谱端外 5% 处求最近 k 个」为 17.8 s)。
  • 零模排除(zero_filter_tol):HEP/GHEP 在 ±zero_filter_tol·scale 两点计数,把零带从窗口中切掉, 过滤与计数精确一致(被排除的个数由惯性给出);σ 附近最近 k 个的目标若被零带干扰,改为窗口 [σ − r, σ + r] 减零带求解。实测 yee-pec-box-1e4(curl-curl,梯度零空间 3135 维)σ = 1、k = 6:改进前只返回 1 个,现在 6/6 精确、证书 6/6、0.88 s;最小 20 个(零带 1e-6)0.9 s,精确。
  • GHIEP 零簇(波导 A = blkdiag(A_tt, 0) 的零空间,zero_filter_tol 不设也排除):σ 附近的普通运行若被 零簇干扰,就数 A 的零主元得出零簇维数,改在零带两侧各放一个单边位移,零簇落在不需要的一端;位移放在 零簇与该侧第一个特征值的中点(由一次 2 对的探测运行找到),贴着零带边缘时残差会停在 1e-10..1e-9。两侧 位移之间的复特征值另做恢复运行。实测 wg-square-1e5(零空间 24649 维):σ = 1e-4、k = 10 时 P2 返回 10 个 零,现在返回 10 个最近的非零模,η ≤ 1e-15,7.7 s;σ = −0.5、k = 22 时 P2 为 18 个模 + 4 个零,现在 22 个模(18 个传播模 + 4 个消逝模),8.0 s。

2.8 核心算法组件:Krylov-Schur、Lanczos(含块模式)、LOBPCG、Jacobi-Davidson

四个求解器都是独立的公共模块(include/hsolve/eigen.hpp、eigen_iterative.hpp),只依赖线性算子接口 (任意 LinearOperator:位移反演、矩阵乘、用户预条件子),共享结果契约(前 nconv 个已收敛、按目标排序), 可脱离 driver 单独调用(交付物 c)。driver 当前使用的是前两者,后两者的定位按实测给出: - 厚重启 Lanczos / 厄密 Krylov-Schur(主路径)与一般 Krylov-Schur(GHIEP)。 - 块 Krylov-Schur(block_size = p,两种求解器都有):每步一次 p 列多右端回代,新块先对基做块 Gram-Schmidt、块内做 Cholesky-QR,病态或相关的块交给两遍核并以随机向量替换相关列;在块边界也检查收敛, 因此块运行恰好达到容差。重数 ≤ p 的特征值一轮取全副本。P4 起 driver 默认使用(P5c 起为 §2.1 的块宽 规则),P4 规则的依据为 端到端测量(4 线程,30 个 HEP/GHEP 测例,p = 1/4/8):三维 1e5 测例迭代阶段快 1.4–2.5 倍,重特征值测例 总时间快 1.4–2.2 倍(证书不再需要收缩重跑),k = 6、7 的测例块更慢(故需求 < 8 对时 p = 1);32 个测例 合计 97.2 → 80.0 s。GHIEP 上 p = 2 在九个测例上从未慢于 p = 1(1.06–1.58 倍)。 - Jacobi-Davidson(目标跟踪、Ritz / 调和提取、柔性 GMRES 或 MINRES 内迭代、收缩):收敛按后向误差, 残差始终用双精度精确计算,因此单精度因子作预条件子即可得到双精度特征对。实测(k = 12):约为双精度 位移反演 Lanczos 的 1.5 倍时间、一半因子内存;在位移距 6 重特征值仅 9.5e-9 / 2.5e-11、单精度迭代修正发散 (双精度因子甚至奇异)时仍全部正确。定位:内存受限时的回退路径(取代现在的「单精度因子 + 迭代修正」, 后者在 syn-mem27-46 上 5 次中 2 次不达标),尚未接入 driver。JD 可能漏掉重特征值的某个副本而自报收敛, 因此必须与惯性证书和收缩重跑一起使用。 - LOBPCG(软锁定、稳健基):代数最小 / 最大的 k 个,完全不需要分解(或用单精度因子作预条件)。实测 syn-mem27-46 最小 12 个:无预条件 15.1 s / 0.16 GiB,单精度因子预条件 8.7 s / 0.54 GiB,对照双精度 位移反演 Lanczos 12.7 s / 0.69 GiB。定位:极低内存预算下的两端目标,尚未接入 driver。


3. 复杂度分析

设 n 为阶数,Z = nnz(K),L 为因子条目数,k 为目标个数,m(ncv)≈ 2k+1 为子空间维数。

阶段 时间 内存
排序 + 符号分析 AMD ≈ O(Z),嵌套剖分 ≈ O(Z log n) O(Z)
数值分解 二维 O(n^{1.5}),三维 O(n²)(嵌套剖分) L:二维 O(n log n),三维 O(n^{4/3})
每次 Op 作用(回代) O(L),访存受限;p 列块回代仍只扫一遍因子 —
每步正交化(CGS2,DGKS 时一遍;块模式为 BLAS3 块 CGS) O(n·m),访存受限 基 n·m(块模式 n·(m + p))
每次重启 O(n·m·k) BLAS3 —
证书 exact:2 次数值分解(复用分析;三维时用只计惯性的 InertiaCounter,便宜 10–23%);randomized:s 步 p 列回代(无分解),s ~ log(Nκ/δ)/√ε 计数前释放主因子,只占计数的工作内存;随机检验的基受内存预算限制
谱切片(每片 c 个) 每片约 2.2 次分解(位移 + 定下一切点的计数),每对约 2.1 + 33/c 次回代 输出 n·m + 一片工作集约 7·c·n

总时间 T ≈ T_analysis + (1 + 2[证书] + 1[需分解的 B 正定性检测])·T_factor + N_solve·T_solve + O(n m² · 重启数), 单向量时实测 N_solve ≈ 3k。块模式下 N_solve 是 p 列回代的次数,每次的代价远小于 p 次单列回代(p = 4 时 每列约 1/3,p = 16 时约 1/4–1/9),而总作用列数增加(不同特征值时 p = 4 约为 p = 1 的 2 倍)。k 增大时 T_solve 部分线性增长,T_factor 与 k 无关。


4. 预处理策略

  1. 输入归一:npz/npy/mtx 读入后合并重复项、恢复三角存储、厄密性检查;缺陷在容差内则替换为 (A+Aᴴ)/2, 保证分解(只读一个三角)、算子与残差看到同一矩阵。读入不经三元组副本:csr 原地规范化,coo/csc 分块流入 并直接放进 CSR 槽位,MatrixMarket 读两遍;峰值为结果的 1.0×(csr)到 1.8×(结构不对称输入取厄密部分), P2 为 2.0–3.0×。
  2. 铅笔并模式:一次计算 A ∪ B 上三角并模式(只存索引),所有位移共用,赋值时逐行归并(§2.2)。
  3. 自适应排序(ordering=-1):先做极快的 AMD 分析探测,再按代价模型把每个候选排序——AMD、自研并行 嵌套剖分、SCOTCH、METIS、PORD(得分相近时按此顺序优先)——在本次运行计划的工作(分解、证书计数、块回代的 次数,由配置与问题类型推导)上定价,分析最有希望者、以其实际估计替换预测,直到最优者已分析(P5c)。模型的 常数在评测配置(16 线程)下对 40 个 n ≤ 1e5 数据测例与两个 1e6 三维测例拟合(P9 按新的嵌套剖分重拟合),可由 测量程序复算;用 driver 自己的代码重放选择时相对最佳排序的平均超额为 1.1%(样本内与留一测例都是;P5c 的 模型 4.3% / 5.0%),38 个测例合计 205.35 s 对最佳的 205.31 s:三维测例上最好的都是自研嵌套剖分、二维的是 AMD。 模型完全确定:不用实测耗时(同一输入实测相差 3 倍,P3 时曾使两次相同运行选了不同排序),SCOTCH 因排序逐次 不同(1e6 时 flops 相差 1.3–1.6 倍)而「按预测采纳」、不拿其估计比较——相同运行选相同排序。要求逐位复现时只在 AMD 与固定种子的 METIS 之间选(P4 规则)。 自研并行嵌套剖分(P4 实现于 factor 层,P5c 起为排序候选,P9 起为三维问题的首选,也可 ordering = 10 直接指定):MUMPS 内的排序是串行的,占三维测例分析的 90–97%;我们实现了 METIS 式的多级顶点分隔子排序,两半与 试分作为 OpenMP 任务并行(P9 修正了关键路径上连带等待兄弟子树的 taskwait:1e6 图 16 线程 7.4 → 2.4 s),大图的 收缩与切分用 taskloop 并发,随机数按子图播种,排列与线程数无关,以 PERM_IN 交给 MUMPS。P9 的两项改进 (results/p9_ordering.md):图压缩——闭邻域相同的顶点合成带权顶点(叶子按权判定),ss-tem152078 排序 0.70 → 0.26 s;分隔子的流精修——FM 在网格上停在局部极小,在分隔子两侧各 2 层的带内求最小顶点割(拆点网络上 的 Dinic 最大流)找到平面分隔子:yee-pec-box-1e6 的 MUMPS flops 7.39e12 → 5.43e12(SCOTCH 6.75–7.09e12,坐标 几何剖分 5.29e12),19 个测例几何平均 −10%。流精修的规则:小问题上 flops 的下降不带来时间的下降 (yee-pec-cube-16:flops −17% 而整次运行 +9%),所以 driver 只在计划的数值时间 ≥ 4.5 倍预测排序时间时做流精修, ≥ 30 倍时顶 2 级再多做试分(ss-ge87h76 flops −12%)。16 线程 1e6 时排序 2.0–2.4 s(SCOTCH 整个分析 4.3–6.3 s、 METIS 13–14 s,都是串行),因子 flops 为 SCOTCH 中位运行的 0.76 / 0.77 倍,三次分解省 18.5 s / 14.4 s。
  4. 缩放:MUMPS ICNTL(8)=7,每次分解按当前数值重算,使同一分析适用于不同位移。
  5. 谱变换:位移反演(§2.1);B 正定性判定(§1.2:对角 B、对角占优或有非正对角元、范数估计 Lanczos 的 负 Ritz 值都免分解;其余先试严格的不完全 Cholesky 证明,最后才分解 B)。

5. 收敛性分析

5.1 收敛速度

位移反演 Krylov-Schur 对第 i 个目标的收敛因子约为 |θ_{k+1}|/|θ_i| = |λ_i − σ|/|λ_{k+1} − σ|(λ_{k+1} 为第一个 不需要的特征值)。σ 置于目标频段中心使该比值最小;k 个目标与第 k+1 个之间的谱隙越大收敛越快。

5.2 停止判据与后向误差

内层判据:Ritz 估计 ≤ tol_in·|θ|(tol_in = 0.1·tol)。由 (A−λB)x = −(1/θ)(A−σB)(Op x − θx) 得 ‖(A−λB)x‖ ≤ ‖K‖·est/|θ|,故后向误差 η = ‖r‖/((‖A‖₂ + |λ|‖B‖₂)‖x‖) ≲ tol_in。最终以真实残差验收 η ≤ tol。 ‖·‖₂ 取 30 步 Lanczos 的最大 |Ritz 值|——它是 ‖·‖₂ 的下界,因此计算出的 η 是真实后向误差的上界, 验收偏保守(1-范数是上界,会使 η 偏乐观,故不用)。

5.3 停滞处置

达到 max_restarts 仍未收敛的对标记为未接受;证书不通过触发收缩重跑(最近 k 个:最多 2 轮,每轮求缺数 + 2 对、缺的那几个最近的对收敛即结束——多要的对可能落在宽于容差的簇里永不收敛,yee-pec-box-1e5 上重跑的第三个 对是 curl-curl 零空间的向量,不设此停止条件时重跑跑满 1000 次重启;切片:只要还在 找到新对就继续,至多缺数 + 4 轮,连续 2 轮无新对即停;缺的是重特征值的副本时,重跑位移放在离它 1% 谱隙处, 让该重根主导算子);残差不达标触发残差修正迭代;所有事件写入日志与报告。


6. 并行方案

多线程 / MPI / GPU 三层的分工与实测如下,无 GPU 时同样可复现(证书均为 exact,每次运行经 tools/eval 判定有效;细节见下文与 docs/PARALLEL.md、results/p9_measurements.md、results/p10_mpi.md、 results/p10_gpu.md):

层 负责的计算 实测加速比(16 核) 何时启用
多线程(OpenMP,进程内) 全部数值计算:排序(自研并行嵌套剖分)、MUMPS 分解与回代(L0 子树 + 多线程 BLAS + BLAS hook)、稀疏核、正交化 1 → 16 线程:1e5 三维 3.6–4.5 倍(对最快的 1 线程配置;同一主元顺序 4.3–5.1 倍),二维 2.7 倍;1e6 三维 4 → 16 线程 1.82 倍;受一个 socket 的内存带宽限制 总是(默认)
多进程(MPI;启动器 hsolve-mpirun 运行 MPI 程序 hsolve-mpi) 每个 socket 一个 helper 进程:nearest 证书的两次 Sylvester 计数同时做、窗口目标的谱切片;leader 占全部核做主分解与 Krylov 两 socket(8 + 8 核)对单进程:1e6 nearest 1.09–1.11 倍,1e5 三维 nearest 1.10–1.20 倍,多片窗口 1.50–1.74 倍;单 socket 0.86–0.93 倍,故单 socket 时启动脚本直接运行单进程 hsolve 多 socket 机器可选
GPU(--gpu auto\|on,一张卡) 1e6 分解(含证书计数)中 L0 层之上的大 dgemm(贡献块更新,k ≥ ~1000),FP64 cuBLAS,运行时加载 1e6 三维:三次分解 1.07–1.09 倍(配 P9 块参数 1.08–1.10 倍),整次运行 1.058–1.069 倍;1e5 无值得卸载的调用(强制 on 0.72–0.97 倍) 有 GPU 且分解估计 ≥ 3e12 flops 时 auto;默认 off
降级 没有 MPI、没有 GPU:单进程 CPU 路径即默认路径,结果相同 — 无 GPU、无 MPI 的机器
组件 并行方式
MUMPS 分解 / 回代 OpenMP + L0-OpenMP 子树并行(ICNTL(48)=1;比确定性模式回代快 1.75 倍):L0 层以下每棵子树一个线程,其上的大前沿由多线程 BLAS 处理;P9 的块参数与补丁让大前沿的尾随更新用更宽的面板(§2.2);块 Krylov 的多右端回代一次扫过因子服务 p 列;顺序版 MUMPS 实例间非线程安全,进程内所有 MUMPS 调用串行
填充约简排序 MUMPS 内串行;自研嵌套剖分以 OpenMP 任务并行(分隔子的两半与试分为任务、taskgroup 等待,大图的收缩与切分用 taskloop;排列与线程数无关):1e6 图 16 线程排序 2.0–2.4 s,SCOTCH 串行分析 4.3–6.3 s(§4)
正交化、内积 手写 CGS2 核(融合扫描、DGKS),OpenMP 固定行块归约,任意线程数逐位相同
稠密核(Rayleigh–Ritz、重启旋转、块 CGS2) OpenBLAS(OpenMP 版)BLAS3
MUMPS 回代中的窄 BLAS(P5) BLAS hook(默认链入 hsolve):L0 层之上的大调用按固定块并行切分、长 Gram 积按 K 切分、窄 dgemm 用 AVX-512 / AVX2 窄核(运行时按 CPUID 选择),其余原样交给 OpenBLAS;固定线程数时结果确定,在 MUMPS 的并行区内串行、不超订(docs/BLAS.md)
稀疏核(SpMV/SpMM、融合修正残差、铅笔装配、输入转换) OpenMP 行并行,每行固定由一个线程按固定顺序计算(结果与线程数无关);多向量时交错存放、每遍服务 16 个向量;运行时检测 AVX-512(每行 ≥ 8 个 double 的块用 intrinsics,否则按块宽编译的可移植向量核),无 AVX-512 的 CPU 自动回退

多线程加速比实测(P9 集成构建,gpu01 测量槽:一个 16 核 socket,T 线程的运行绑在槽的前 T 个核上、整个槽 独占,证书 exact,T 与配置交错、5 次取中位数,360 次运行都经 tools/eval 判定有效;tools/bench/thread_scaling.py, results/p9_measurements.md §5)。默认配置的自适应排序按线程数定价,1 线程时可能选与 16 线程不同的排序,所以给出 两种加速比,都不拿较慢的串行配置作基线:(1) 对最快的 1 线程配置——默认配置在 T 线程的时间对 1 线程下实测的六种 配置(默认,以及固定为 AMD、自研嵌套剖分、SCOTCH、METIS、PORD)中最快者;(2) 同一主元顺序——16 线程运行所用 的排序固定于每个 T(因子条目在各 T 相同),即同一计算的并行加速比,分阶段加速比在此口径下取。求解器时间(s):

测例 最快的 1 线程配置 默认 1 线程(所选排序) 2 4 8 16 线程 16 线程对最快 1 线程 并行效率 同一主元顺序 1 → 16 线程
syn-mem27-46(三维 HEP,n ≈ 1e5) METIS 9.06 11.01(SCOTCH) 5.58 3.38 2.33 2.01 4.51× 0.28 自研嵌套剖分 9.78 → 1.92,5.09×
yee-pec-box-1e5(三维 GHEP,Yee 棱元) 自研嵌套剖分 10.52 10.58(自研嵌套剖分) 6.14 3.76 2.72 2.49 4.23× 0.26 即默认,4.26×
ss-qa8fk-qa8fm(三维 GHEP,声学) PORD 5.51 6.97(SCOTCH) 3.34 2.13 1.61 1.54 3.57× 0.22 自研嵌套剖分 6.25 → 1.42,4.40×
syn-near-singular-complex-1e5(复厄密 HEP) AMD 4.99 5.02(AMD) 4.21 3.44 2.71 2.22 2.25× 0.14 自研嵌套剖分 5.41 → 1.92,2.82×
wg-square-1e5(二维 GHIEP,波导) AMD 1.42(即默认) 1.42(AMD) 1.02 0.72 0.55 0.52 2.71× 0.17 即默认,2.71×
cav2d-rect-pert-1e5(二维 GHEP) AMD 0.91 0.91(AMD) 0.74 0.57 0.42 0.34 2.65× 0.17 即默认,2.66×
yee-pec-box-1e6(三维 GHEP,n ≈ 1e6;3 次) 未筛选 – – 125.65(4 线程) 85.36 69.16 1.82×(对 4 线程) 0.45(对 4 线程) 即默认(自研嵌套剖分),1.82×(4 → 16)

分阶段(同一主元顺序,1 → 16 线程,三个三维测例):自研嵌套剖分的排序与分析快 5.3–5.8 倍,数值分解 4.1–6.7 倍, 证书的计数分解 4.4–5.4 倍,块回代只快 2.6–3.3 倍(受内存带宽限制:三维 1e5 测例 8 → 16 线程回代不再变快), 正交化与重启 3.8–5.2 倍;1 → 2 线程 1.72–1.91 倍(效率 0.86–0.95)。二维与低填充测例(AMD 排序,串行分析)在 16 线程 只到 2.65–2.71 倍;规模越大扩展越好(1e6 三维测例 4 → 16 线程快 1.82 倍:分解 1.89 倍、计数 1.99 倍、回代只有 1.20 倍, 4/8/16 线程同一主元顺序);一个 socket 的内存带宽是上限(P9 factspeed:一次 1e6 分解 4 → 16 线程只快 1.84 倍)。 默认配置在 16 线程比固定的自研嵌套剖分慢 0.09–0.30 s(三个测例;差额主要在分解一栏,即自适应排序的 AMD 探测,见 DESIGN 的 P9 未做项)。 已知偏差(评审发现,不在评测配置内):排序代价模型只在 16 线程标定,1 线程时在 syn-mem27-46 与 ss-qa8fk-qa8fm 上选 SCOTCH,而 METIS / PORD 分别快 1.21 / 1.27 倍、自研嵌套剖分快 1.13 / 1.12 倍(其余四例所选即最快,差 ≤ 1%); P9 集成初稿以默认配置自己的 1 线程运行作基线,报告的 5.39× / 4.55× 与分析 7.90× / 8.31× 因此把较慢的串行排序算进了 并行加速比,已按上表更正。P3 时(syn-mem27-46,1 → 8 线程 12.38 → 4.36 s)分析串行、不随线程数变快(1.07 s), 现在排序本身并行(同一主元顺序下 syn-mem27-46 的分析 1 线程 1.68 s → 16 线程 0.29 s)。 回代的瓶颈(P4,4 线程实测):三维测例 约 41% 的因子字节在 L0 子树层之上,逐节点由多线程 BLAS 处理,带宽只有 11–18 GB/s(同核 STREAM 22–27 GB/s); 多右端回代绕开它:每列代价 p = 4 约为单列的 1/3,p = 16 为 1/4–1/9,这就是 P4 把块 Krylov 设为默认的原因 (§2.1、§2.8)。正交化在配置的 k 下只占迭代时间的 8–11%(P3)。16 线程测量槽中的回代剖析见 docs/BLAS.md §2:L0 层之上的窄调用 OpenBLAS 只用一个核,这正是 BLAS hook 并行切分的对象。

多进程(MPI MUMPS,P9 实测为负结果,results/p9_mpi.md §3):在一个 16 核 socket(单次运行规格)上, 同一矩阵、同一主元顺序(hsolve 的排列经 PERM_IN)、同一 MUMPS 5.8.2 与控制参数,MPI 版 MUMPS 保留因子的数值分解 为 hsolve 顺序版 1 × 16 路径的 0.84–0.85 倍(2 rank × 8 线程)、0.72–0.73(4 × 4)、0.60–0.63(8 × 2)、0.59 (16 × 1),只计惯性的计数相同(0.83 / 0.71–0.72 / 0.57–0.61 / 0.56–0.57),16 列块回代 0.79–0.94 倍,进程树峰值 内存随 rank 数增长(syn-mem27-100:14.0 → 28.8 GiB)。1 个 rank 的 MPI 版与顺序版相同(1.00–1.01),损失来自 MPI 并行本身;MUMPS 自己的 METIS、ParMETIS 并行分析、分布式输入都不改变结论,flops 在 2 × 8、4 × 4 时均衡到 2–8% 内。 上限在于 socket 的内存带宽:8 → 16 线程一次分解只快 1.24 倍,证书的两次计数即使作为两个同时运行、毫无通信的 8 线程进程也只有顺序对的 0.92–0.93 倍。另外 ScaLAPACK 根节点(MUMPS 并行的默认)报告的 INFOG(12) 漏掉根前沿的 负主元,不能用于证书(hsolve 设 ICNTL(13) = 1)。因此单次 16 核运行内 hsolve 用顺序版 MUMPS + OpenMP;多进程只可能 在跨 socket / 跨节点(更多内存带宽)时有收益。 多进程模式(P10,docs/PARALLEL.md、results/p10_mpi.md):既然同一 socket 上多进程只会抢带宽,hsolve-mpi 改为 每个 socket(NUMA 节点)一个 helper 进程:leader 绑定全部核运行与单进程相同的 hs::solve(主分解、Krylov),只把彼此 独立的大块分解交给 helper——nearest 证书的两次精确计数(两个 helper 同时,各用本 socket 的核与带宽),窗口目标的 谱切片(每片一次分解 + Krylov);leader 与 helper 从不同时计算,一次运行不超过 16 核。是否交出由代价规则与覆盖整棵 进程树的内存预算决定(发送前预测、helper 报告后复核),helper 任务失败由 leader 接手,结果与单进程相同。两 socket (每个 8 核)上:1e6 nearest 1.11 / 1.09 倍(syn-mem27-100 75.8 → 68.5 s,yee-pec-box-1e6 64.1 → 59.0 s;证书 36.0 → 29.2 s),1e5 三维 nearest 1.10–1.20 倍,多片窗口 1.50–1.74 倍(syn-mem27-46 [0.1, 0.3] 33.0 → 19.0 s); MPI 启动约 1.7–2.0 s 墙钟不计入求解时间,所以只在 1e6 与多片窗口净赚。单 socket 上 0.86–0.93 倍,启动脚本在只有 一个 NUMA 节点时直接运行普通 hsolve(不起 MPI 作业)。

GPU(P10,results/p10_gpu.md):BLAS hook 的 GPU 路由(src/gpu)在 MUMPS 分解(含证书的两次精确计数)中把 L0 层之上、主机流量模型判为划算的大 dgemm(前沿贡献块的更新,k ≥ ~1000)以 FP64 cuBLAS 卸载到一张 GPU,CUDA 库在 运行时 dlopen(构建不依赖 CUDA)。分工:分析与排序、L0 子树、面板与组装、回代与 Krylov 迭代都在 CPU(16 线程); GPU 承担 1e6 分解约 43–47% 的 flops(只占 CPU 时间的 22%),每次调用 1.7–5.0 倍;1e6 三维测例上三次分解 1.07–1.09 倍 (配 P9 块参数 1.08–1.10 倍),整次运行 1.058–1.069 倍(证书 exact,每次有效、计数相同)。受主机内存带宽(暂存与 加回的流量,约 30 GB/s)限制,1e5 规模没有值得卸载的调用(on 为 0.72–0.97 倍),所以 --gpu auto 只在分解估计 ≥ 3e12 flops 时用 GPU;默认 off。无 GPU / 无 CUDA 库 / 显存不足时自动为 CPU 路径并在报告中说明(降级模式); 每次惯性计数仍是双精度 LDLᵀ 的精确 Sylvester 惯性,证书的条件与保证同 CPU 路径(实测计数与 CPU 路径 相同)。更大的收益需要因子常驻 GPU(GPU 稀疏直接解法),G1 的 SPRAL SSIDS 实验在 V100 上为负结果(results/gpu_g1.md)。


7. 故障场景与诊断流程

故障场景 检测 处置 验证(实测)
零附近密集谱(低频击穿) 零主元检测在所有附近位移触发 σ 处无检测分解 + 谱隙中点计数;非物理零模用 zero_filter_tol 按惯性切除零带(不靠事后过滤) syn-zero-cluster:绝对误差 ~1e-17,证书通过;syn-zero-cluster-real-1e5 32.9 s → 2.6–3.5 s;yee-pec-box-1e4(σ = 1、k = 6、zero_filter_tol 1e-6)6/6 精确,3135 个零空间特征值按惯性排除
重特征值 证书计数 > 找到个数 收缩重跑补齐副本 Yee 谐振腔、方波导简并模全部取全(SLEPc 漏根)
近奇异位移(σ 贴近谐振点) 零主元(INFOG(28))或 INFO=−10 微扰 σ 一次 / 簇内无检测分解 syn-near-singular(σ = λ(1+1e-12)):误差 9e-16
区间内特征值很多 区间端点惯性计数 谱切片,每片单独认证 yee-pec-box-1e4 区间内 1075 个:11.1 s / 0.20 GiB(单位移 49.8 s / 0.89 GiB),误差 2.2e-15
GHIEP 零空间(波导节点自由度) A 的零主元计数(zero_cluster_dim) 零带两侧单边位移,零簇不被需要 wg-square-1e5(零空间 24649 维):10 个最近非零模,η ≤ 1e-15(P2 返回 10 个零)
内存受限 MUMPS 分析阶段预估(INFOG(16/26)) 内存外分解;超限则拒绝并报告;块基放不下时块宽减半(告警;块宽规则的 8 不预留,放不下时不告警地用 4) PARSEC 10 万阶(因子预估 7–9 GB > 7 GB 预算):自动 OOC,结果正确
百万阶 GHIEP 后处理内存 峰值 RSS(报告 peak_rss_bytes) 只留 Schur 基、分块投影、精修前释放分解 wg-square-1e6:峰值 2886 → 1766 MB,特征值集合不变,η ≤ 2.2e-13

诊断流程:每次运行输出 report.json(残差三件套、证书、每片记录 slices、零簇维数、分解统计、块宽、五个 互斥阶段的计时 setup/factor/iterate/verify/certificate、峰值内存、告警)与 JSON-lines 事件日志(分析、排序 决策、分解、计数与计数器、每次 Krylov 运行的块宽、证书各轮、补救),可据此定位:精度问题看 pairs/rescue, 漏根看 certificate 与 slices,性能看 factor_stats 与各阶段计时(证书的代价单列为 time_certificate_s)。 结果可用 tools/eval 独立复核(§9)。


8. 安全设计

  • 禁止硬编码:所有参数由矩阵性质与配置按文档化规则推导(排序代价模型、位移扰动、证书端点等); 公开测例的特定数值从不出现在代码中。
  • 参考解物理隔离:测例输入在 data/cases/,参考解在 data/refs/;求解器 CLI 只接收 --A --B --config --out, 从不获得参考解路径;测例元数据中禁止携带参考值(tools/case.py 强制检查)。
  • 数据保护:日志与报告只含规模、范数估计、计时与统计,不含矩阵元素;特征向量只写入用户指定目录。
  • 资源安全:内存预算先于分解检查,并作为 MUMPS 工作内存上限(ICNTL(23))传入,超限变成可处理的错误 而不是被系统杀掉;区间目标在计数之后先检查 n×m 输出放不放得下。读文件时先核对头部声明的长度再分配: 头部声称 3.75e8 个元素的 1.2 KB npz 原先峰值 2.80 GiB 后才报错,现在 0.071 GiB 即报 Io。进程内 MUMPS 调用 串行,多线程调用方(如 Python 中并发 solve)不会碰到 MUMPS 实例间的全局状态竞争。开发期所有运行经资源 看门狗(绑核、进程树 RSS 上限、高水位峰值统计)。
  • 开源依赖:全部依赖开源(docs/DEPENDENCIES.md),无闭源服务。

9. 评测结果(持续更新)

对照组:SLEPc 3.26(Krylov-Schur + 位移反演 + 同版本 MUMPS 5.8.2,给予最有利配置:问题类型由元数据告知、 B 正定用 Cholesky、收敛判据与 hsolve 同为后向误差)。所有时间为求解器内部时间、同口径:hsolve 的 time_total_s 对 SLEPc 的 EPSSetUp + EPSSolve + 推迟的特征向量计算(不含 Python/MPI 启动与读测例);每次 运行都由 tools/eval 独立判定,只有双方每次重复都有效时才给加速比。

9.1 P9 集成现状:16 核对调优后的 SLEPc 与对 main c822126(如实陈述)

P9 集成构建(自研嵌套剖分带流精修 + MUMPS 块参数 + 默认构建的打补丁 MUMPS,§2.2、§4)在 gpu01 的 16 核独占测量槽 (cores 16–31,16 线程,32 GiB,guard --exclusive)中测量,2026-10-14;SLEPc 每个测例用其 16 核调优配置 (1e5:results/baseline_tuning_p16.md;1e6:results/cmp-p9-1e6-profiles.json,即 1e5 的最佳配置在 1e6 上再筛选 布局 / 排序 / BLR 与 Krylov 组,eps_ncv = 3k),5 次交错取中位数,每次运行都经 tools/eval 判定有效(4 个求解器 × 8 个配置 × 5 次 = 160 次运行全部有效)。hsolve = 默认配置(certificate = exact),hsolve-auto = certificate = auto, 关证书 = certificate = off。括号内为同一方法下 P5c(1e5,results/cmp-p5c-best*.md)或 main c822126(1e6, results/cmp-p9-1e6.md,c005)的结果;SLEPc 自身时间与当时相差 ≤ 1%。详见 results/p9_measurements.md §4、 results/cmp-p9int-best.md、results/cmp-p9int-best-interval.md、results/cmp-p9int-1e6.md。

测例 hsolve(s) SLEPc 调优(s) hsolve 加速比 hsolve-auto 关证书加速比
syn-mem27-46(三维 HEP,n ≈ 1e5) 1.99 3.51 1.77×(P5c 1.45×) 2.57×(1.96×) 3.15×(2.34×)
yee-pec-box-1e5(三维 GHEP) 2.44 3.34 1.37×(1.14×) 1.37×(1.14×) 2.07×(1.60×)
wg-square-1e5(二维 GHIEP) 0.48 0.91 1.89×(1.84×) 1.90×(1.82×) 1.89×(1.83×)
ss-qa8fk-qa8fm(GHEP) 1.49 1.43 0.96×(0.89×) 0.96×(0.89×) 1.31×(1.18×)
cav2d-rect-pert-1e5(二维 GHEP) 0.29 0.22 0.74×(0.71×) 0.74×(0.71×) 0.94×(0.94×)
yee-pec-box-1e5 区间 [40, 200] 3.30 10.36 3.14×(2.70×) 3.13×(2.72×) 3.13×(2.71×)
syn-mem27-100(三维 HEP,n = 1e6) 82.46 116.00 1.41×(main 1.04×) 2.01×(1.60×) 2.74×(2.13×)
yee-pec-box-1e6(三维 GHEP,n ≈ 1e6) 69.13 59.30 0.86×(main 0.67×) 1.08×(0.91×) 1.70×(1.38×)
  • 带确定性完备性证书的默认配置在 8 个配置中的 5 个快于调优 SLEPc(P5c 时 6 个中 4 个;1e6 的 main 为 2 个中 1 个 持平)。落后的三个:ss-qa8fk-qa8fm 与 cav2d-rect-pert-1e5 的差距是证书的两次计数分解(hsolve 做 3 次数值分解, 关证书 1 次,SLEPc 1 次;P8 实测更便宜的精确计数都无收益);yee-pec-box-1e6 上 SLEPc 的最佳配置用 BLR (cntl_7 = 1e-10,4 × 4 rank,ParMETIS)把 59 次单右端回代做得很便宜,而 hsolve 的两次计数占 33.9 / 69.1 s—— 关证书时 hsolve 快 1.70 倍,auto(随机排除检验)快 1.08 倍。
  • 1e6 对 SLEPc 的更正:P9 mpi 的初稿(SLEPc 用默认 ncv)报告 main c822126 为 1.15× / 0.74×;评审在 1e6 上筛选 SLEPc 的 Krylov 组后(eps_ncv = 3k 使 SLEPc 快 1.08 / 1.16 倍、yee 的双峰消失)更正为 1.04× / 0.67× (results/cmp-p9-1e6.md)。P9 集成构建在同一 SLEPc 配置下为 1.41× / 0.86×(SLEPc 自身 116.0 / 59.3 s,当时 115.7 / 59.6 s)。
  • 对 main c822126 的回归(results/p9_measurements.md §2–3,ABBA 交错,每次都有效、证书 exact):1e6 内存内 8 次 syn-mem27-100 111.2 → 83.2 s(1.34×)、yee-pec-box-1e6 88.2 → 69.1 s(1.28×)、wg-square-1e6(二维 GHIEP,AMD)5.94 → 5.94 s;收益在三次分解(排序的 flops 少 25% / 21%;块参数与补丁在同一主元顺序上每次分解再快 1.065–1.083 倍、端到端 1.056 / 1.053 倍——排除了 SCOTCH 波动的 factspeed 门槛,两例都过 1.05 倍)、分析与回代, 峰值内存 −2.8 / −1.7 GiB。n ≤ 3e5 的 41 个数据测例 3 次:几何平均 0.910(HEP 0.888、GHEP 0.908、GHIEP 1.005),28 例 快 3% 以上;ss-3dspectralwave2 312 → 151 s(自研嵌套剖分的因子放得进 32 GiB 内存,main 的 SCOTCH 因子在外存回代)。 筛查中慢 3% 以上的 3 个(syn-lap2d-100、wg-halfslab-1e5、wg-square-1e3,只差 2–36 ms 的二维小例,两个构建都用 AMD)与 其余不快的 4 个复测 10 次:都在 3% 以内(几何平均 0.999)。
  • 本节未覆盖:无 AVX-512 的 CPU(线程数 1–16 的扩展见 §6)。

9.2 P5c 记录:16 核对调优后的 SLEPc

16 核独占测量槽(cores 16–31,16 线程,guard --exclusive),SLEPc 每个测例用 16 核调优配置 (results/baseline_tuning_p16.md),5 次交错取中位数,30 次运行全部经 tools/eval 判定有效 (results/cmp-p5c-best.md、results/cmp-p5c-best-interval.md,测量记录 results/p5c_measurements.md)。 hsolve = 默认配置(certificate = exact),hsolve-auto = certificate = auto,关证书 = certificate = off。 括号内为同一方法下 P4 代码的 16 核结果(results/cmp-p16-best*.md;SLEPc 自身时间两次相差 2% 以内):

测例 hsolve(s) SLEPc 调优(s) hsolve 加速比 hsolve-auto 关证书加速比
syn-mem27-46(三维 HEP) 2.39 3.48 1.45×(P4 1.26×) 1.96× 2.34×(P4 1.89×)
yee-pec-box-1e5(三维 GHEP) 2.95 3.36 1.14×(P4 1.03×) 1.14× 1.60×(P4 1.45×)
wg-square-1e5(二维 GHIEP) 0.485 0.891 1.84×(P4 1.50×) 1.82× 1.83×(P4 1.51×)
ss-qa8fk-qa8fm(GHEP) 1.68 1.50 0.89×(P4 0.64×) 0.89× 1.18×(P4 0.81×)
cav2d-rect-pert-1e5(二维 GHEP) 0.300 0.215 0.71×(P4 0.64×) 0.71× 0.94×(P4 0.79×)
yee-pec-box-1e5 区间 [40, 200] 3.81 10.30 2.70×(P4 2.37×) 2.72× 2.71×(P4 2.41×)
  • 带完备性证书的默认配置在 6 个配置中的 4 个快于调优 SLEPc;ss-qa8fk-qa8fm 与 cav2d-rect-pert-1e5 仍落后, 差距来自证书的两次计数分解(这两个测例 hsolve 做 3 次数值分解,关证书时 1 次,SLEPc 1 次)。
  • certificate = auto 只在 syn-mem27-46 上改变结果(选 randomized,1.96×),其余测例按实测时间仍选精确计数。
  • 对 P4(main fad746c)的回归测量:42 个数据测例 ABBA 交错 3 次,41 个可比测例几何平均 0.786(HEP 0.772、 GHEP 0.808、GHIEP 0.808),总时间 514.8 → 453.6 s;只有 ss-tem152078 慢 6.7%(排序模型选了自研 ND, 分析比 SCOTCH 多 0.6 s)。
  • ss-3dspectralwave2 在 14 GiB 内存预算下曾随机失败(out-of-core,MUMPS 内存估计逐次波动约 30%, results/p5c_measurements.md §2.2)。P8 起计数失败换另一计数源、分析超上限再分析,都不行时交回已收敛的对 并标为证书未完成:14 GiB 下连续 15 次全部认证(results/p8_certcost.md)。P7 起内存预算默认按运行环境的上限自动设定 (32 GiB 上限下约 27 GiB),1e6 三维测例在 32 GiB 下改为内存内、快 1.71–1.83×(results/p7_membudget.md)。
  • P8 实测:在保留确定性证明(certificate = exact)的前提下,更便宜的计数办法(两进程并行计数、单次合并分解、 省缩放或零主元检测、换计数源)都没有可用收益,ss-qa8fk-qa8fm(0.87×)与 cav2d-rect-pert-1e5(0.73×)的 差距仍是两次计数分解(results/p8_certcost.md)。
  • 本节未覆盖:16 以外的线程数、无 AVX-512 的 CPU。

9.3 P4 记录:对调优后的 SLEPc(2 核与 4 核)

(本节为 P4 时的数据与结论。其中的「下一步」——完备性检验的 randomized / 单精度计数接入 driver、自研并行排序 接入自适应排序、16 核测量——已在 P5c 完成,16 核结果见 §9.2,P9 集成的见 §9.1。)

调优后的 SLEPc 明显更强(results/baseline_tuning.md,2 核,交错中位数):对每个测例与核数做贪心坐标 搜索(布局、MUMPS 排序与参数、BLR、Krylov 维数、纯化等),比 SLEPc 默认配置快 1.13 倍(syn-mem27-46)、 1.20 倍(ss-qa8fk-qa8fm)、1.07–1.29 倍(wg-square-1e5)、1.94 倍(cav2d-rect-pert-1e5)。SLEPc 默认配置在 yee-pec-box-1e5 上无效(5 次都漏掉一个重特征值副本),在 wg-square-1e5 上随机失败(几乎所有配置都会, 存档配置通过了 63/63 次)。

2 核,hsolve(P3 代码)对调优 SLEPc(求解器时间 s;所有 84 次运行有效):

测例 hsolve hsolve 关证书 SLEPc 调优 hsolve 加速比 关证书加速比
syn-mem27-46(三维 HEP) 9.57 6.26 4.88 0.51× 0.78×
yee-pec-box-1e5(三维 GHEP) 9.98 8.30 6.65 0.67× 0.80×
wg-square-1e5(二维 GHIEP) 2.54 2.47 2.63 1.04× 1.07×
ss-qa8fk-qa8fm(GHEP) 7.64 5.70 3.53 0.46× 0.62×
cav2d-rect-pert-1e5(二维 GHEP) 1.00 0.80 0.66 0.66× 0.83×
yee-pec-box-1e5 区间 [40, 200](37 个) 18.01 18.91 26.89 1.49× 1.42×

差距来自 hsolve 的分析(syn-mem27-46 上 1.44 s,SLEPc 用 PORD 0.52 s)与 3–4 次分解(SLEPc 1 次);回代阶段 基本持平,区间目标 hsolve 只需一半回代。

4 核,hsolve P4(自动块宽、InertiaCounter)(drvint 端到端表,results/p4_measurements.md §3;SLEPc 取 1×4 与 4×1 两种布局中较快者,4 核尚无调优配置): - 真实三维 nearest 测例 hsolve 仍较慢:0.58–0.89 倍(ss-2cubes_sphere 0.58、ss-qa8fk-qa8fm 0.64、 yee-pec-box-1e5 0.66、syn-mem27-46 0.79、yee-pec-cube-32 0.80、syn-lap3d-aniso-1e5 0.89),合成的 syn-ghep-near-singular-real-1e5 0.51、syn-zero-cluster-real-1e5 0.85。主因是完备性证书:两次计数分解 1.2–2.0 s,占这些运行的 30–40%(InertiaCounter 只省其中 10–20%)。 - 二维与小规模测例 hsolve 更快:cav2d-rect-pert-1e5 1.18 倍,syn-lap2d-100 1.11 倍,重特征值测例 1.59 / 1.73 倍。 - SLEPc 在 yee-pec-box-1e5、yee-pec-cube-32、ss-2cubes_sphere 上的结果不被接受(后向误差超标或缺副本), hsolve 在全部 32 个测例、三种变体的 96 次评测中都通过且由惯性证书认证;10 个复厄密测例 SLEPc 无法运行 (基线环境的 PETSc 为实数构建)。 - P4 对 P3(同一会话,4 线程):32 个测例合计 97.2 → 80.0 s;三维 1e5 测例单个快 1.08–1.45 倍。GHIEP(2 线程, 交错):wg-square-1e5 2.33 → 1.84 s、wg-halfslab-1e5 3.49 → 2.58 s;P3 在 wg-square-1e5 上已与调优 SLEPc 持平(上表),P4 的 GHIEP 与调优 SLEPc 尚未直接对比。

结论与下一步:在需要「可证明完整」的前提下,hsolve 在真实三维 nearest 测例上仍慢于调优后的 SLEPc,而 SLEPc 在多个测例上给出错误或不完整的结果;关掉证书时 hsolve 在 2 核的 nearest 测例上为 0.62–1.07 倍(P3)。 下一步:用回代 代替分解的完备性检验(src/verify,§2.3)与单精度计数接入 driver、自研并行排序接入自适应排序、16 核独占重测 (SLEPc 16 核调优与对比命令已备好,results/baseline_tuning.md)。

9.4 P3 记录(未调优的 SLEPc 基线)

4 核、tol = 1e-10、15 个测例(results/cmp4b.md;当时的基线脚本会丢掉 PETSc 选项的值,SLEPc 的求解时间也 未含推迟的特征向量计算(对 SLEPc 略有利),见 results/baseline_tuning.md 的 pitfalls):

指标 hsolve SLEPc
结果正确 15/15(精确参考误差 1e-16 ~ 1e-18) 3 个错误集合(漏重根,误差 5e-4 ~ 2e-3)+ 4 个未收敛
端到端总时间 48.8 s 69.3 s
纯求解时间 48.8 s(含完备性证书) 31.3 s(无证书)
峰值内存 全部 ≤ SLEPc —

独立评测(tools/eval:由测例矩阵与返回向量重算全部指标,不信任求解器自报): - results/eval_run2.md:hsolve 39 个测例 39 通过 / 0 失败——25 个对已认证参考完整(23 个离散精确、2 个稠密), 11 个与 ARPACK 参考一致,3 个(ss-2cubes_sphere、ss-ge87h76、ss-si34h36)无参考可比;最大后向误差 4.2e-11, 无格式问题,无虚报。 - results/eval_cmp4b.md:hsolve 15/15 通过(最大后向误差 9.5e-13);SLEPc 10 通过 / 5 失败,其中 yee-pec-box-1e4 漏掉二重特征值 107.69 的一个副本、以 118.69 顶替却自报成功(虚报);ss-tem27623 上 SLEPc 后向误差达标(2.2e-13)但相对残差 6.8e-5、特征值误差 4.2e-7(hsolve:4.1e-13、9.3e-16)。

(补充大规模测例与故障场景验证矩阵尚待完成。)


10. 复现

conda env create -f env/environment.yml && source env/activate.sh
tools/dev/build.sh release && tools/dev/test.sh release      # 先由 third_party/mumps 编译打补丁的 MUMPS(缓存),再编译 hsolve
HS_MUMPS=env tools/dev/build.sh release                       # 回退:链接环境的 conda-forge MUMPS(P9 之前的构建)
./build/release/hsolve --version                               # 构建信息:mumps=<所用 MUMPS> mumps_blocking=p9|mumps
./build/release/hsolve --A A.npz [--B B.npz] --config config.json --out out/
./build/release/hsolve --A A.npz --B B.npz --interval 1000 2000 --slice-size 0 --out out/   # 谱切片
PYTHONPATH=build/release/python python -c "import hsolve; print(hsolve.version())"        # Python 接口
./build/release/hsolve --A A.npz --B B.npz --sigma 0.5 --k 10 --block-size 1 --out out/  # 单向量(默认 0 = 自动块宽)
./build/release/hsolve --A A.npz --B B.npz --sigma 0.5 --k 10 --certificate auto --out out/  # 完备性检验方法(默认 exact)
HS_BLAS_ROUTE=off ./build/release/hsolve --A A.npz --sigma 0.5 --k 10 --out out/          # 关闭 BLAS hook 的路由(纯 OpenBLAS)
python3 tools/run/guard.py --exclusive --timeout 2700 -- python3 tools/bench/compare.py --tag mytag --cores 16-31 \
    --solvers hsolve,hsolve-auto,slepc --slepc-profile best --reps 5 case1 ...  # 测量槽内对比调优 SLEPc
python3 tools/run/guard.py -- python -m tools.eval.sweep results/raw/mytag                                     # 独立评测
tools/dev/cluster_run.sh gpu01 -- tools/dev/build.sh release                                                   # 在集群节点上运行
Python 用法见 docs/PYTHON.md;实测数字来自 bench/ 下的测量程序或经 guard.py 的 CLI 运行,方法与命令见 results/p3_measurements.md、results/p4_measurements.md、results/baseline_tuning.md 与 bench/README.md。 同一配置与线程数下结果在容差内一致;需逐位一致时设置 "deterministic": true(分解与回代逐位可复现,自适应 排序随之用固定种子的 METIS;排序决策本身是确定的代价模型),不要显式指定 SCOTCH("ordering": 3,其排序 逐次运行都会变化)。