Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$ 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.

share|improve this question
    
add comment

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
$$ 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 Hints –  corium May 25 '11 at 17:15
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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