linear-solvers

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

Linear Solvers

线性求解器

Goal

目标

Provide a universal workflow to select a solver, assess conditioning, and diagnose convergence for linear systems arising in numerical simulations.

为数值模拟中出现的线性系统提供通用工作流，用于选择求解器、评估条件数以及诊断收敛问题。

Requirements

要求

Python 3.10+
NumPy, SciPy (for matrix operations)
See individual scripts for dependencies

Python 3.10+
NumPy、SciPy（用于矩阵运算）
查看各个脚本获取依赖信息

Inputs to Gather

需要收集的输入

Input	Description	Example
Matrix size	Dimension of system	`n = 1000000`
Sparsity	Fraction of nonzeros	`0.01%`
Symmetry	Is A = Aᵀ?	`yes`
Definiteness	Is A positive definite?	`yes (SPD)`
Conditioning	Estimated condition number	`10⁶`

输入项	描述	示例
矩阵规模	系统维度	`n = 1000000`
稀疏性	非零元素占比	`0.01%`
对称性	是否满足A = Aᵀ？	`yes`
定性	矩阵是否为正定？	`yes (SPD)`
条件数	估计的条件数	`10⁶`

Decision Guidance

决策指南

Solver Selection Flowchart

求解器选择流程图

Is matrix dense and small enough to factor in memory (dense float64
storage n²·8 bytes < ~2 GB, i.e. n ≲ 16000)?
├── YES → Use direct solver (Cholesky/LDLᵀ/LU by symmetry)
└── NO → Is matrix symmetric?
    ├── YES → Is it positive definite?
    │   ├── YES → Use CG with AMG/IC preconditioner
    │   └── NO → Use MINRES
    └── NO → Is it nearly symmetric?
        ├── YES → Use BiCGSTAB
        └── NO → Use GMRES with ILU/AMG

矩阵是否为稠密矩阵且规模小到可在内存中分解（稠密float64存储n²·8字节 < ~2 GB，即n ≲ 16000）？
├── 是 → 使用直接求解器（根据对称性选择Cholesky/LDLᵀ/LU）
└── 否 → 矩阵是否对称？
    ├── 是 → 是否为正定矩阵？
    │   ├── 是 → 使用带AMG/IC预条件器的CG
    │   └── 否 → 使用MINRES
    └── 否 → 是否接近对称？
        ├── 是 → 使用BiCGSTAB
        └── 否 → 使用带ILU/AMG预条件器的GMRES

Quick Reference

快速参考表

Matrix Type	Solver	Preconditioner
SPD, sparse	CG	AMG, IC
Symmetric indefinite	MINRES	SPD preconditioner (SSOR, symmetric block-diagonal, or AMG on SPD part)
Nonsymmetric	GMRES, BiCGSTAB	ILU, AMG
Dense	LU, Cholesky	None
Saddle point	Schur complement, Uzawa	Block preconditioner

矩阵类型	求解器	预条件器
SPD、稀疏	CG	AMG、IC
对称不定	MINRES	SPD预条件器（SSOR、对称块对角，或针对SPD部分的AMG）
非对称	GMRES、BiCGSTAB	ILU、AMG
稠密	LU、Cholesky	无
鞍点	Schur补、Uzawa	块预条件器

Script Outputs (JSON Fields)

脚本输出（JSON字段）

Script	Key Outputs
`scripts/solver_selector.py`	`recommended` , `alternatives` , `notes`
`scripts/convergence_diagnostics.py`	`rate` , `asymptotic_rate` , `stagnation` , `recommended_action`
`scripts/sparsity_stats.py`	`nnz` , `density` , `bandwidth` , `symmetry`
`scripts/preconditioner_advisor.py`	`suggested` , `notes`
`scripts/scaling_equilibration.py`	`row_scale` , `col_scale` , `notes`
`scripts/residual_norms.py`	`residual_norms` , `relative_norms` , `converged`

脚本	关键输出
`scripts/solver_selector.py`	`recommended` , `alternatives` , `notes`
`scripts/convergence_diagnostics.py`	`rate` , `asymptotic_rate` , `stagnation` , `recommended_action`
`scripts/sparsity_stats.py`	`nnz` , `density` , `bandwidth` , `symmetry`
`scripts/preconditioner_advisor.py`	`suggested` , `notes`
`scripts/scaling_equilibration.py`	`row_scale` , `col_scale` , `notes`
`scripts/residual_norms.py`	`residual_norms` , `relative_norms` , `converged`

