检索结果-内蒙古大学图书馆

Scalable High-Quality Hypergraph Partitioning

ACM TRANSACTIONS ON algorithmS 2024年第1期20卷 1-54页

作者： Gottesbueren, Lars Heuer, Tobias Maas, Nikolai Sanders, Peter Schlag, Sebastian Karlsruhe Inst Technol Fasanengarten 5 D-76135 Karlsruhe Germany Apple Inc Cupertino CA 95014 USA

Balanced hypergraph partitioning is an NP-hard problem with many applications, e.g., optimizing communication in distributed data placement problems. The goal is to place all nodes across k different blocks of bounded size, such that hyperedges span as few parts as possible. This problem is well-studied in sequential and distributed settings, but not in shared-memory. We close this gap by devising efficient and scalable shared-memory algorithms for all components employed in the best sequential solvers without compromises with regards to solution quality. This work presents the scalable and high-quality hypergraph partitioning framework Mt-KaHyPar. Its most important components are parallel improvement algorithms based on the FM algorithm and maximum flows, as well as a parallel clustering algorithm for coarsening - which are used in a multilevel scheme with log(n) levels. As additional components, we parallelize the n-level partitioning scheme, devise a deterministic version of our algorithm, and present optimizations for plain graphs. We evaluate our solver on more than 800 graphs and hypergraphs, and compare it with 25 different algorithms from the literature. Our fastest configuration outperforms almost all existing hypergraph partitioners with regards to both solution quality and running time. Our highest-quality configuration achieves the same solution quality as the best sequential partitioner KaHyPar, while being an order of magnitude faster with ten threads. Thus, two of our configurations occupy all fronts of the Pareto curve for hypergraph partitioning. Furthermore, our solvers exhibit good speedups, e.g., 29.6x in the geometric mean on 64 cores (deterministic), 22.3x (log(n)-level), and 25.9x (n-level).

关键词： Graph and hypergraph partitioning shared-memory high-quality multilevel algorithm determinism concurrent gain computations clustering community detection work-stealing FM algorithm maximum flows

来源：评论

学校读者我要写书评

暂无评论

Multiobjective Optimization for Politically Fair Districting: A Scalable multilevel Approach

引用

OPERATIONS RESEARCH 2023年第2期71卷 536-562页

作者： Swamy, Rahul King, Douglas M. Jacobson, Sheldon H. Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Political districting in the United States is a decennial process of redrawing the boundaries of congressional and state legislative districts. The notion of fairness in political districting has been an important topic of subjective debate, with district plans affecting a wide range of stakeholders, including the voters, candidates, and political parties. Even though districting as an optimization problem has been well studied, existing models primarily rely on nonpolitical fairness measures such as the compactness of districts. This paper presentsmixed integer linear programming (MILP) models for districting with political fairness criteria based on fundamental fairness principles such as vote-seat proportionality (efficiency gap), partisan (a)symmetry, and competitiveness. A multilevel algorithm is presented to tackle the computational challenge of solving large practical instances of these MILPs. This algorithm coarsens a large graph input by a series of graph contractions and solves an exact biobjective problem at the coarsest graph using the epsilon-constraint method. A case study on congressional districting in Wisconsin demonstrates that district plans constituting the approximate Pareto-front are geographically compact, as well as efficient (i.e., proportional), symmetric, or competitive. An algorithmically transparent districting process that incorporates the goals of multiple stakeholders requires a multiobjective approach like the one presented in this study. To promote transparency and facilitate future research, the data, code, and district plans aremade publicly available.

关键词： gerrymandering political redistricting fairness efficiency gap partisan asymmetry competitiveness multilevel algorithm Pareto optimal

来源：评论

学校读者我要写书评

暂无评论

Numerical Calculation of Electromagnetic Scattering from Multiple Objects by Superposition Solution Combined with MoM - multilevel algorithm

Numerical Calculation of Electromagnetic Scattering from Mul...

引用

Conference on International Symposium on Electromagnetic Compatibility Tokyo

