# Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?

I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with

$$\mathbf{A}=\mathbf{T}+\mathbf{C}$$

where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-only matrix:

$$\mathbf{C}=\begin{pmatrix} 0& 0 & \cdots & 0 & c\\ 0 & \ddots & & & 0\\ \vdots & & \ddots & & \vdots\\ 0 & & & \ddots & 0\\ c & 0 & \cdots & 0& 0 \end{pmatrix}$$

What are some efficient algorithms for solving this system of linear equations (i.e. solving for $\mathbf{x}$)?

• For $C$ clearly we don't need to store the zeros so just store $c_{1,n}$ and $c_{n,1}$ and for $T$ you need just store the bandwidth elements since it is tridiagonal the bandwidth will be $3$. When you do the computation $A= T + C$ computationally it's only $O(n)$. For the storage of $T$ take advantage of the fact that $T$ is symmetric. If none of this makes sense let me know. – Wolfy Aug 31 '16 at 20:21
• @Wolfy You've only told me about how I could/should store the matrix $\mathbf{A}$. You've made no mention of how one might go about solving the linear system, or solving for $\mathbf{x}$ given the matrix $\mathbf{A}$ and the vector $\mathbf{b}$. I obviously would not like to calculate $\mathbf{A}^{-1}$ through an elementary method. – Arturo don Juan Aug 31 '16 at 20:39
• Right sorry hard to see sometimes on a mobile phone. Do you know anything about $LU$ factorization? You can solve $A = LU$ then to solve for $x$ you use a backward and forward solve. Wikipedia explains it in a simple way. – Wolfy Aug 31 '16 at 20:42

• The problem with this approach is that the matrix $\mathbf{C}$ is both singular (when the dimension is greater than 2) and cannot be written as an outer product of vectors. Unless I'm looking at this from the wrong angle, this method doesn't seem to helpful. :( – Arturo don Juan Aug 31 '16 at 23:12