Workflow

工作流

Characterize matrix - symmetry, definiteness, sparsity
Analyze sparsity - Run
```
scripts/sparsity_stats.py
```
Select solver - Run
```
scripts/solver_selector.py
```
Choose preconditioner - Run
```
scripts/preconditioner_advisor.py
```
Apply scaling - If ill-conditioned, use
```
scripts/scaling_equilibration.py
```
Monitor convergence - Use
```
scripts/convergence_diagnostics.py
```
Diagnose issues - Check residual history with
```
scripts/residual_norms.py
```

矩阵特征描述 - 对称性、定性、稀疏性
稀疏性分析 - 运行
```
scripts/sparsity_stats.py
```
选择求解器 - 运行
```
scripts/solver_selector.py
```
选择预条件器 - 运行
```
scripts/preconditioner_advisor.py
```
应用缩放 - 若矩阵病态，使用
```
scripts/scaling_equilibration.py
```
监控收敛 - 使用
```
scripts/convergence_diagnostics.py
```
诊断问题 - 通过
```
scripts/residual_norms.py
```
检查残差历史

Conversational Workflow Example

对话式工作流示例

User: My GMRES solver is stagnating after 50 iterations. The residual drops to 1e-3 then stops improving.

Agent workflow:

Diagnose convergence:

bash

python3 scripts/convergence_diagnostics.py --residuals 1,0.1,0.01,0.005,0.003,0.002,0.002,0.002 --json

Check for preconditioning advice:

bash

python3 scripts/preconditioner_advisor.py --matrix-type nonsymmetric --sparse --ill-conditioned --json

Recommend: Increase restart parameter, try ILU(k) with higher k, or switch to AMG.

用户：我的GMRES求解器在50次迭代后停滞，残差降到1e-3后不再改善。

Agent工作流：

诊断收敛情况：

bash

python3 scripts/convergence_diagnostics.py --residuals 1,0.1,0.01,0.005,0.003,0.002,0.002,0.002 --json

获取预条件器建议：

bash

python3 scripts/preconditioner_advisor.py --matrix-type nonsymmetric --sparse --ill-conditioned --json

推荐方案：增加重启参数，尝试更高k值的ILU(k)，或切换到AMG。

Pre-Solve Checklist

求解前检查清单

CLI Examples

CLI示例

bash

undefined

bash

undefined

Analyze sparsity pattern

分析稀疏模式

python3 scripts/sparsity_stats.py --matrix A.npy --json

Select solver for SPD sparse system

为SPD稀疏系统选择求解器

python3 scripts/solver_selector.py --symmetric --positive-definite --sparse --size 1000000 --json

Get preconditioner recommendation

获取预条件器推荐

python3 scripts/preconditioner_advisor.py --matrix-type spd --sparse --json

Diagnose convergence from residual history

根据残差历史诊断收敛情况

python3 scripts/convergence_diagnostics.py --residuals 1,0.2,0.05,0.01 --json

Apply scaling

应用缩放

python3 scripts/scaling_equilibration.py --matrix A.npy --symmetric --json

Compute residual norms

计算残差范数

python3 scripts/residual_norms.py --residual 1,0.1,0.01 --rhs 1,0,0 --json

undefined

python3 scripts/residual_norms.py --residual 1,0.1,0.01 --rhs 1,0,0 --json

undefined

Error Handling

错误处理

Error	Cause	Resolution
`Matrix file not found`	Invalid path	Check file exists
`Matrix must be square`	Non-square input	Verify matrix dimensions
`Residuals must be positive`	Invalid residual data	Check input format

错误	原因	解决方案
`Matrix file not found`	路径无效	检查文件是否存在
`Matrix must be square`	输入矩阵非方阵	验证矩阵维度
`Residuals must be positive`	残差数据无效	检查输入格式

Interpretation Guidance

解读指南

Convergence Rate

收敛速率

convergence_diagnostics.py

reports two rates:

rate

(mean of all per-iteration residual ratios over the full history) and

asymptotic_rate

(mean over a short trailing window). The

stagnation

flag is driven by

asymptotic_rate

(> 0.95), because stagnation is a tail property — early fast drops can hide a flat tail. Read