作者： Tanaka, Masahiro Gifu Univ Fac Engn Gifu 5011193 Japan

We have applied the superposition solution combined with the method of moments into electromagnetic scattering from multiple objects so far. In this paper, we apply the multilevel algorithm for superposition solution,... 详细信息

ISBN: (纸本)9784885522871

关键词： superposition solution multilevel algorithm method of moments integral equations

来源：评论

学校读者我要写书评

暂无评论

Distributed Deep multilevel Graph Partitioning 29th

Distributed Deep Multilevel Graph Partitioning

引用

29th International Conference on Parallel and Distributed Computing (Euro-Par)

作者： Sanders, Peter Seemaier, Daniel Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9783031396977;9783031396984

We describe the engineering of the distributed-memory multilevel graph partitioner dKaMinPar. It scales to (at least) 8192 cores while achieving partitioning quality comparable to widely used sequential and shared-memory graph partitioners. In comparison, previous distributed graph partitioners scale only in more restricted scenarios and often induce a considerable quality penalty compared to non-distributed partitioners. When partitioning into a large number of blocks, they even produce infeasible solution that violate the balancing constraint. dKaMinPar achieves its robustness by a scalable distributed implementation of the deep-multilevel scheme for graph partitioning. Crucially, this includes new algorithms for balancing during refinement and coarsening.

关键词： algorithms distributed systems graph partitioning multilevel algorithm balancing

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Interpolation algorithm for Fast Born Approximation Analysis of Scattering by Electrically Large Objects

Hierarchical Interpolation Algorithm for Fast Born Approxima...

引用

IEEE International Conference on Microwaves, Antennas, Communications and Electronic Systems (COMCAS)

作者： Elbaz, E. Brick, Y. Ben Gurion Univ Negev Sch Elect & Comp Engn IL-8410501 Beer Sheva Israel

ISBN: (纸本)9780738146720

An algorithm for the fast computation of Born approximation scattered field integral for electrically large lowcontrast inhomogeneous targets is presented. The algorithm takes advantage of the integrand's phase in order to efficiently sample partial the contributions to the scattered field, in both the source and observer coordinates. These contributions are gradually interpolated and aggregated, with appropriate phase factors, in a multilevel fashion, in order to obtain the total field integral, sampled at a desired density. This reduces the cost of field integrations by three orders of the scatterer's electrical length. For the far-field and incident plane wave scenario, the computations are further simplified and reduced to that of a single scalar component.

关键词： Wave scattering Born approximation fast methods multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

A multilevel bilinear programming algorithm for the vertex separator problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2018年第1期69卷 189-223页

作者： Hager, William W. Hungerford, James T. Safro, Ilya Univ Florida Dept Math POB 118105 Gainesville FL 32611 USA RaceTrac Store Support Ctr 200 Galleria Pkwy SE Atlanta GA 30339 USA Clemson Univ Sch Comp 228 McAdams Hall Clemson SC 29634 USA

