I have this problem in my textbook:

Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\c_2&a_2&b_2&0&\vdots&0\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\d_2&0&\cdots&0&c_n&a_n\end{bmatrix} without swapping any rows and columns. Estimate complexity.

And I don't know how to approach this. Classic elimination would work in very efficient $O(n)$ time with this matrix, but the problem is when, let's say, I want to eliminate $c_{2}$ with $1$-st row that is add to second row $\frac{-c_{2}}{a_{1}}\cdot \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1 \end{bmatrix}$ and when $a_1=0$. I can't do that, and even if $a_1\neq 0$ then the same problem can occur somewhere in the middle of this proccess. Moreover, as the problem text states, I am not allowed to swap any rows or columns, so I don't know if this approach can be somehow fixed. Can anybody help?


If I understand your problem correctly, you have the answer at http://nikolavitas.blogspot.com.es/2013/08/three-diagonal-periodic-system-of.html

The algorithm is still very efficient as it uses 2 times Gaussian elimination at n-1 x n-1 matrix.

I coded the method in IDL. You won't have much trouble to translate it to any other language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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