asymptotic_rate

when judging the regime below:

Asymptotic rate	Meaning	Action
< 0.1	Excellent	Current setup optimal
0.1 - 0.5	Good	Acceptable for most problems
0.5 - 0.95	Slow	Consider better preconditioner
> 0.95	Stagnation	Change solver or preconditioner

convergence_diagnostics.py

会报告两种速率：

rate

（整个历史中所有迭代残差比率的平均值）和

asymptotic_rate

（最近一小段窗口内的平均值）。

stagnation

标志由

asymptotic_rate

（> 0.95）驱动，因为停滞是尾部特性——早期的快速下降可能掩盖后期的平台期。判断状态时查看

asymptotic_rate

：

渐近速率	含义	操作建议
< 0.1	极佳	当前设置最优
0.1 - 0.5	良好	适用于大多数问题
0.5 - 0.95	缓慢	考虑使用更好的预条件器
> 0.95	停滞	更换求解器或预条件器

Stagnation Diagnosis

停滞诊断

Pattern	Likely Cause	Fix
Flat residual	Poor preconditioner	Improve preconditioner
Oscillating	Near-singular or indefinite	Check matrix, try different solver
Very slow decay	Ill-conditioned	Apply scaling, use AMG

模式	可能原因	修复方案
残差平台	预条件器效果差	改进预条件器
残差振荡	矩阵接近奇异或不定	检查矩阵，尝试不同求解器
残差衰减极慢	矩阵病态	应用缩放，使用AMG

Verification checklist

验证检查清单

Do not trust a solve until each of these is satisfied with a recorded value, not a "looks fine":

Recorded
```
asymptotic_rate
```
from
```
convergence_diagnostics.py
```
and confirmed it is below the 0.95 stagnation threshold (and ideally < 0.5); a low whole-history
```
rate
```
alone does not rule out a flat tail.
Checked the relative residual from
```
residual_norms.py
```
against the physics-scaled
```
--rel-tol
```
(default 1e-6), not just the absolute norm; for unscaled RHS use
```
--require-both
```
so an undersized
```
rhs
```
cannot fake convergence.
Confirmed
```
solver_selector.py
```
```
recommended
```
matches the actual matrix properties recorded from
```
sparsity_stats.py
```
(
```
symmetry
```
, and definiteness if known) — e.g. CG only when symmetric AND positive-definite, MINRES for symmetric-indefinite, GMRES/BiCGSTAB for nonsymmetric.
For systems flagged ill-conditioned, ran
```
scaling_equilibration.py
```
and recorded
```
row_scale_max/row_scale_min
```
and
```
col_scale_max/col_scale_min
```
; for symmetric matrices used
```
--symmetric
```
(D A D) so symmetry is preserved, and applied row_scale THEN col_scale for nonsymmetric two-sided scaling.
Reviewed
```
sparsity_stats.py
```
```
notes
```
/
```
zero_rows
```
/
```
zero_cols
```
from
```
scaling_equilibration.py
```
— any zero row or column means the system is structurally singular and the scale-of-1 fallback is not a fix.
Confirmed the preconditioner from
```
preconditioner_advisor.py
```
is admissible for the chosen Krylov method — in particular a MINRES preconditioner must be SPD (an indefinite incomplete LDLᵀ is invalid).

在确认求解有效前，需记录以下各项的数值，而非仅凭“看起来没问题”：

记录
```
convergence_diagnostics.py
```
输出的
```
asymptotic_rate
```
，确认其低于0.95的停滞阈值（理想情况下< 0.5）；仅低的全历史
```
rate
```
不能排除尾部平台期。
对比
```
residual_norms.py
```
输出的相对残差与基于物理尺度设置的
```
--rel-tol
```
（默认1e-6），而非仅查看绝对范数；对于未缩放的右端项，使用
```
--require-both
```
，避免因右端项过小而伪装收敛。
确认
```
solver_selector.py
```
推荐的求解器与
```
sparsity_stats.py
```
记录的实际矩阵属性（
```
symmetry
```
，若已知则包括定性）匹配——例如，仅当矩阵对称且正定时才使用CG，对称不定矩阵使用MINRES，非对称矩阵使用GMRES/BiCGSTAB。
对于标记为病态的系统，运行
```
scaling_equilibration.py
```
并记录
```
row_scale_max/row_scale_min
```
和
```
col_scale_max/col_scale_min
```
；对于对称矩阵，使用
```
--symmetric
```
（D A D）以保持对称性，对于非对称矩阵，先应用行缩放再应用列缩放进行双侧缩放。
查看
```
sparsity_stats.py
```
的
```
notes
```
以及
```
scaling_equilibration.py
```
的
```
zero_rows
```
/
```
zero_cols
```
——任何零行或零列意味着系统结构奇异，仅使用缩放因子1的回退方案无法解决问题。
确认
```
preconditioner_advisor.py
```
推荐的预条件器适用于所选的Krylov方法——特别注意，MINRES的预条件器必须是SPD（不定的不完全LDLᵀ无效）。

