# Operation count, LU-decomposition

I'm having trouble with an assignment question. The question is as follows:

Determine the total number of multiplications and divisions (as a function of $n$) required to compute the LU-decomposition of a general $n \times n$ matrix $A_n$, whose entries $a_{ij}$ satisfy $a_{ij} = 0$ if $j ≤ i − 2$. (Draw a schematic picture of such a matrix, say for the case $n = 5$, to see its zero structure).
Also determine the number of multiplications and divisions required to solve the lower-triangular system $L_g = f$ and for solving the upper-triangular system $U_x = g$.

I drew the matrix for the case where $n = 5$, but other than that I don't know how to solve this problem. Can someone help explain it to me?

Thank you

• Set up your $A = LU$ with $LU$ multiplied out. Then, you have a one-to-one correspondence between the entries of $A$ and the entries of $LU$. Deduce how to find each entry of $L$ and each entry of $U$ via this correspondence. This should lead you to an total number of operations needed to perform the decomposition. – clocktower Feb 12 '16 at 18:20
• I'm sorry. I don't follow what you're saying. – David_T Feb 12 '16 at 18:24
• I'll respond ASAP. – clocktower Feb 12 '16 at 18:26
• Perfect. Thank you so much! – David_T Feb 12 '16 at 18:27

I will show an example of the operations count for a simple $LU$ factorization of a $3\times 3$ matrix $A$.

$$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} = LU$$

Multiplying this out, we have $$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix}u_{11} & u_{12} & u_{13} \\l_{21}u_{11} & l_{21}u_{12} + u_{22} & l_{21}u_{13} + u_{23} \\ l_{31}u_{11} & l_{31}u_{12} + l_{32}u_{22} & l_{31}u_{13} + l_{32}u_{23} + u_{33} \end{bmatrix} = LU$$

Observe the one-to-one correspondence from entries of $A$ to $LU$. Let $(s,m)$ be the number of subtractions and the number of multiplications, respectively. Here, $n = 3$.

Operations for $U$:

$u_{1j}$ for $j=1,2,3$

• $u_{11} = a_{11}$

• $u_{12} = a_{12}$

• $u_{13} = a_{13}$

So, no operations needed.

$u_{2j}$ for $j = 2,3$:

• $u_{22} = a_{22} - l_{21}u_{12}$ - $(1,1)$

• $u_{23} = a_{23} - l_{21}u_{13}$ - $(1,1)$

So, 2 subtractions, i.e. $n-1$, and 2 multiplications, i.e. $n-1$

Finally, $u_{33} = a_{33} - l_{31}u_{13} - l_{32}u_{23}$ - $(2,2)$

So, 2 subtractions, i.e. $(n-2)\cdot 2$, and 2 multiplications, i.e. $(n-2)\cdot 2$.

So, for the $3\times 3$ case, we have 4 substractions and 4 multiplications to find $U$. We can generalize this for any $n$.

Operations for $L$:

Preform same procedure.

Now, apply this same style procedure to the special $A$ matrix as described in your problem and generalized for any $n$. Hope this helps.

• Will check this out ASAP. Thank you!! – David_T Feb 12 '16 at 20:29
• When you do $u_{22} = a_{22} - l_{21}u_{21}$, isn't it supposed to be $u_{12}$? – David_T Feb 13 '16 at 15:26
• Yes, my mistake. – clocktower Feb 13 '16 at 15:53
• No problem. Thank you – David_T Feb 13 '16 at 16:11
• How would I get the total number of operations at the end? Do I just sum up everything together? – David_T Feb 13 '16 at 16:18