Browse reports by year:
[ ALL 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 ]
Browse report authors:
[ ALL A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ]
Browse reports by title:
[ ALL A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ]

University of Minnesota - Computer Science and Engineering Technical Report Abstract

Multilevel Algorithms For Generic Coarse Grids For Multigrid Methods

Report Number: 01-021
Date of Submission: 5/9/2001

Authors:
   
   

View Report:
   PDF format

Abstract:

Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.