Common pitfalls & rationalizations

常见陷阱与误区

Tempting shortcut	Why it's wrong / what to do
"The mean `rate` is low, so it converged."	`rate` is the whole-history mean and is dominated by early fast drops; stagnation is a tail property. Read `asymptotic_rate` and confirm it is below 0.95.
"The absolute residual is tiny, so we're done."	A small absolute norm can be meaningless if the RHS is large or unscaled. Check the `relative_norms` / `relative_value` against a physics-scaled `--rel-tol` .
"It's symmetric, so just use CG."	CG requires symmetric AND positive-definite. A symmetric-indefinite matrix needs MINRES (with an SPD preconditioner); using CG can break down or stall. Confirm definiteness before selecting.
"Large system, so factor it directly."	`solver_selector.py` gates dense direct solvers on dense float64 storage (n²·8 bytes < ~2 GB, n ≈ 16384); above that a dense Cholesky/LU is infeasible and you must route to an iterative method.
"Scaling is just dividing each row by its max."	One-sided row scaling does not equilibrate. For nonsymmetric matrices derive `col_scale` from the row-scaled matrix and apply both; for symmetric matrices use the symmetric D A D scale or you destroy symmetry.
"GMRES stagnates, so add more iterations."	A flat tail means the preconditioner or restart length is the problem, not iteration count. Strengthen the preconditioner (higher ILU fill / AMG), increase the restart parameter, or switch methods.

诱人的捷径	错误原因/正确做法
“平均 `rate` 很低，所以已经收敛了。”	`rate` 是全历史平均值，受早期快速下降的影响较大；停滞是尾部特性。查看 `asymptotic_rate` 并确认其低于0.95。
“绝对残差很小，所以我们完成了。”	若右端项较大或未缩放，小的绝对范数可能毫无意义。对比 `relative_norms` / `relative_value` 与基于物理尺度的 `--rel-tol` 。
“矩阵是对称的，所以直接用CG。”	CG要求矩阵对称且正定。对称不定矩阵需要MINRES（搭配SPD预条件器）；使用CG可能导致崩溃或停滞。选择前需确认定性。
“系统规模大，所以直接分解。”	`solver_selector.py` 会根据稠密float64存储量（n²·8字节 < ~2 GB，n≈16384）判断是否使用稠密直接求解器；超过该规模，稠密Cholesky/LU分解不可行，必须使用迭代法。
“缩放就是将每行除以其最大值。”	单侧行缩放无法实现平衡。对于非对称矩阵，从行缩放后的矩阵推导 `col_scale` 并同时应用两者；对于对称矩阵，使用对称D A D缩放，否则会破坏对称性。
“GMRES停滞了，所以增加迭代次数。”	平台期意味着预条件器或重启长度有问题，而非迭代次数不足。增强预条件器（更高的ILU填充率/AMG）、增加重启参数，或更换方法。

Security

安全性

Input Validation

输入验证

All numeric inputs (residuals, tolerances, matrix entries) are validated as finite numbers
Comma-separated residual/vector inputs are capped at 100,000 entries
The
```
solver_selector.py
```
```
--size
```
parameter is bounded at 10 billion

--matrix-type

is validated against a fixed allowlist (

spd

symmetric-indefinite

nonsymmetric

)

Boolean flags (

--symmetric

--positive-definite

--sparse

--ill-conditioned

) are type-safe argparse flags

