= LU factorization and solve costs
{c}
{title2=$\tfrac23n^3+2rn^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 is
$$
F(n)=\sum_{k=1}^{n-1}\bigl((n-k)+2(n-k)^2\bigr)=\frac{n(n-1)(4n+1)}6=\frac23n^3+O(n^2).
$$
Here $O$ uses <Big O notation>. <Partial pivoting> adds $O(n^2)$ comparisons and row movement, leaving the leading arithmetic count unchanged. The leading $\tfrac23n^3$ count agrees with the standard dense <LU decomposition> analysis.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others>[§2.5.2, Definition 2.5.2; §2.5, equations (2.5.7)–(2.5.8) and Theorem 2.5.1; lower-order counts depend on implementation]{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 costs
$$
\frac23n^3+2rn^2+O(n^2+rn),
$$
whereas refactorizing for each of the $r$ right-hand sides costs $\tfrac23rn^3+O(rn^2)$. For $n=1000$ and $r=10$, the leading counts are about $6.87\times10^8$ versus $6.69\times10^9$ <arithmetic operations>, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized <matrix multiplication> also affect speed.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others>[§2.5.2, Important note after Definition 2.5.2: flop counts are a rough runtime model; the numerical comparison here is an original calculation]{ref}
Back to article page
