Accession Number:

ADA439418

Title:

Partitioning Algorithms for Simultaneously Balancing Iterative and Direct Methods

Descriptive Note:

Technical rept.

Corporate Author:

MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2004-03-03

Pagination or Media Count:

18.0

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 e.g., 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 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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE