MULTIGRID_POISSON_1D, a C++ library which applies a multigrid method to solve the linear system associated with a discretized version of the 1D Poisson equation.
The 1D Poisson equation is assumed to have the form
-u''(x) = f(x), for a < x < b u(a) = ua, u(b) = ub
Let K be a small positive integer called the mesh index, and let N = 2^K be the corresponding number of uniform subintervals into which [A,B] is divided. Assigning a value U(I) to each of the N+1 equally spaced nodes with coordinate X(I), we approximate the equation by
-U(i-1) + 2 U(i) - U(i+1) ------------------------- = f( X(i) ), 1 < I < N+1 h^2 U(1) = ua, U(N+1) = ub.
It remains to solve the linear system for the desired values of U. This could be done directly, or iteratively. An iterative method such as Jacobi, Gauss-Seidel or SOR might be suitable, but experience shows that the convergence rate of these iterative methods decreases drastically as the value of K is increased - that is, as a more refined and accurate answer is sought.
The multigrid method defines a nested set of grids, and corresponding solutions, to the problem, and applies an iterative linear solver. By transfering information from one grid to a finer or coarser one, a more rapid convergence behavior can be encouraged.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
MULTIGRID_POISSON_1D is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.
CYCLIC_REDUCTION, a C++ library which solves a tridiagonal linear system using cyclic reduction.
MGMRES, a C++ library which applies the restarted GMRES algorithm to solve a sparse linear system, by Lili Ju.