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.

  • $\begingroup$ Thank you very much for the answer. Unfortunately I am not familiar with multigrid, so I still have some questions: is SPD sufficient for multigrid to be applicable? Is there any library for matlab which solves a linear equation with multigrid? The one's which I have found by googling are slow or use the pde-framework. $\endgroup$
    – Markus
    Mar 5 '15 at 12:14
  • $\begingroup$ I don't think that SPD is enough in practice. One could think of Laplace equation with strongly varying coefficients, for example. As for implementations: Multigrid makes use of knowledge of where the matrix came from. Once you give a solver only the matrix, you lose the advantage of being able to use extra information. $\endgroup$ Mar 6 '15 at 12:58

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.