MGCG Method

						November 12, 1999


***     Copyright notice


Copyright(C) 1999, 2000 Osamu Tatebe, all rights reserved, no
warranty.

This software is a free software.  All rights of this software belong
to Osamu Tatebe.  You can redistribute this whole package as it is if
you do not modify and inform me by E-mail.


*** 1.  Description


MGCG method is a conjugate gradient with multigrid preconditioner.
This library solves a linear system of equations whose coefficient
matrix has five diagonals that typically arises from discritization
of two-dimensional problem.


*** 2.  Function declaration and parameters


      SUBROUTINE MGCG(G_LEV, NUM_C, G_M1, G_M2,
     $                A1, B, X, ITER, EPS, WS, IER)

      INPUT:

        G_LEV     Num. of grids
        NUM_C     Num. of iterations on the coarsest grid
        G_M1(G_LEV)   Array of num. of grid points in x-direction
        G_M2(G_LEV)   Array of num. of grid points in y-direction
        A1(NUM_DIAG, N * 4/3)  Coefficient matrices
        B(N)      Right-hand term
        X(N1)     Initial approximate
        ITER      Maximum number of iterations
        EPS       Epsilon 

      WORK SPACE:

        WS(*)     Work array of dimension 2 * N + 2 * N1 + N * 4/3
                                          + N * 4/3 + N / 3 + 2 * (M1+M2) + 4 * (G_LEV-1)

      OUTPUT:

        X(N1)     Approximate solution
        ITER      Num. of iterations until convergence
        IER       Error code

      where M1 = G_M1(1), M2 = G_M2(1), N = M1 * M2 and N1 = (M1+2) * (M2+2).


*** 3.  Matrices


Matrix is stored by compressing in row.  Since matrix on each grid
level has five diagonals, each matrix is stored in 5 by N array when
the matrix is N by N.  For example, coefficients of the i'th equation
are stored in A[1..5, i] where

    A[1, i] x[i - M] + A[2, i] x[i - 1] + A[3, i] x[i]
                     + A[4, i] x[i + 1] + A[5, i] x[i + M] = b[i].

Each matrix is stored to one 5 by NN array in order of grid level,
where NN is a sum of unknowns of each grid level.


*** 4.  Sample problem


This library includes a sample main program that solves several
problems of two-dimensional Poisson equation.


*** 5.  User-defined coarsening and boundary condition


This library provides restriction and prolongation for standard
coarsening and Dirichlet or Dirichlet/Neumann boundary condition.  To
use semicoarsening or matrix-dependent coarsening, it is necessary to
rewrite 'rest_s.f' and 'prog_s.f'.


*** 6.  Questions and comments


When problems occur, you feel freely to contact me by E-mail:

	tatebe@etl.go.jp

Your comments and questions are always welcome.


*** 7.  References


[1] Osamu Tatebe, The Multigrid Preconditioned Conjugate Gradient
Method, Proceedings of Sixth Copper Mountain Conference on Multigrid
Methods, NASA Conference Publication 3224, pp.621-634, 1993
http://www.etl.go.jp/~tatebe/research/paper/CM93-letter.ps.gz (59K)
http://www.etl.go.jp/~tatebe/research/paper/CM93-A4.ps.gz     (59K)
http://www.mgnet.org/mgnet/Conferences/CopperMtn93/tatebe.ps.gz

[2] Osamu Tatebe and Yoshio Oyanagi, Efficient Implementation of the
Multigrid Preconditioned Conjugate Gradient Method on Distributed
Memory Machines, Proceedings of Supercomputing '94, IEEE Computer
Society, pp.194-203, 1994
http://www.etl.go.jp/~tatebe/research/paper/SC94-letter.ps.gz (98K)
http://www.etl.go.jp/~tatebe/research/paper/SC94-A4.ps.gz     (98K)
http://www.acm.org/pubs/articles/proceedings/supercomputing/198354/
p194-tatebe/p194-tatebe.pdf

[3] Osamu Tatebe, MGCG METHOD: A ROBUST AND HIGHLY PARALLEL ITERATIVE
METHOD, Ph.D Thesis, University of Tokyo, March, 1997
http://www.etl.go.jp/~tatebe/research/paper/PhD-tatebe.ps.gz (330K)