The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. The Vertex Separator Problem was formulated in the paper 10.1016/***.2014.05.042 as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. We develop a method for improving upon a given vertex separator by applying a Mountain Climbing algorithm to the bilinear program using an incidence vector for the separator as a starting guess. Sufficient conditions are developed under which the algorithm can improve upon the starting guess after at most two iterations. The refinement algorithm is augmented with a perturbation technique to enable escapes from local optima and is embedded in a multilevel framework for solving large scale instances of the problem. The multilevel algorithm is shown through computational experiments to perform particularly well on communication and collaboration networks.

关键词： Vertex separator Continuous formulation Graph partitioning multilevel Weighted edge contractions multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

Drawing Large Graphs by multilevel Maxent-Stress Optimization

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2018年第5期24卷 1814-1827页

作者： Meyerhenke, Henning Noellenburg, Martin Schulz, Christian KIT Inst Theoret Informat D-76131 Karlsruhe Germany TU Wien Algorithms & Complex Grp A-1040 Vienna Austria Univ Vienna Dept Comp Sci A-1010 Vienna Austria Karlsruhe Inst Technol D-76131 Karlsruhe Germany

Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to the maxent-stress metric proposed by Gansner et al. (2013) that combines layout stress and entropy. As opposed to previous work, we do not solve the resulting linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on a single thread) while producing a comparable solution quality.

关键词： Graph layout algorithm engineering multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

Some multilevel decoupled algorithms for a mixed navier-stokes/darcy model

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2018年第1期44卷 115-145页

作者： Cai, Mingchao Huang, Peiqi Mu, Mo Morgan State Univ Dept Math 1700 E Cold Spring Ln Baltimore MD 21251 USA Nanjing Forestry Univ Dept Appl Math Nanjing 210037 Jiangsu Peoples R China Hong Kong Univ Sci Technol Dept Math Kowloon Hong Kong Peoples R China

In this work, several multilevel decoupled algorithms are proposed for a mixed Navier-Stokes/Darcy model. These algorithms are based on either successively or parallelly solving two linear subdomain problems after solving a coupled nonlinear coarse grid problem. Error estimates are given to demonstrate the approximation accuracy of the algorithms. Experiments based on both the first order and the second order discretizations are presented to show the effectiveness of the decoupled algorithms.

关键词： Fluid flow coupled with porous media flow Darcy law Navier-Stokes equations Interface coupling multilevel algorithm Decoupling Linearization

来源：评论

学校读者我要写书评

暂无评论

Solving the Large Scale Next Release Problem with a Backbone-Based multilevel algorithm

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2012年第5期38卷 1195-1212页

作者： Xuan, Jifeng Jiang, He Ren, Zhilei Luo, Zhongxuan Dalian Univ Technol Sch Software Dalian 116621 Peoples R China Dalian Univ Technol Sch Math Sci Dalian 116621 Peoples R China

The Next Release Problem (NRP) aims to optimize customer profits and requirements selection for the software releases. The research on the NRP is restricted by the growing scale of requirements. In this paper, we propose a Backbone-based multilevel algorithm (BMA) to address the large scale NRP. In contrast to direct solving approaches, the BMA employs multilevel reductions to downgrade the problem scale and multilevel refinements to construct the final optimal set of customers. In both reductions and refinements, the backbone is built to fix the common part of the optimal customers. Since it is intractable to extract the backbone in practice, the approximate backbone is employed for the instance reduction while the soft backbone is proposed to augment the backbone application. In the experiments, to cope with the lack of open large requirements databases, we propose a method to extract instances from open bug repositories. Experimental results on 15 classic instances and 24 realistic instances demonstrate that the BMA can achieve better solutions on the large scale NRP instances than direct solving approaches. Our work provides a reduction approach for solving large scale problems in search-based requirements engineering.

关键词： The next release problem backbone soft backbone multilevel algorithm requirements instance generation search-based requirements engineering

来源：评论

学校读者我要写书评

暂无评论

A multilevel tabu search algorithm for balanced partitioning of unstructured grids

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2016年第9期105卷 678-692页

作者： Mehrdoost, Zahra Bahrainian, Seyed Saied Shahid Chamran Univ Ahvaz Dept Mech Engn Ahvaz *** Iran

This paper presents a multilevel algorithm for balanced partitioning of unstructured grids. The grid is partitioned such that the number of interface elements is minimized and each partition contains an equal number of grid elements. The partition refinement of the proposed multilevel algorithm is based on iterative tabu search procedure. In iterative partition refinement algorithms, tie-breaking in selection of maximum gain vertices affects the performance considerably. A new tie-breaking strategy in the iterative tabu search algorithm is proposed that leads to improved partitioning quality. Numerical experiments are carried out on various unstructured grids in order to evaluate the performance of the proposed algorithm. The partition results are compared with those produced by the well-known partitioning package Metis and k-means clustering algorithm and shown to be superior in terms of edge cut, partition balance, and partition connectivity. Copyright (c) 2015 John Wiley & Sons, Ltd.

关键词： grid partitioning multilevel algorithm tabu search unstructured grid

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：