From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Multigrid Examples
Date: 14 Feb 2001 11:25:29 GMT
Newsgroups: sci.math.num-analysis
Summary: What are algebraic multigrid techniques?

In article <3A89F3B0.C90C5AB0@engmail.uwaterloo.ca>,
 Sanjayan Vinayagamoorthy <svinayag@engmail.uwaterloo.ca> writes:
|> Hello,
|> 
|> I was exposed to various methods of solving sparse matrices (LU
|> factorisation, conjugate-gradient) but
|> the technique that still puzzles me is Multigrid.  I understand the
|> basics of it, but when I have tried to code
|> it, the results have not been pretty.  I looked at numerical recipes
|> (www.nr.com) but they explain it in the
|> context of ellliptical equations, something I haven't even heard.  I was
|> wondering if anyone knows of a
|> book or a webpage that explains multigrid by solving a simple equation
|> Ax=b.  It seems there should be
|> plenty of infomation, but any searches on web that I have done on it
|> have come up empty.  If anyone
|> could help me, I would really appreciate 

what you are after is known as "algebraic multigrid" and here come some papers:
there are many papers on this subject, but typically also in these papers 
there is background of discretization methods involved, since
otherwise the whole concept makes little sense. but indeed one tries to translate
this concept into abstract properties of the matrix alone.


Webster, R.
Efficient algebraic multigrid solvers with elementary restriction and 
prolongation. (English)
[J] Int. J. Numer. Methods Fluids 28, No.2, 317-336 (1998). 
[ISSN 0271-2091] http://www.interscience.wiley.com


Krieger, Udo R.
Numerical solution of large finite Markov chains by algebraic multigrid 
techniques. (English)
[CA] Stewart, William J. (ed.), Computations with Markov chains. 
Proceedings of the 2nd international workshop on the numerical solution of 
Markov chains, Raleigh, NC, USA,
January 16--18, 1995. Boston, MA: Kluwer Academic Publishers. 403-424 (1995). 
[ISBN 0-7923-9550-6/hbk]
Iterative aggregation/disaggregation procedures are a convenient 
numerical solution method for computing the stationary distribution vector 
of an ergodic homogeneous Markov
chain with a finite state space. We show the equivalence of this method and 
a two-level multigrid method. Based on error results of the A/D-method, 
we provide an error analysis
of an efficient multigrid variant of the multiplicative Schwarz-iteration 
method. Furthermore, we apply these results to a multigrid version of the 
replacement process approach
developed by Sumita and Rieders.


Brandt, Achi
Algebraic multigrid theory: The symmetric case. (English)
[J] Appl. Math. Comput. 19, 23-56 (1986).
A rigorous two-level theory is developed for general symmetric matrices 
and nonsymmetric ones using Kaczmarz relations, without assuming any 
regularity, not even any grid
structure of the unknowns. The theory applies to algebraic multigrid 
processes, as well as to the usual geometric multigrid. It yields 
realistic estimates and answers to some basic
algorithmic questions. The theory helps to rigorize local mode 
analyses and locally analyze cases where the latter does not apply. 
A preliminary version appeared in 1983.


Brandt, A.; McCormick, S.; Ruge, J.
Algebraic multigrid (AMG) for sparse matrix equations. (English)
[CA] Sparsity and its applications, Meet. Loughborough/Engl. 1983, 257-284 (1984).
[For the entire collection see Zbl. 544.00021.] \par Many matrix equations 
are either inherently discrete (e.g., in geodesy) or for certain 
practical purposes remote from their origin
(e.g., a finite element discretization on a preselected irregular grid). 
AMG is an algorithm designed to solve such problems by using information 
contained only in the matrix while at
the same time basing itself on multigrid principles. 
This paper introduces the basic AMG concepts, develops its foundations, 
and describes current AMG strategies.

hope that helps
peter