Wait, What?
A matrix algorithm can return a number that is mathematically legal and still be numerically useless.
Numerical linear algebra is where algebra meets finite-precision computers. The equations may be exact on paper, but real machines round, reorder, block, vectorise and approximate. The professional skill is not merely knowing Gaussian elimination or QR decomposition. It is knowing which factorisation fits the structure, how sensitive the problem is, how stable the algorithm is, and whether the computed answer deserves trust.
Quick Answer
Learn this subject through the route linear systems → elimination → triangular solves → LU → pivoting → conditioning → backward error → least squares → QR → SVD → special structure → sparse systems → iterative methods → blocking and hardware → professional validation. A beginner should be able to trace each row operation. A professional should be able to explain why the chosen algorithm is stable enough, efficient enough and appropriate for the matrix structure.
1. Begin With the Problem, Not the Factorisation
Most learners meet matrices as symbols to manipulate. Numerical work begins by asking what task the matrix represents. Are we solving Ax=b? Fitting an overdetermined model? Finding a low-rank approximation? Computing an eigenvector? Solving a huge sparse system? These jobs require different algorithms.
The first professional habit is therefore to identify the computational question before selecting the method.
2. Gaussian Elimination Is a Controlled Sequence of Simplifications
For a dense square system, Gaussian elimination transforms the matrix into upper-triangular form and then solves by back substitution. Learners should first trace a 3×3 system by hand and record which entries become zero after each elimination step.
Current Cornell CS 4220 notes make the structural point explicit: elimination can be understood as computing a factorisation PA=LU, followed by forward and backward triangular solves. See Cornell CS 4220: Gaussian elimination (2026).
3. LU Factorisation Separates Expensive Setup From Repeated Solves
If the same matrix A is used with many different right-hand sides b, recomputing elimination from scratch wastes work. LU stores the elimination structure so later solves require only triangular substitutions.
- L stores elimination multipliers.
- U stores the resulting upper-triangular system.
- P records row permutations introduced by pivoting.
This is a powerful algorithmic pattern: perform a more expensive decomposition once, then answer many related queries cheaply.
4. Pivoting Is About Numerical Safety, Not Cosmetic Reordering
A tiny pivot can amplify rounding error. Partial pivoting swaps rows so a larger-magnitude entry is used as the next pivot. The mathematics of the exact system is preserved, but the floating-point trajectory changes substantially.
This is the moment to teach an important distinction: two algebraically equivalent procedures can behave very differently on a computer.
5. Conditioning Belongs to the Problem
An ill-conditioned problem can magnify tiny input changes even when the algorithm is excellent. A well-conditioned problem is intrinsically less sensitive. Condition numbers therefore describe the sensitivity of the mathematical problem, not the quality of one implementation.
Learners should experiment with two nearly identical systems and observe when a small change in A or b causes a much larger change in x. That experience turns “condition number” from a formula into a prediction about trust.
6. Stability Belongs to the Algorithm
A numerically stable algorithm produces a result close to the exact answer of a nearby problem. This idea of backward stability is often more useful than asking whether every intermediate floating-point value was accurate.
The teaching sequence should therefore separate three questions: Was the original problem sensitive? Was the algorithm stable? Was the final residual acceptably small?
7. Residual and Forward Error Are Not the Same Thing
After computing an approximate solution x̂, the residual is r=b−Ax̂. A small residual means x̂ nearly satisfies the equations. But for an ill-conditioned system, a small residual does not guarantee that x̂ is close to the true x.
This is a professional checkpoint: validate both the equation fit and the sensitivity context.
8. Least Squares Changes the Question
When there are more equations than unknowns, Ax=b may have no exact solution. Least squares instead asks for x that minimises the residual norm. Cornell’s 2026 notes introduce this as a minimisation problem and compare several factorisations, including QR and SVD. See Introduction to least squares.
9. QR Is the Workhorse for Least Squares
QR writes A=QR, where Q has orthonormal columns and R is triangular. Orthogonality is valuable because it preserves Euclidean lengths and usually supports stable computation.
Learners can first understand Gram–Schmidt geometrically, then progress to modified Gram–Schmidt, Householder reflections and Givens rotations. Cornell’s current notes show how QR converts least squares into a triangular solve: Least squares and QR (2026).
10. Normal Equations Are Simple but Can Square the Conditioning Problem
Forming AᵀA turns least squares into a square system, which looks attractive. But it can worsen numerical sensitivity because the condition number is effectively squared. The lesson is not “never use normal equations”; it is to understand what numerical price the simplification may impose.
11. SVD Reveals the Geometry of the Matrix
The singular value decomposition A=UΣVᵀ separates a matrix into orthogonal directions and their scale factors. Small singular values reveal directions that are weakly determined by the data. SVD therefore connects solving, least squares, rank, compression and regularisation.
A good learning activity is to gradually shrink one singular value and watch the solution become increasingly sensitive to noise.
12. Ill-Posed Problems Need Regularisation, Not More Decimal Places
If data do not strongly determine some directions, increasing floating-point precision does not repair the underlying inference problem. Techniques such as truncated SVD or Tikhonov regularisation deliberately trade exact fit for stability. Cornell’s 2026 discussion of ill-posedness and regularisation is a useful professional bridge: Ill-posedness and regularization.
13. Special Structure Should Change the Algorithm
- Symmetric positive-definite matrix → consider Cholesky.
- Sparse matrix → avoid treating every zero as stored dense data.
- Banded matrix → exploit the narrow nonzero region.
- Orthogonal matrix → use the structure directly.
- Low-rank matrix → exploit a compressed representation.
Professional numerical computing is full of such conditional choices. General-purpose methods are valuable, but structure is computational information.
14. Sparse Systems Lead to Iterative Methods
For very large sparse systems, direct factorisations may create too much fill-in or require too much memory. Iterative methods approach the answer through repeated matrix-vector operations. Conjugate Gradient is important for symmetric positive-definite systems; GMRES is a major method for more general nonsymmetric problems.
Oxford’s 2026–27 scientific-computing syllabus explicitly connects sparse systems, Conjugate Gradient, GMRES and preconditioning: Oxford Scientific Computing.
15. Preconditioning Changes the Geometry Seen by the Iterative Solver
An iterative method may converge slowly because the system is badly scaled or has an unfavourable spectrum. A preconditioner transforms the problem into one that is easier for the solver while preserving the target solution in an equivalent form.
This is a useful professional principle: sometimes the best way to accelerate an algorithm is not to change the core recurrence, but to change the representation of the problem it sees.
16. Blocking Connects Algorithms to Modern Hardware
Textbook elimination is often taught one row or column at a time. High-performance libraries reorganise work into blocks so more computation can be expressed as matrix-matrix operations that use caches, vector units and accelerators efficiently.
LAPACK’s design is built around this idea, and its guide explains orthogonal factorisations for least-squares problems: LAPACK Users’ Guide: Orthogonal Factorizations and Linear Least Squares. The existing How to Learn Cache-Efficient Algorithms article owns the broader locality and memory-hierarchy job.
17. Usually Solve the System; Do Not Form the Inverse
Beginners often learn x=A⁻¹b and then assume software should explicitly compute A⁻¹. In numerical work, solving the system through a suitable factorisation is usually more efficient and better behaved. An explicit inverse is appropriate only when the actual task requires the inverse itself.
18. Numerical Optimisation Is a Neighbouring but Different Job
Matrix factorisations frequently appear inside optimisation algorithms, but they should not be conflated. The existing How to Learn Numerical Optimisation Algorithms article owns gradient descent, Newton methods, line search and convergence. This article owns the linear-algebra machinery used to solve and diagnose matrix problems.
19. Common Learning Failure States
- Treating row operations as symbol pushing without tracking the invariant system.
- Ignoring pivoting because the exact arithmetic example happened to work.
- Confusing condition number with algorithm runtime.
- Assuming a tiny residual proves a tiny solution error.
- Using normal equations automatically for every least-squares problem.
- Computing a matrix inverse when a direct solve is the actual task.
- Ignoring sparsity, symmetry or positive definiteness.
- Comparing algorithms only by big-O time while ignoring numerical error and memory traffic.
20. A Beginner-to-Professional Learning Ladder
- Level 1: trace elimination on a 2×2 and 3×3 system.
- Level 2: perform forward and backward substitution.
- Level 3: reconstruct L and U from elimination steps.
- Level 4: demonstrate why pivoting changes numerical behaviour.
- Level 5: compute and interpret residuals and condition numbers.
- Level 6: solve least squares with QR and compare with normal equations.
- Level 7: use SVD to diagnose rank deficiency and sensitivity.
- Level 8: choose Cholesky, LU, QR or SVD from matrix structure.
- Level 9: solve a large sparse system iteratively and test preconditioning.
- Level 10: profile numerical accuracy, memory traffic and hardware utilisation together.
21. Teach the Matrix as a Changing State
For novices, display each elimination or factorisation step as a visible state transition. Ask learners to predict the next row, identify the pivot, explain the invariant and only then execute the code. Worked examples can reduce unnecessary cognitive load while learners are still building the schema for multi-step procedures.
For programming practice, adaptive Parsons problems can scaffold learners who are not yet ready to write a full implementation from scratch; see Hou, Ericson and Wang (ICER 2022). Retrieval practice and interleaving can then move the skill from recognition toward independent reconstruction; see A Spaced, Interleaved Retrieval Practice Tool.
22. Immediate, Delayed and Transfer Checks
- Immediate: trace one elimination step and explain the invariant.
- Numerical: compare the same solve with and without a poor pivot.
- Diagnostic: compute a residual and explain why it is not a full error guarantee.
- Delayed: reconstruct LU or QR from memory on a small matrix.
- Transfer: choose a method for dense, sparse, least-squares, rank-deficient and symmetric positive-definite cases.
- Professional: justify the algorithm using conditioning, stability, complexity and hardware behaviour.
23. AI Assistance Boundary
AI can generate practice matrices, explain factorisation steps and help compare solver choices. The learner should still be able to identify the matrix structure, choose a method, predict numerical failure, interpret condition and residual information, and independently verify that the computed result is credible.
Professional Direction
Advanced study includes sparse direct solvers, multifrontal methods, Krylov subspace methods, preconditioning, eigenvalue algorithms, randomized numerical linear algebra, low-rank approximation, mixed precision, communication-avoiding algorithms, GPU factorisation and distributed dense/sparse linear algebra. ACM’s current CS2023 Algorithmic Foundations frames algorithms as foundational across advanced computing; numerical linear algebra is one of the clearest places where mathematical analysis, machine representation and systems performance become inseparable.
Algorithm-learning rule: do not ask only whether the formula is correct. Ask whether the problem is well-conditioned, the algorithm is stable, the representation fits the matrix, and the computed answer survives verification.
eduKate Sengkang 