Why solve Ax = b with an LU factorization instead of computing the inverse of A?
answer
- count how many right-hand sides you have
- factor once, reuse many times
- triangular systems solve by substitution
- the one-off cost versus the per-solve cost
- inverting does roughly three times the work
basics
~20 sFactoring A into lower and upper triangular factors costs about a third of what forming the inverse costs and is more accurate. It is also reusable: each new right-hand side then needs only two cheap triangular solves.
solid answer
~50 sLU factorization writes `A = LU` with `L` lower triangular and `U` upper triangular, so `Ax = b` becomes two easy problems: solve `Ly = b` by forward substitution, then `Ux = y` by back substitution. The factorization costs about two thirds of `n^3` operations for an n-by-n matrix, while explicitly forming `A^-1` costs roughly three times that and then still needs a matrix-vector product. Accuracy is the stronger argument: the inverse route performs more arithmetic on already-rounded numbers and amplifies error, whereas substitution on the factors is backward stable with partial pivoting. The decisive practical point is reuse - if you must solve with many right-hand sides, you factor once and pay only about `n^2` work per solve. In practice you almost never need `A^-1` itself; you need the action of `A^-1` on a vector.
go deeper
Recall that solving is done by factoring and substituting, not by building an inverse, and that a triangular system is easy because each equation introduces one new unknown at a time.
Explain the mechanics end to end: what L and U are, the forward-then-back substitution pass, the cubic factorization versus quadratic solve cost, and what partial pivoting protects against.
Show the operational judgment - recognising a many-right-hand-sides workload, caching a factorization across calls, picking Cholesky when the matrix is symmetric positive definite, and knowing when a solver's singularity warning means the model is wrong rather than the code.
Frame the tradeoff at system level: where factorizations live and get invalidated, when a cubic factorization becomes the bottleneck that pushes you to iterative or structure-exploiting methods, and how much accuracy the organisation is buying for that cost.
## The setup Given a square, invertible matrix `A` and a right-hand side `b`, mathematics says `x = A^-1 b`. Computation says: do not build `A^-1`. This gap between the algebraic notation and the numerical practice is exactly what the question probes. ## What LU factorization is Gaussian elimination, done bookkeeping-first, factors `A` into `A = LU`, where `L` is lower triangular with ones on its diagonal and `U` is upper triangular. `U` is what elimination leaves behind; `L` records the multipliers you used along the way. In floating point you additionally permute rows to put the largest available entry in each pivot position - **partial pivoting** - so the true statement is `PA = LU` for a permutation matrix `P`. Once you have the factors, solving is trivial in two stages: - **Forward substitution** on `Ly = Pb`: the first equation involves only `y1`, the second only `y1` and `y2`, and so on down. - **Back substitution** on `Ux = y`: the last equation involves only `xn`, and you climb upward. Each substitution touches roughly half of an n-by-n triangle, so each costs on the order of `n^2` operations. ## The cost argument The factorization itself is the expensive part, about `(2/3) n^3` arithmetic operations. Explicitly computing `A^-1` amounts to solving `Ax = e_j` for all n unit vectors, which lands near `2 n^3` - about three times more work - and you still have to multiply `A^-1` by `b` afterwards. So even for a single right-hand side, the factor-and-substitute path is cheaper. ## The accuracy argument Every floating-point operation rounds. Building `A^-1` runs a full elimination and then commits the result to memory as n^2 rounded numbers; multiplying by `b` rounds again, and the errors of all n columns of the inverse mix into every entry of the answer. Substitution on `L` and `U` performs less arithmetic on fewer rounded intermediates. Formally, LU with partial pivoting is backward stable in practice: the computed `x` is the exact solution of a slightly perturbed system `(A + E)x = b` with a tiny `E`. The explicit-inverse route carries no comparable guarantee and is measurably worse on hard matrices. Neither method rescues an inherently sensitive matrix - that is a property of `A` itself - but the inverse route adds avoidable damage on top. ## The reuse argument, which usually decides it Many real problems keep `A` fixed and vary `b`: a structural model loaded in a hundred different ways, a time-stepping scheme with the same operator every step, a calibration matrix applied to each new batch of readings. Factor once at `(2/3) n^3`, then pay only about `2 n^2` per right-hand side. With n = 1000 and 500 right-hand sides, the factorization is done once and the 500 solves cost a small fraction of a single re-elimination each. Re-running elimination from scratch on every augmented system throws that away, and forming the inverse pays a higher one-off price for a worse answer. ## Choosing the right factorization - **General square `A`**: LU with partial pivoting. - **Symmetric positive definite `A`** (symmetric, and `z^T A z > 0` for every nonzero `z`): **Cholesky**, `A = LL^T`. It exploits symmetry to halve the work, near `(1/3) n^3`, needs no pivoting for stability, and fails cleanly - the algorithm hits a non-positive number under a square root - precisely when the matrix is not positive definite. That failure doubles as a positive-definiteness test. - **Triangular or banded `A`**: substitution directly, or a banded factorization that never touches the zeros. ## When you genuinely want the inverse Almost never for solving. You want it when the entries of `A^-1` are themselves the object of interest - for instance when a specific diagonal entry carries meaning for a downstream calculation - and even then, computing selected columns by solving against unit vectors beats forming the whole thing. ## What a good answer sounds like Name the two triangular solves, give the rough cost split between the one-off factorization and the per-solve substitution, mention partial pivoting as the thing that keeps elimination stable, and finish on reuse across right-hand sides. Saying "never invert a matrix" as a slogan without any of that reasoning is exactly the shallow answer interviewers are listening for.
- What does partial pivoting add to LU, and why is it needed?It swaps rows so the largest available entry in the current column becomes the pivot, giving `PA = LU`. Without it, a pivot that is zero stops elimination outright and a pivot that is merely tiny produces huge multipliers that magnify rounding error. Pivoting keeps every multiplier at most one in magnitude, which is what makes the factorization stable in practice.
- A is symmetric positive definite. What changes in your approach?Use Cholesky, `A = LL^T`, instead of LU. Symmetry means you only compute one triangle, so the cost drops to roughly half of LU, and no pivoting is required for stability. Solving is still forward then back substitution, now against `L` and `L^T`. As a bonus, the factorization only succeeds if the matrix really is positive definite, so it doubles as a check.
- You need to solve Ax = b for 500 different right-hand sides with the same A. What is the plan?Factor `A` once, then run 500 pairs of triangular solves. The `(2/3) n^3` factorization is paid a single time and each subsequent solve costs only about `2 n^2`. Re-eliminating per right-hand side repeats the cubic cost 500 times, and forming the inverse pays about three times the factorization cost up front for a less accurate result.
saying these in an interview costs you the question
- Saying x = A^-1 b is how you would actually compute it
- Claiming the inverse is faster because it is computed once
- Not knowing forward and back substitution cost only n squared
- Reciting never invert a matrix with no reason behind it
- Using LU on a symmetric positive definite system and ignoring Cholesky
- Believing pivoting is only about avoiding an exactly zero pivot