I have an $n$ by $n$ $k$-banded matrix for which I calculated the LU decomposition via Matlab. Now, I want to solve the system to find the resulting vector and compare the operation count with another algorithm.

Online I have found many sources explaining the computational complexity of the forward and back substitution to be $\mathcal O(N^2)$. However, I could not find much for a $k$-banded matrix. I assume that it should take less operations than $N^2$, because the zeros do not have to be considered in the calculation, and you only need to consider 4 elements per row.

Could someone help me derive the operation count for a $k$-banded matrix for the forward and backward substitution?



You must log in to answer this question.

Browse other questions tagged .