2.4.3 填充位 (Fill-ins) 优化与重排序算法 (Markowitz Reord...

文档摘要

2.4.3 填充位 (Fill-ins) 优化与重排序算法 (Markowitz Reordering) 在稀疏矩阵求解的幽微世界里，有一场无声的战争——不是发生在内存带宽与计算吞吐之间，也不是在浮点单元与访存延迟之间，而是在零与非零的边界线上。当我们在 $LU$ 分解中对一个原本只有 $10^4$ 个非零元的 $10^3 \times 10^3$ 矩阵动刀时，若不做任何干预，分解后可能凭空“长出”上万个本不该存在的非零元——它们不携带物理意义，不反映原始系统的耦合关系，却贪婪地吞噬内存、拖慢前代/回代、甚至让整个求解器在 $O(n^3)$ 的幻觉中窒息而亡。这些幽灵般的新增非零元，就是我们今天要亲手驯服的对象：填充位（Fill-ins）。