Fast and Scalable Multigrid Methods for Hypergraph Partitioning Problems

Clemson University, Clemson SC

Investigators

Abstract

The advancement of science requires the development of new mathematical methods that can rapidly and reliably solve large-scale scientific computing problems. Any modern scientific computing tool and supercomputer must have the ability to effectively (and one hopes optimally) manipulate both the data and parallel computational processes to manage: (a) the load-balancing in parallel computation; (b) data migration between components in a supercomputer; (c) performance optimization; (d) task scheduling; and (e) storage/memory reduction and data compression. These and many other problems (such as electronic chip design and community detection in social networks) can be tackled using a family of mathematical optimization problems called partitioning that are formulated on mathematical models called hypergraphs. However, partitioning of hypergraphs is extremely hard in theory and practice. To tackle it, this research project will develop and investigate efficient and effective methods that are inspired by multigrid, which is one of the most successful classes of numerical methods for solving large-scale scientific computing problems. The technical goal of this project is to carry out computational and theoretical investigations in algebraic and nonlinear multigrid methods for hypergraph partitioning motivated by various problems in the areas of computational mathematics and scientific computing. These investigations aim to provide breakthroughs in practical computational capabilities, modeling matrix-matrix (vector) multiplication, matrix partitioning, and general load-balancing for scientific computing applications. The results of the project will also deepen understanding of theory of multigrid methods applied to computational discrete optimization. In recent decades, multigrid-inspired methods for graphs (also known as multilevel) led to important breakthroughs in a variety of computational problems. However, in contrast to the multigrid-inspired methods for graph cut-based problems (such as graph partitioning and linear arrangement), multigrid-inspired methods for hypergraphs are relatively unexplored. This project aims to develop theory related to multigrid-inspired methods for discrete optimization problems on graphs and hypergraphs, of great practical importance in computational mathematics.