LU factorization and solve costs ($\frac{2}{3}{n}^3+2r{n}^2$)

For classical dense Gaussian elimination over the real numbers, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. At step $k$, there are $n-k$ elimination multipliers to divide out and $(n-k{)}^2$ remaining entries, each requiring one multiplication and one subtraction. Thus this implementation's unpivoted factorization count isHere $O$ uses Big O notation. Partial pivoting adds $O(n^2)$ comparisons and row movement, leaving the leading arithmetic count unchanged. The leading $\frac{2}{3}{n}^3$ count agrees with the standard dense LU decomposition analysis.^[ref]

With unit $L$, forward substitution uses $n(n-1)$ arithmetic operations. Back substitution uses another $n(n-1)$ plus $n$ diagonal divisions. Together these cost $2n^2-n$ per right-hand side; applying a stored row permutation moves $n$ entries and requires no scalar arithmetic. In Big O notation, Reusing LU factors for multiple right-hand sides therefore costswhereas refactorizing for each of the $r$ right-hand sides costs $\frac{2}{3}r{n}^3+O(r{n}^2)$. For $n=1000$ and $r=10$, the leading counts are about $6.87\times 10^8$ versus $6.69\times 10^9$ arithmetic operations, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized matrix multiplication also affect speed.^[ref]