Comparing the cost with direct solvers

We see from the above results that the Jacobi algorithm reduces the error quite

slowly in each iteration. For a general matrix of size $nn,$ Gaussian elimination

$($or Cholesky factorization$)$ costs $O(n^3)$ whereas each iteration of Jacobi costs $O(n^2).$

So$,$ for a system of size $n=100,$ if we perform more than $100$ Jacobi iterations, we are

doing more work than the direct solvers $($Gaussian$/$Cholesky$)$ Ouch! However,

we now note that the matrix A has a special structure.

$($a$)$ How many non$-$zeros does the matrix A have in each row?

$($b$)$ Based on the answer to part $($a$),$ how does the cost $($in big$-$Oh notation$)$ of per$-$

forming the Jacobi algorithm change if you could take advantage of this spar$-$

sity? Do you think either of your implementations $($component$-$wise or vector$-$

update$)$ takes advantage of the sparsity?

$($c$)A$ is an $m-$banded matrix, where $m=2P=2\sqrt[\phantom{2}]{n}.$ What is the cost in construct$-$

ing an LU factorization using the special algorithm for an $m-$banded matrix?

Give your answer in terms of $O(n^{})$ and justify your value of $.$

$($d$)$ Based on your result for parts $($b$)$ and $($c$),$ what is the number of iterations for

which the faster Jacobi algorithm $($from part $($b$))$ becomes more expensive $($in

terms of big$-$Oh notation$)$ than the fast direct solver $($from part $($c$))$ if $n=100?$