Is there an efficient way to solve a system of linear equations with an almost tridiagonal sparse matrix?

Question

I have a problem where I need to solve a linear system of equation $Ax = b$ where the matrix A is almost tridiagonal, except for elements on the last two columns (see below).

I need to solve such a system at each time step and the matrix changes every time but keeps the same form. For the moment, I am using a LU decomposition to solve this system (Wikipedia), but I thought since the matrix is very sparse and almost tridiagonal, there would be a faster way. Could there be a slightly modified version of the Thomas algorithm for example?

I have tried to use Matlab's gmres function but it is not faster. Please note that my matrix is neither symmetric nor positive definite, so it limits the options that I have.

Here's the shape of the matrix in question:

Answer 1

At the bottom you have two equations for the last two variables. Solve that system and substitute the result to eliminate the last two columns; then you have a tridiagonal system.