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
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⁶ |
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
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 |
Script Outputs (JSON Fields)
| 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 |
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
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:
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:
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.
Pre-Solve Checklist
CLI Examples
# Analyze sparsity pattern
python3 scripts/sparsity_stats.py --matrix A.npy --json
# Select solver for SPD sparse system
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
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 |
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 |
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 |
Verification checklist
Do not trust a solve until each of these is satisfied with a recorded value, not a "looks fine":
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. |
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
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
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
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
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
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
1---2name: linear-solvers3description: >4 Select and configure linear solvers for Ax=b systems arising in numerical5 simulations — choose between direct (LU, Cholesky) and iterative (CG, GMRES,6 BiCGSTAB, MINRES) methods, analyze sparsity patterns and matrix conditioning,7 recommend preconditioners (AMG, ILU, IC), apply row/column scaling, and8 diagnose convergence stagnation from residual histories. Use when setting up9 a linear solve for FEM/FVM assembly, debugging slow or stalled Krylov10 iterations, choosing a preconditioner for SPD or nonsymmetric systems, or11 investigating ill-conditioning, even if the user only says "my solver is12 slow" or "GMRES won't converge."13allowed-tools: Read, Write, Grep, Glob14metadata:15 source: https://skillmd.com/skills/heshamfs/linear-solvers16 author: HeshamFS17 version: "1.2.2"18 security_tier: medium19 security_reviewed: true20 tested_with:21 - claude-code22 last_evaluated: "2026-06-24"23 eval_cases: 424 last_reviewed: "2026-06-23"25 standards:26 - "Saad (2003), Iterative Methods for Sparse Linear Systems (Krylov methods, ILU/ILUT, preconditioning)"27 - "Hestenes & Stiefel (1952) Conjugate Gradient method and the (√κ−1)/(√κ+1) error bound"28 - "Saad & Schultz (1986), GMRES restarted Krylov method"29 - "Ruge & Stüben (1987), Algebraic Multigrid (AMG) classical coarsening"30 - "Ruiz (2001) equilibration; Sinkhorn & Knopp (1967) doubly-stochastic scaling"31---3233# Linear Solvers3435## Goal3637Provide a universal workflow to select a solver, assess conditioning, and diagnose convergence for linear systems arising in numerical simulations.3839## Requirements4041- Python 3.10+42- NumPy, SciPy (for matrix operations)43- See individual scripts for dependencies4445## Inputs to Gather4647| Input | Description | Example |48|-------|-------------|---------|49| Matrix size | Dimension of system | `n = 1000000` |50| Sparsity | Fraction of nonzeros | `0.01%` |51| Symmetry | Is A = Aᵀ? | `yes` |52| Definiteness | Is A positive definite? | `yes (SPD)` |53| Conditioning | Estimated condition number | `10⁶` |5455## Decision Guidance5657### Solver Selection Flowchart5859```60Is matrix dense and small enough to factor in memory (dense float6461storage n²·8 bytes < ~2 GB, i.e. n ≲ 16000)?62├── YES → Use direct solver (Cholesky/LDLᵀ/LU by symmetry)63└── NO → Is matrix symmetric?64 ├── YES → Is it positive definite?65 │ ├── YES → Use CG with AMG/IC preconditioner66 │ └── NO → Use MINRES67 └── NO → Is it nearly symmetric?68 ├── YES → Use BiCGSTAB69 └── NO → Use GMRES with ILU/AMG70```7172### Quick Reference7374| Matrix Type | Solver | Preconditioner |75|-------------|--------|----------------|76| SPD, sparse | CG | AMG, IC |77| Symmetric indefinite | MINRES | SPD preconditioner (SSOR, symmetric block-diagonal, or AMG on SPD part) |78| Nonsymmetric | GMRES, BiCGSTAB | ILU, AMG |79| Dense | LU, Cholesky | None |80| Saddle point | Schur complement, Uzawa | Block preconditioner |8182## Script Outputs (JSON Fields)8384| Script | Key Outputs |85|--------|-------------|86| `scripts/solver_selector.py` | `recommended`, `alternatives`, `notes` |87| `scripts/convergence_diagnostics.py` | `rate`, `asymptotic_rate`, `stagnation`, `recommended_action` |88| `scripts/sparsity_stats.py` | `nnz`, `density`, `bandwidth`, `symmetry` |89| `scripts/preconditioner_advisor.py` | `suggested`, `notes` |90| `scripts/scaling_equilibration.py` | `row_scale`, `col_scale`, `notes` |91| `scripts/residual_norms.py` | `residual_norms`, `relative_norms`, `converged` |9293## Workflow94951. **Characterize matrix** - symmetry, definiteness, sparsity962. **Analyze sparsity** - Run `scripts/sparsity_stats.py`973. **Select solver** - Run `scripts/solver_selector.py`984. **Choose preconditioner** - Run `scripts/preconditioner_advisor.py`995. **Apply scaling** - If ill-conditioned, use `scripts/scaling_equilibration.py`1006. **Monitor convergence** - Use `scripts/convergence_diagnostics.py`1017. **Diagnose issues** - Check residual history with `scripts/residual_norms.py`102103## Conversational Workflow Example104105**User**: My GMRES solver is stagnating after 50 iterations. The residual drops to 1e-3 then stops improving.106107**Agent workflow**:1081. Diagnose convergence:109 ```bash110 python3 scripts/convergence_diagnostics.py --residuals 1,0.1,0.01,0.005,0.003,0.002,0.002,0.002 --json111 ```1122. Check for preconditioning advice:113 ```bash114 python3 scripts/preconditioner_advisor.py --matrix-type nonsymmetric --sparse --ill-conditioned --json115 ```1163. Recommend: Increase restart parameter, try ILU(k) with higher k, or switch to AMG.117118## Pre-Solve Checklist119120- [ ] Confirm matrix symmetry/definiteness121- [ ] Decide direct vs iterative based on size and sparsity122- [ ] Set residual tolerance relative to physics scale123- [ ] Choose preconditioner appropriate to matrix structure124- [ ] Apply scaling/equilibration if needed125- [ ] Track convergence and adjust if stagnation occurs126127## CLI Examples128129```bash130# Analyze sparsity pattern131python3 scripts/sparsity_stats.py --matrix A.npy --json132133# Select solver for SPD sparse system134python3 scripts/solver_selector.py --symmetric --positive-definite --sparse --size 1000000 --json135136# Get preconditioner recommendation137python3 scripts/preconditioner_advisor.py --matrix-type spd --sparse --json138139# Diagnose convergence from residual history140python3 scripts/convergence_diagnostics.py --residuals 1,0.2,0.05,0.01 --json141142# Apply scaling143python3 scripts/scaling_equilibration.py --matrix A.npy --symmetric --json144145# Compute residual norms146python3 scripts/residual_norms.py --residual 1,0.1,0.01 --rhs 1,0,0 --json147```148149## Error Handling150151| Error | Cause | Resolution |152|-------|-------|------------|153| `Matrix file not found` | Invalid path | Check file exists |154| `Matrix must be square` | Non-square input | Verify matrix dimensions |155| `Residuals must be positive` | Invalid residual data | Check input format |156157## Interpretation Guidance158159### Convergence Rate160161`convergence_diagnostics.py` reports two rates: `rate` (mean of all per-iteration162residual ratios over the full history) and `asymptotic_rate` (mean over a short163trailing window). The `stagnation` flag is driven by `asymptotic_rate` (> 0.95),164because stagnation is a tail property — early fast drops can hide a flat tail.165Read `asymptotic_rate` when judging the regime below:166167| Asymptotic rate | Meaning | Action |168|-----------------|---------|--------|169| < 0.1 | Excellent | Current setup optimal |170| 0.1 - 0.5 | Good | Acceptable for most problems |171| 0.5 - 0.95 | Slow | Consider better preconditioner |172| > 0.95 | Stagnation | Change solver or preconditioner |173174### Stagnation Diagnosis175176| Pattern | Likely Cause | Fix |177|---------|--------------|-----|178| Flat residual | Poor preconditioner | Improve preconditioner |179| Oscillating | Near-singular or indefinite | Check matrix, try different solver |180| Very slow decay | Ill-conditioned | Apply scaling, use AMG |181182## Verification checklist183184Do not trust a solve until each of these is satisfied with a recorded value, not a "looks fine":185186- [ ] 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.187- [ ] 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.188- [ ] 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.189- [ ] 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.190- [ ] 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.191- [ ] 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).192193## Common pitfalls & rationalizations194195| Tempting shortcut | Why it's wrong / what to do |196|-------------------|-----------------------------|197| "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. |198| "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`. |199| "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. |200| "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. |201| "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. |202| "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. |203204## Security205206### Input Validation207- All numeric inputs (residuals, tolerances, matrix entries) are validated as finite numbers208- Comma-separated residual/vector inputs are capped at 100,000 entries209- The `solver_selector.py` `--size` parameter is bounded at 10 billion210- `--matrix-type` is validated against a fixed allowlist (`spd`, `symmetric-indefinite`, `nonsymmetric`)211- Boolean flags (`--symmetric`, `--positive-definite`, `--sparse`, `--ill-conditioned`) are type-safe argparse flags212213### File Access214- `sparsity_stats.py` and `scaling_equilibration.py` read a single matrix file (`.npy` format) specified by `--matrix`215- `np.load()` is called with `allow_pickle=False` to prevent arbitrary code execution via crafted `.npy` files216- Matrix files are rejected if they exceed 500 MB before any parsing occurs217- Matrix dimension limits (100,000 per dimension) prevent memory exhaustion218- All other scripts read no external files; inputs are provided via CLI arguments219220### Tool Restrictions221- **Read**: Used to inspect script source, references, and matrix files222- **Write**: Used to save analysis results or solver recommendations; writes are scoped to the user's working directory223- **Grep/Glob**: Used to locate relevant files and search references224- The skill's `allowed-tools` excludes `Bash` to prevent the agent from executing arbitrary commands when processing untrusted matrix files or numeric inputs225226### Safety Measures227- No `eval()`, `exec()`, or dynamic code generation228- All subprocess calls use explicit argument lists (no `shell=True`)229- Reduced tool surface (no Bash) limits the agent to read/write operations only230- JSON output mode produces structured, parseable results without shell-interpretable content231232## Limitations233234- **Large dense matrices**: Direct solvers may run out of memory235- **Highly indefinite**: Standard preconditioners may fail236- **Saddle-point**: Requires specialized block preconditioners237238## References239240- `references/solver_decision_tree.md` - Selection logic241- `references/preconditioner_catalog.md` - Preconditioner options242- `references/convergence_patterns.md` - Diagnosing failures243- `references/scaling_guidelines.md` - Equilibration guidance244245## Version History246247- **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 consistency248- **v1.1.0** (2024-12-24): Enhanced documentation, decision guidance, examples249- **v1.0.0**: Initial release with 6 solver analysis scripts