# Sparse linear system of certain type

Let $n_1,n_2 \in \mathbb{N}$ and $n=n_1n_2$ and $b\in \mathbb{R}^n$. I have a SPD-matrix $A=(a_{i,j})\in \mathbb{R}^{n \times n}$ with $a_{i,j}=0$ if $|i-j| \notin \{0,1,n_1\}$. Can we solve the system $Ax=b$ in time $\mathcal{O}(n)$? I work with Matlab. The Backslash operator does not seem to scale linearly in $n$. What about if $A=(a_{i,j})\in \left(\mathbb{R}^{d \times d}\right)^{n \times n}$ where $d\in \mathbb{N}$ is a fixed integer? The problem arises from an image analysis problem with an image of size $n_1 \times n_2$ resp. $n_1 \times n_2 \times d$. The hessian of a certain functional has nonzero entries only for neighboring pixels. That's why my matrix has this special structure.

You have the equivalent of the 5-point stencil in finite differences. The general answer is that you cannot solve this in $O(n)$ without making use of other properties of the matrix and/or its entries. Using the sparsity structure, by itself, is not enough.
For example, if the matrix arises from the Laplace or another symmetric and elliptic equation, then you can use multigrid solvers to obtain $O(n)$ complexity. On the other hand, you get the same sparsity pattern if you discretize the high-frequency Helmholtz equation (with the bad sign) using the five-point stencil, and for that equation multigrid does not help.