3
$\begingroup$

$ A \in \mathbb{R}^{n x n} $ of a tridiagonal matrix and $b \in \mathbb{R}^{n}$

What is the least number of arithmetic statements as a function of n to solve $A*x = b$?

$ \left( \begin{matrix} a_{1,1} & a_{1,2} & 0 & \ldots & 0\\ a_{2,1} & a_{22} & a_{2,3} & \ldots & \vdots\\ 0 & a_{3,2} & \ddots &\ddots & 0\\ \vdots & \ddots & \ddots & \ddots & a_{n-1,n}\\ 0 & \ldots & 0 & a_{n,n-1} & a_{n,n} \end{matrix} \right) $

for LU in 4x4 tridiagonal matrix I need 3 to zero operations -> n-1 for LU decomposition

Gaussian Elimination: $((n-1)n(n+1))/3 + ((n-1)n)/2$ subtractions/Multiplications and $(n(n+1))/2$ divisions.

Are the first steps correct?

What is the correct solution?

Thanks.

  • 0
    http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm2011-05-25

2 Answers 2

0

Not quite - using Gaussian elimination naively ends up drastically increasing the number of steps required. Naive Gaussian Elimination accounts for clearing every single non-diagonal element. But here, they are already clear in all but two other diagonals!

Because this has the feel of a homework question in a numerical analysis course, I won't give an explicit answer. (If it is a homework question, you should tag it as such). But I will say that it is possible to solve the system in less than 6n (even 5n, if you are witty) operations. That's not $n^2$!

HINT Now, to get to the solution, think of modifying Gaussian Elimination so that you don't attempt to clear out empty values. Try it on a 5 by 5 matrix or something, and count how many operations you need then.

  • 0
    $ r_{1} = c_{1}/b_{1}, r_{i} =c_{i}/(b_{i} − a_{i}r_{i}−1) ,i = 2, 3, . . . , n − 1 $ $ q_{1} = d_{1}/b_{1}, q_{i} = (d_{i} − a_{i}q_{i}−1)/(b_{i} − a_{i}r_{i}−1), i = 2, 3, . . . , n$ $X_{n} = qX_{n}, X_{i} = q_{i} − r_{i}X_{i}+1, i = n − 1, n − 2, . . . , 1$ solution = 2n Dev and 3n Mul =) thx for the Hints2011-05-25
1

For a banded system of size $N$ with bandwidth $B$, the cost is $\mathcal{O}(B^2 N)$.

For a triangular system of size $N$ with bandwidth $B$, the cost is $\mathcal{O}(N^2)$.

For a complete linear dense system of size $N$, the cost is $\mathcal{O}(N^3)$.

In general, you should never do a naive gaussian elimination when you have some sparsity structure.

Here is a link with the costs for different sparse matrices