Preconditioning the $[1 \quad-2 \quad 1]$ Finite Difference matrix

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

• 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. – Maxim Umansky Jul 20 '20 at 21:32
• 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. – Wolfgang Bangerth Jul 20 '20 at 22:46
• 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. – Abdullah Ali Sivas Jul 20 '20 at 22:56
• @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 ? – Vefhug Jul 21 '20 at 6:41
• @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). – Wolfgang Bangerth Jul 21 '20 at 23:46