1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – clocktower Feb 12 '16 at 18:20
  • $\begingroup$ I'm sorry. I don't follow what you're saying. $\endgroup$ – David_T Feb 12 '16 at 18:24
  • $\begingroup$ I'll respond ASAP. $\endgroup$ – clocktower Feb 12 '16 at 18:26
  • $\begingroup$ Perfect. Thank you so much! $\endgroup$ – David_T Feb 12 '16 at 18:27
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.