$ 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 4×4 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.
Best Answer
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