15
$\begingroup$

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix.

Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the number of operations for the first column is $2n(n-1)$. For the second column, we have $n-1$ additions and $n-1$ multiplications, and we do this for $(n-2)$ rows giving us $2(n-1)(n-2)$. Therefore, the total number of operations required for the full decomposition can be written as

$$ \sum_i^n 2(n-i) (n-i+1) $$

How do we get from this sum to a total cost of $\frac{2}{3}n^3$?

$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

An easy transformation ($j = n-i+1$) easily shows that \begin{align} \sum_{i=1}^n 2(n-i) (n-i+1) &= 2 \sum_{j=0}^{n-1}j(j+1)\\ &= 2 \sum_{j=0}^{n-1}(j^2+j)\\ &= 2 \left(\frac{1}{3} n^{3} - \frac{1}{3} n\right) \end{align}

Then, since we are interested only in the asymptotic behaviour, we drop the $\frac{2}{3}n$ part, and what's left is $\frac{2}{3} n^{3}$.

$\endgroup$
3
  • 2
    $\begingroup$ I get it up to the $2 \sum_{j=0}^{n-1} (j^2 + j)$ .. but then I don't see how did you get the next step. I must be missing something. $\endgroup$
    – amaatouq
    Commented Jun 18, 2015 at 22:19
  • 2
    $\begingroup$ You can use the classical formulas for the sums of the first $n$ squares and the first $n$ integers : $$ \sum_0^n{k^2} =\frac{1}{6} {\left(2 n + 1\right)} {\left(n + 1\right)} n $$ and $$ \sum_0^n{k} =\frac{n(n+1)}{2}$$ and adapt them to $n-1$ $\endgroup$
    – lmsteffan
    Commented Jun 18, 2015 at 22:29
  • $\begingroup$ I am a little confused. Why don't any of the answers here also consider the part where we have to also find the upper triangular matrix? $\endgroup$
    – user681443
    Commented Feb 28, 2020 at 1:58
4
$\begingroup$

Below is the gist. Hope the loose but cleaner notation can help our memory.

$\sum_i^n 2(n-i) (n-i+1)\approx2\sum n^2\approx2\int x^2dx\approx\frac{2}{3}x^3$

$\approx$ is in the sense of top term coefficient.

$\endgroup$
2
$\begingroup$

Well, $$ 2\sum_i^n (n-i)(n-i)+(n-i) = 2\sum_i^n (n-i)^2+2\sum_i^n(n-i) $$

Now, let's reindex these sums backwards so it's pretty. $$ 2\sum_i^n (i)^2+2\sum_i^n(i) $$

Now, if you know a little induction (or wolfram alpha) you can prove that $$ \sum_i^n (i)^2 = n^3/3+n^2/2+n/6 $$ and $\sum_i^n i$ is at worst $n^2$. So we have $\frac{2}{3}n^3$

$\endgroup$
2
  • 1
    $\begingroup$ I don't see how you get that $\sum_i^n (i)^2 = n^2/3 + n^2/2+n/6$ $\endgroup$
    – amaatouq
    Commented Jun 18, 2015 at 22:22
  • 3
    $\begingroup$ Here math.stackexchange.com/questions/48080/… is the MSE discussion about it. There are many proofs. One proof is by induction using the formula for $\sum_i^n i$ as a starter. There are some number theoretic proofs. It's a good fact to know. $\endgroup$
    – Zach Stone
    Commented Jun 18, 2015 at 22:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .