8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The form of the matrix will not prevent you from running into a problem with the matrix (or a submatrix) being singular, but I don't read the problem as asking about what might go wrong. Instead by asking for an "efficient algorithm... without swapping any rows and columns", it seems that your "[c]lassic elimination" without pivoting would be a reasonable approach. Do you see how to estimate the complexity of this method? $\endgroup$ – hardmath Nov 24 '13 at 21:57
4
$\begingroup$

It is not difficult to determine the complexity of a straightforward elimination/reduction to upper triangular form. Note that the initial matrix:

$$ \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} $$

becomes after one step of elimination:

$$ \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\ 0 &a_2 - \frac{b_1 c_2}{a_1}&b_2&0&\vdots&-\frac{d_1 c_2}{a_1}\\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}\\0&-\frac{b_1 d_2}{a_1}&\cdots&0&c_n&a_n-\frac{d_1 d_2}{a_1}\end{bmatrix} $$

The cost of this step is constant $O(1)$, and it leaves a $(n-1)\times(n-1)$ cyclic three-diagonal submatrix in the lower right corner. Full reduction will thus entail $O(n)$ cost. To solve a linear system one might perform the same operations on the right-hand side, also an $O(n)$ cost. One also has then to perform a backsolve with an upper triangular matrix having at most three nonzero entries per row, another $O(n)$ task. So that represents the complexity of solving systems with such coefficient matrices.

$\endgroup$
  • 1
    $\begingroup$ +1, thanks, but what if $a_1=0$? Then the first step will differ. And there can be complications further. Isn't that a problem? $\endgroup$ – xan Nov 25 '13 at 16:06
  • $\begingroup$ It is a limitation of Gaussian elimination without pivoting that when zeros appear in places where we want to (in essence) produce a leading one, then we are stuck! The idea of partial pivoting is trying to get around this by swapping rows tactically (resp. full pivoting swapping rows and columns). But the problem statement forbids swapping rows or columns, which I interpret as trying to keep your analysis of complexity as simple as possible. Certain conditions (like diagonal dominance) may hold and guarantee success without pivoting. $\endgroup$ – hardmath Nov 25 '13 at 16:52

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.