Let $A$ be the well known tridiagonal matrix coming from the 1D Finite difference discretization of the Laplacian, with stencil $\frac{[1 \quad-2 \quad 1]}{h^2}$.

The system $Ax = b$ is very large, so an iterative method must be used. Also, it is symmetric and positive definite, so I could employ PCG to solve it. The big question is: what preconditioner should I set? I've searched on the web but, surprisingly, I couldn't find anything.

Any reference, MatLab/C++ code or anything in between would be highly appreciated.

Best regards

  • 3
    $\begingroup$ You don't need an iterative method here; for a tridiagonal matrix use the standard sweeping method; it is exact and the computational cost of it scales linearly with the matrix size. See en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm. $\endgroup$ Jul 20, 2020 at 21:32
  • 2
    $\begingroup$ That's right -- in 1d, just use the Thomas algorithm to solve for the tridiagonal matrix. In higher dimensions, older codes would use Gauss-Seidel or SSOR, whereas the consensus today is that algebraic and geometric multigrid are the only truly good preconditioners. $\endgroup$ Jul 20, 2020 at 22:46
  • $\begingroup$ I am going to agree with Wolfgang Bangerth, with some addition. AMG and GMG are great for some problems. For other problems, either we don't know or monolithically using MG methods is a bad idea. For Poisson/Laplace problems usually throwing a blackbox AMG solver -like BoomerAMG- will be more than enough. $\endgroup$ Jul 20, 2020 at 22:56
  • $\begingroup$ @WolfgangBangerth exactly, I was going to ask for the 2D/3D/ND... case, when the matrix is sum of kronecker products. Just one last question: I'm learning PETSc at the moment, do you think that using the PETSc Amg routine is the "best" choiche I could do at the moment, in terms of efficiency ? $\endgroup$
    – Vefhug
    Jul 21, 2020 at 6:41
  • $\begingroup$ @Vefhug Yes. Use the interfaces to the 'hypre' package to precondition your Laplace matrix. That's the most efficient method accessible from PETSc, at least for large problems (100,000 or more unknowns). $\endgroup$ Jul 21, 2020 at 23:46


Your Answer

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