Factor Once, Solve Fifty Times

A pipeline has to solve $A\mathbf{x} = \mathbf{b}$ for the same $100 \times 100$ matrix $A$ but $50$ different right-hand sides $\mathbf{b}_1, \dots, \mathbf{b}_{50}$ .

Two standard cost facts you may use, counted in floating-point operations (flops) for an $n \times n$ matrix:

Operation	Cost
Gaussian elimination reducing $A$ to triangular form (equivalently, producing $A = LU$ )	$\approx \dfrac{n^3}{3}$
One forward substitution plus one back substitution, given $L$ and $U$	$\approx n^2$

Plan A runs the full elimination from scratch for every right-hand side.

Plan B factors $A$ once, then reuses $L$ and $U$ for all $50$ solves.

Roughly how many times less work does Plan B do than Plan A?

Factor Once, Solve Fifty Times

Hints