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?