[Intermediate → Advanced] — Solving . The most-used algorithm in scientific computing, and the one where conditioning bites hardest.
Why this note matters most
Almost everything reduces to a linear solve:
| Problem | Reduces to |
|---|---|
| Newton’s method | each iteration |
| FEM | — often millions of unknowns |
| Implicit PDE solvers | a linear solve per time step |
| Least squares / regression | the normal equations |
| Kalman filter | a solve in the gain computation |
| Second-order optimisation |
If you optimise one thing in a scientific code, it’s usually the linear solve.
Never invert the matrix
The single most important practical rule in this domain:
Computing and multiplying is:
~3× more expensive — inversion is with a larger constant than a factor-and-solve.
Less accurate — more operations, more rounding, and the explicit inverse can be catastrophically inaccurate for ill-conditioned .
Destroys sparsity — the inverse of a sparse matrix is generally dense. A tridiagonal matrix is cheap to factor and its inverse would not fit in memory.
In code: numpy.linalg.solve(A, b), not inv(A) @ b. scipy.linalg.solve_triangular, cho_solve, lu_solve. MATLAB’s A\b. The only legitimate uses of an explicit inverse are when you genuinely need the entries — a covariance matrix’s inverse for a statistical quantity, for instance.
LU decomposition
Gaussian elimination, recorded.
with unit lower triangular, upper triangular, a permutation.
Then solving is two cheap triangular solves:
Ly = Pb forward substitution O(n²)
Ux = y back substitution O(n²)
Cost: factorisation , each solve .
Which is why you factor once and solve many times. With 100 right-hand sides, factor-then-solve is ~100× faster than solving from scratch each time. This comes up constantly — implicit time-stepping reuses the same every step, and re-factorising it each time is a common and expensive mistake.
Pivoting
Partial pivoting swaps rows to put the largest available entry on the diagonal.
Without it, Gaussian elimination is unstable. The classic demonstration:
Eliminating with the tiny pivot multiplies the second row by , and the original entry is lost to rounding entirely. The computed answer is wrong by 100%. Swap the rows first and it’s fine.
Partial pivoting is why LAPACK’s
dgesvis backward stable in practice and your textbook implementation isn’t. It costs almost nothing — comparisons against arithmetic — and it’s not optional. → Backward stability
Complete pivoting (rows and columns) is more stable and rarely worth the cost.
Specialised factorisations
Exploit structure — often a 2× or better win, and better stability.
Cholesky — for symmetric positive definite :
Half the work (), half the storage, no pivoting needed, and unconditionally stable. Use it whenever is SPD — covariance matrices, FEM stiffness matrices, and the normal equations all are.
Bonus: Cholesky failing is a test. If the factorisation breaks down, isn’t positive definite — which is exactly how you check that a covariance matrix is valid or that a Hessian is at a minimum rather than a saddle.
QR — with orthogonal, upper triangular.
More expensive than LU () and more stable, because orthogonal transformations don’t amplify error — . The right tool for least squares.
SVD — .
The most expensive and the most informative. Gives you rank, condition number, null space, pseudoinverse, and the best low-rank approximation. When a problem is rank-deficient or nearly so, SVD is what tells you and what handles it. → Linear Algebra
Conditioning
The error bound:
Rule of thumb: means you lose about digits.
With a
double’s 16 digits: leaves you 8 good digits. leaves you none — the computed answer is uncorrelated with the true one.
This is a property of the problem, not the algorithm. A perfectly stable solver on an ill-conditioned system still gives you a bad answer, and that’s not a bug to fix. → Conditioning vs stability
What causes ill-conditioning:
Badly scaled variables — mixing metres and micrometres. Fix by non-dimensionalising, and this is the most common and most fixable cause.
Nearly-dependent columns — two nearly-identical features in a regression. This is multicollinearity, and it’s why regularisation exists.
The normal equations. Solving least squares via squares the condition number: . Use QR or SVD instead — this is the single most common numerical mistake in statistics and ML code, and it silently halves your accuracy.
Estimating it: numpy.linalg.cond(A), or LAPACK’s condition estimator which is rather than requiring a full SVD.
A residual is not an error. A small does not imply is close to the true solution when is large. Check the condition number, not just the residual.
Sparse systems
Most large real systems are sparse — FEM, circuit simulation, PDEs, graphs. A million unknowns with ten nonzeros per row.
Dense storage would be entries. Sparse is .
Formats: CSR (row-wise, good for ), CSC (column-wise), COO (easy to build, convert before computing).
Direct sparse solvers
Sparse LU or Cholesky, with reordering.
The problem is fill-in — factorisation creates nonzeros where had none, and a bad ordering can fill the matrix completely.
Reordering algorithms — AMD (approximate minimum degree), METIS nested dissection — permute rows and columns to minimise fill. The difference between a good and bad ordering is frequently orders of magnitude in memory and time. This is what makes sparse direct solvers viable, and it’s why UMFPACK/CHOLMOD/MUMPS are non-trivial software.
Iterative solvers
For very large systems where even sparse factorisation is too expensive.
They only need products — never the matrix explicitly, which enables matrix-free methods.
| Method | For |
|---|---|
| Conjugate Gradient (CG) | symmetric positive definite — the workhorse |
| MINRES | symmetric indefinite |
| GMRES | general nonsymmetric |
| BiCGSTAB | nonsymmetric, cheaper than GMRES |
CG converges in at most steps in exact arithmetic, and in practice in far fewer — with error contracting like:
Note the — CG’s convergence depends on the square root of the condition number, which is much better than it sounds.
Preconditioning is what makes iterative methods work. Solve where but is cheap to invert:
- Jacobi — diagonal. Trivial, weak
- Incomplete LU/Cholesky (ILU/IC) — factorise approximately, dropping small fill
- Multigrid — for elliptic PDEs, which is optimal. The best preconditioner there is for the right problem
- Domain decomposition — parallel-friendly
An unpreconditioned iterative solver on a real problem usually doesn’t converge in useful time. The preconditioner is not an optimisation — it’s the algorithm. Most of the research effort in this area is about preconditioners, not the Krylov methods themselves.
Choosing
Is A small (n < ~1000) and dense?
├── symmetric positive definite? → CHOLESKY
├── general? → LU with partial pivoting
├── least squares? → QR (never the normal equations)
└── rank-deficient / uncertain? → SVD
Is A large and sparse?
├── moderately large, direct feasible? → sparse Cholesky/LU + reordering
└── very large? → CG (SPD) or GMRES + a preconditioner
Practical notes
Use LAPACK. Directly, or through NumPy/SciPy/Eigen/Armadillo. Forty years of numerical care that you will not reproduce. Your hand-written elimination will be slower and less accurate.
Factor once, solve many. Cache the factorisation whenever is reused.
Exploit structure. Symmetric, positive definite, banded, triangular, Toeplitz — each has a specialised routine that’s substantially faster. Telling the library about structure is free performance.
Never form the normal equations for least squares.
Check before trusting a result. And check the residual — but know it isn’t sufficient.
Scale your variables to comparable magnitudes. It’s the cheapest conditioning fix available.
Watch memory on sparse direct solvers. Fill-in can exceed RAM without warning; that’s the signal to switch to iterative.
Related
- Eigenvalues — the other big linear-algebra computation
- PDEs — where the huge sparse systems come from
- Linear Algebra — the theory
- Numerical methods map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering