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
Best Answer
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.