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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.