I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns:
$$ \begin{bmatrix} {b_1 } & {0 } & \ldots & {0 } & {a_1 } & {0 } & \ldots & { 0} \\ {0 } & {b_2 } & {0 } & { } & {0 } & {a_2 } & {0 } & \vdots \\ \vdots & {0 } & {b_3 } & {0 } & { } & {0 } & \ddots & {0 } \\ {0 } & { } & {0 } & {b_4 } & {0 } & { } & { } & {a_{n-k}} \\ {a_1 } & {0 } & { } & {0 } & {b_5 } & {0 } & { } & {0 } \\ {0 } & {a_2 } & {0 } & { } & {0 } & {b_6 } & { } & \vdots \\ \vdots & { } & \ddots & { } & { } & { } & \ddots & {0 } \\ {0 } & \ldots & {0 } & {a_{n-k}} & {0 } & \ldots & {0 } & {b_n } \\ \end{bmatrix} \cdot \begin{bmatrix} {x_ 1 } \\ {x_ 2 } \\ {x_ 3 } \\ {x_ 4 } \\ {x_ 5 } \\ {x_ 6 } \\ \vdots \\ {x_n } \\ \end{bmatrix} = \begin{bmatrix} {d_ 1 } \\ {d_ 2 } \\ {d_ 3 } \\ {d_ 4 } \\ {d_ 5 } \\ {d_ 6 } \\ \vdots \\ {d_n } \\ \end{bmatrix} $$
I'm aware of the TDMA algorithm for solving non-symmetric tridiagonal systems, but I haven't come across an existing implementation that allows the upper and lower diagonals to be arbitrarily offset from the main diagonal.
In addition, I'm wondering whether it would be possible to take advantage of the symmetry of the matrix to solve the system faster than with standard TDMA.
Please excuse the naivety of my question!
Here's a bit more information about $M$:
- $M$ is the Hessian matrix for a large nonlinear system I'm trying to solve via an interior point method
- It is always positive definite
- It is constructed like this: $ M = B^{T} \cdot A \cdot B + C$, where $A$ and $C$ are $(n-k, n-k)$ and $(n, n)$ diagonal matrices respectively, and $B$ is an $(n-k, n)$ upper bidiagonal matrix.
I don't think there's much more I can tell you without getting into to much depth, but if you're interested I'm trying to implement the algorithm described in this paper.