MULTIGRID_POISSON_1D
Multigrid Solver for 1D Poisson Problem

MULTIGRID_POISSON_1D is a MATLAB 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.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

MULTIGRID_POISSON_1D is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CYCLIC_REDUCTION, a MATLAB library which solves a tridiagonal linear system using cyclic reduction.

FD1D_BVP, a MATLAB program which applies the finite difference method to a two point boundary value problem in one spatial dimension.

MGMRES, a MATLAB library which applies the restarted GMRES algorithm to solve a sparse linear system, by Lili Ju.

Reference:

1. William Briggs, Van Emden Henson, Steve McCormick,
   A Multigrid Tutorial,
   SIAM, 2000,
   ISBN13: 978-0-898714-62-3,
   LC: QA377.B75.
2. William Hager,
   Applied Numerical Linear Algebra,
   Prentice-Hall, 1988,
   ISBN13: 978-0130412942,
   LC: QA184.H33.

Source Code:

• monogrid_poisson_1d.m, solves a 1D PDE, using the Gauss-Seidel method.
• multigrid_poisson_1d.m, solves a 1D PDE using the multigrid method.
• ctof.m, transfers data from a coarse to a finer grid.
• ftoc.m, transfers data from a fine grid to a coarser grid.
• gauss_seidel.m, carries out one step of a Gauss-Seidel iteration.
• i4_log_2.m, computes the logarithm base 2 of an I4.
• timestamp.m, prints out the current YMDHMS date as a timestamp.

Examples and Tests:

• multigrid_poisson_1d_test.m, calls all the tests.
• multigrid_poisson_1d_test_output.txt, the output file.
• multigrid_poisson_1d_test01_mono.m, solves test problem 1 using Gauss-Seidel.
• multigrid_poisson_1d_test01_multi.m, solves test problem 1 using the multigrid method.
• exact1.m, the exact solution for test problem 1.
• force1.m, the forcing term for test problem 1.
• multigrid_poisson_1d_test02_mono.m, solves test problem 2 using Gauss-Seidel.
• multigrid_poisson_1d_test02_multi.m, solves test problem 2 using the multigrid method.
• exact2.m, the exact solution for test problem 2.
• force2.m, the forcing term for test problem 2.

You can go up one level to the MATLAB source codes.