# Decomposing a banded matrix

Suppose we have a linear algebra problem with a banded matrix A which has nonzero entries on the main diagonal, two nearest sub-diagonals, and two other sub-diagonals (such band structure often arises in the context of numerical solution of PDEs in 2D),

$$A x = b$$

and we write A as a sum of a 3-diagonal matrix $$T_1$$ (nonzero entries on the main diagonal and two nearest sub-diagonals), and a 3-banded matrix $$T_2$$ (nonzero entries on the main diagonal and two sub-diagonals not nearest to the main one),

$$A = T_1 + T_2$$

to attempt solving the linear system iteratively, using an efficient solver for 3-diagonal matrices,

$$T_1 x^{k+1} = b - T_2 x^k$$

One can symmetrize it by alternating $$T_1$$ and $$T_2$$ on the left-hand side.

When would this strategy be successful? If this method works, there must be a standard name for it - what is it? Is this a variation of the ADI method? What is the optimal way to decompose $$A$$ into $$T_1$$ and $$T_2$$?

• This is an interesting question, and I would like to take a look at it. I know that if you have a time derivative and alternating the derivative in x and y direction, this is exactly the system you would get, though you would have $T_1+I$ and $T_2+I$ type matrices (alternating) on the left-hand side. So the question is do you have a time-dependent problem or steady? Dec 2, 2021 at 6:52
• Would it not provide more numerical stability to always have the full diagonal on the left side? That is, decompose $A=D+S_1+S_2$, $D$ the diagonal, $S_k$ the non-diagonal bands from $T_k$, and then solve $(D+S_1)x^{k+1}=b-S_2x^k$? Dec 2, 2021 at 8:16
• This looks a lot like ADI to me. As an interesting test case, you can consider finite-difference discretization of the elliptic PDE $$-\partial_i(a^{ij}\partial_ju) = f$$ for $u$, where the (SPD) diffusivity tensor $a^{ij}$ is diagonal and has very different magnitudes along the $x$- and $y$-directions. Then see what happens if you rotate the principal axes of the diffusivity tensor. Dec 2, 2021 at 18:02
• I agree that that looks like an ADI scheme to me. If you are on a uniform x-y mesh, then you can reorder degrees of freedom in such a way that after reordering, $T_2$ is also tridiagonal. You can then apply the Thomas algorithm for tridiagonal matrices to both $T_1$ and $T_2$, alternating directions. Dec 2, 2021 at 22:28