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$?

  • 2
    $\begingroup$ 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? $\endgroup$ Dec 2, 2021 at 6:52
  • 2
    $\begingroup$ 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$? $\endgroup$ Dec 2, 2021 at 8:16
  • $\begingroup$ 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. $\endgroup$ Dec 2, 2021 at 18:02
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 2, 2021 at 22:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.