factor-once-solve-many

Imagine you have to unlock the same door for a hundred different people. You could fashion a fresh key from scratch each time — or cut one good key once and then hand it around. Factor-once-solve-many is that second strategy applied to linear systems: when you must solve A x = b for the same matrix A but many different right-hand sides b, you do the expensive work on A a single time and reuse it for every b.

Concretely, the expensive part of solving A x = b is the elimination, which produces the LU factorization P A = L U at a cost of about 2 n^3 / 3 flops. But once L and U exist, solving for any new b is just two triangular solves — forward substitution L y = P b, then back substitution U x = y — costing only about n^2 flops apiece. So the first solve costs O(n^3), and every subsequent solve with a new b costs only O(n^2). For k right-hand sides you pay one cubic factorization plus k cheap quadratic solves, instead of k full cubic eliminations.

This is one of the most important practical reasons LU (and Cholesky) factorizations are computed and stored rather than thrown away. It shows up everywhere: implicit time-stepping reuses the same factorization at every step, optimization solves with the same matrix and updated gradients, and inverse problems hit the same A repeatedly. It is also why you never solve A x = b by computing the inverse: forming A inverse is more work AND less accurate than just keeping the factorization and reusing it. The one caveat: if A itself changes, the saved factorization is stale and must be recomputed (or cheaply updated).