Fast and Scalable Multigrid Methods for Hypergraph Partitioning Problems

超图分区问题的快速且可扩展的多重网格方法

• 批准号: 1522751
• 负责人: Ilya Safro
• 金额: $ 18万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-15 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1522751&HistoricalAwards=false
• 关键词: Fast; Scalable; Multigrid; Methods; Hypergraph

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.

科学的进步要求发展新的数学方法，能够快速、可靠地解决大规模的科学计算问题。任何现代科学计算工具和超级计算机都必须有能力有效地（人们希望是最佳的）操纵数据和并行计算过程来管理：(a)并行计算中的负载平衡；(b)超级计算机组件之间的数据迁移；(c)性能优化；(d)任务调度；(e)存储/内存减少和数据压缩。这些问题和许多其他问题（例如电子芯片设计和社交网络中的社区检测）可以使用一组称为分区的数学优化问题来解决，这些问题是在称为超图的数学模型上公式化的。然而，超图的划分在理论和实践中都是非常困难的。为了解决这个问题，该研究项目将开发和研究受多重网格启发的高效方法，多重网格是解决大规模科学计算问题的最成功的数值方法之一。该项目的技术目标是在计算数学和科学计算领域的各种问题的驱动下，对超图划分的代数和非线性多网格方法进行计算和理论研究。这些研究旨在为科学计算应用提供实用计算能力、矩阵-矩阵（向量）乘法建模、矩阵划分和一般负载平衡方面的突破。该项目的成果也将加深对应用于计算离散优化的多重网格方法理论的理解。近几十年来，图的多网格启发方法（也称为多层）在各种计算问题上取得了重要突破。然而，与基于图切割问题（如图划分和线性排列）的多网格启发方法相比，超图的多网格启发方法相对未被探索。本项目旨在发展与图和超图上离散优化问题的多网格启发方法相关的理论，在计算数学中具有重要的实际意义。

项目成果

Generating realistic scaled complex networks

• DOI: 10.1007/s41109-017-0054-z
• 发表时间: 2016-09
• 期刊: Applied Network Science
• 影响因子: 2.2
• 作者: Christian Staudt;M. Hamann;Alexander Gutfraind;Ilya Safro;Henning Meyerhenke