所有数值输入（残差、容差、矩阵元素）均验证为有限数
逗号分隔的残差/向量输入最多允许100,000个条目
```
solver_selector.py
```
的
```
--size
```
参数上限为100亿
```
--matrix-type
```
会验证是否在固定允许列表中（
```
spd
```
、
```
symmetric-indefinite
```
、
```
nonsymmetric
```
）
布尔标志（
```
--symmetric
```
、
```
--positive-definite
```
、
```
--sparse
```
、
```
--ill-conditioned
```
）是类型安全的argparse标志

File Access

文件访问

sparsity_stats.py

and

scaling_equilibration.py

read a single matrix file (

.npy

format) specified by

--matrix

```
np.load()
```
is called with
```
allow_pickle=False
```
to prevent arbitrary code execution via crafted
```
.npy
```
files
Matrix files are rejected if they exceed 500 MB before any parsing occurs
Matrix dimension limits (100,000 per dimension) prevent memory exhaustion
All other scripts read no external files; inputs are provided via CLI arguments

sparsity_stats.py

和

scaling_equilibration.py

读取

--matrix

指定的单个矩阵文件（

.npy

格式）

调用
```
np.load()
```
时设置
```
allow_pickle=False
```
，防止通过恶意
```
.npy
```
文件执行任意代码
矩阵文件若超过500 MB，在解析前会被拒绝
矩阵维度限制为每维100,000，防止内存耗尽
所有其他脚本不读取外部文件；输入通过CLI参数提供

Tool Restrictions

工具限制

Read: Used to inspect script source, references, and matrix files
Write: Used to save analysis results or solver recommendations; writes are scoped to the user's working directory
Grep/Glob: Used to locate relevant files and search references
The skill's
```
allowed-tools
```
excludes
```
Bash
```
to prevent the agent from executing arbitrary commands when processing untrusted matrix files or numeric inputs

读取：用于检查脚本源码、参考资料和矩阵文件
写入：用于保存分析结果或求解器推荐；写入操作仅限于用户的工作目录
Grep/Glob：用于定位相关文件和搜索参考资料
技能的
```
allowed-tools
```
排除了
```
Bash
```
，防止代理在处理不可信矩阵文件或数值输入时执行任意命令

Safety Measures

安全措施

No
```
eval()
```
,
```
exec()
```
, or dynamic code generation
All subprocess calls use explicit argument lists (no
```
shell=True
```
)
Reduced tool surface (no Bash) limits the agent to read/write operations only
JSON output mode produces structured, parseable results without shell-interpretable content

不使用
```
eval()
```
、
```
exec()
```
或动态代码生成
所有子进程调用使用显式参数列表（不使用
```
shell=True
```
）
减少工具范围（无Bash），将代理限制为仅读/写操作
JSON输出模式生成结构化、可解析的结果，不含可被shell解释的内容

Limitations

局限性

Large dense matrices: Direct solvers may run out of memory
Highly indefinite: Standard preconditioners may fail
Saddle-point: Requires specialized block preconditioners

大型稠密矩阵：直接求解器可能耗尽内存
高度不定矩阵：标准预条件器可能失效
鞍点系统：需要专门的块预条件器

References

参考资料

```
references/solver_decision_tree.md
```
- Selection logic
```
references/preconditioner_catalog.md
```
- Preconditioner options
```
references/convergence_patterns.md
```
- Diagnosing failures
```
references/scaling_guidelines.md
```
- Equilibration guidance

```
references/solver_decision_tree.md
```
- 选择逻辑
```
references/preconditioner_catalog.md
```
- 预条件器选项
```
references/convergence_patterns.md
```
- 故障诊断
```
references/scaling_guidelines.md
```
- 平衡指南

Version History

版本历史

v1.2.0 (2026-06-23): Fixed asymptotic stagnation detection, dense-feasibility solver gating, saddle-point/small-dense direct-solver routing, equilibrating two-sided scaling, CG iteration-bound table, and doc/eval consistency
v1.1.0 (2024-12-24): Enhanced documentation, decision guidance, examples
v1.0.0: Initial release with 6 solver analysis scripts

v1.2.0（2026-06-23）：修复了渐近停滞检测、稠密可行性求解器门控、鞍点/小型稠密直接求解器路由、双侧平衡缩放、CG迭代边界表，以及文档/评估一致性
v1.1.0（2024-12-24）：增强了文档、决策指南、示例
v1.0.0：初始版本，包含6个求解器分析脚本