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

Partitioning Algorithms for Simultaneously Balancing Iterative and Direct Methods

Report Number: 04-014
Date of Submission: 3/3/2004

Authors:
   
   

View Report:
   PDF format

Abstract:

This paper focuses on domain decomposition-based numerical simulations whose sub-problems corresponding to the various subdomains are solved using sparse direct factorization methods (eg., FETI). Effective load-balancing of such computations requires that the resulting partitioning simultaneously balances the amount of time required to factor the local subproblem using direct factorization, and the number of elements assigned to each processor. Unfortunately, existing graph-partitioning algorithms cannot be used to load-balance these type of computations as they can only compute partitionings that simultaneously balance numerous constraints defined a~priori on the vertices and optimize different objectives defined locally on the edges. To address this problem, we developed an algorithm that follows a {em predictor-corrector} approach that first computes a high-quality partitioning of the underlying graph, and then modifies it to achieve the desired balancing constraints. During the corrector step we compute a fill reducing ordering for each partition, and then we modify the initial partitioning and ordering so that our objectives are satisfied. Experimental results show that the proposed algorithm is able to reduce the fill-in of the overweight sub-domains and achieve a considerably better balance.