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

Evolutionary n-Level Hypergraph Partitioning With Adaptive Coarsening

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2019年第6期23卷 962-971页

作者： Preen, Richard J. Smith, Jim Univ West England Dept Comp Sci & Creat Technol Bristol BS16 1QY Avon England

Hypergraph partitioning (HGP) is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable subproblems. Current techniques use a multilevel approach wherein an initial partitioning is performed after compressing the hypergraph to a predetermined level. This level is typically chosen to produce very coarse hypergraphs in which heuristic algorithms are fast and effective. This paper presents a novel memetic algorithm which remains effective on larger initial hypergraphs. This enables the exploitation of information that can be lost during coarsening and results in improved final solution quality. We use this algorithm to present an empirical analysis of the space of possible initial hypergraphs in terms of its searchability at different levels of coarsening. We find that the best results arise at coarsening levels unique to each hypergraph. Based on this, we introduce an adaptive scheme that stops coarsening when the rate of information loss in a hypergraph becomes nonlinear and show that this produces further improvements. The results show that we have identified a valuable role for evolutionary algorithms within the current state-of-the-art HGP framework.

关键词： Evolutionary algorithms (EAs) hypergraph partitioning (HGP) memetic algorithms multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Numerical solvers for radiation and conduction in high temperature gas flows

引用

FLOW TURBULENCE AND COMBUSTION 2005年第1-4期75卷 173-190页

作者： Seaïd, M Klar, A Pinnau, R Tech Univ Darmstadt Fachbereich Math D-64289 Darmstadt Germany

In this paper, the authors introduce a robust numerical technique for radiation-conduction heat transfer in the high temperature fields of gas turbine combustors. The conduction and radiation effects are analyzed by a differential and an integral equation, respectively. Using discrete ordinates for the angular discretization of the integral equation for the radiation effects and a Galerkin discretization for the heat equation, the authors propose a fast multilevel algorithm to solve the fully discretized problem. The algorithm uses the same mesh hierarchy for both radiation and conduction effects, but with two different smoothing operators. Numerical results are shown for test problems in three space dimensions, and comparisons to other methods are also given.

关键词： radiation-conduction heat transfer discrete ordinates Galerkin method multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

FAST algorithms FOR NONSMOOTH COMPACT FIXED-POINT PROBLEMS

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 1992年第6期29卷 1769-1792页

作者： HEINKENSCHLOSS, M KELLEY, CT TRAN, HT N CAROLINA STATE UNIV DEPT MATHRALEIGHNC 27695

A fast algorithm for compact fixed-point problems with nonsmooth nonlinearities is designed and analyzed. The algorithm is a combination of an extension of the Atkinson-Brakhage-Nystrom algorithm for smooth problems and a generalization of work by Yamamoto and Chen for nonsmooth problems. A critical structural hypothesis in the general theory is explicitly verified in the context of problems that can be expressed as integral equations with certain types of nonsmoothness. The work is motivated by problems in combat modeling. In particular, we consider the solution of an optimality system that arises in control of competitive systems.

关键词： COMBAT MODELING COMPETITIVE SYSTEMS INTEGRAL EQUATIONS NONDIFFERENTIABLE NONLINEAR EQUATIONS multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

The regulatory algorithm (RGA): a two-dimensional extension of evolutionary algorithms

引用

SOFT COMPUTING 2016年第5期20卷 2067-2075页

作者： Kluever, Juergen Kluever, Christina Univ Duisburg Essen Univ Str 12 D-45117 Essen Germany

In orientation to new developments in evolutionary biology we propose an extension of evolutionary algorithms in two dimensions, the regulatory algorithm (RGA). It consists of two levels of vectors, the regulatory vector and the structural vector. Each element of the regulatory vector is connected with one or several elements of the structural vector, but not vice versa. The connections can be interpreted as steering connections, the switching on or off of the structural elements and/or as switching orders for the structural elements. An RGA that operates with the usual genetic operators of mutation and crossover can be used for avoiding rules like penalty or default operators, it is in certain problems significantly faster than a standard genetic algorithm, and it is very suited when modeling and optimizing systems that consist themselves of different levels. Examples of RGA usage are shown, namely, the optimal dividing of socially deviant youths in a hostel, the optimal introduction of communication standards in information systems, and the allocation of employees to superiors by taking into regard the different personality types.

关键词： Evolutionary algorithms Biological evolution Regulatory genes Structural genes Regulatory algorithm multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

multilevel Physical Optics Algorithm for Near Field Scattering

引用

IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION 2014年第8期62卷 4325-4335页

作者： Gendelman, Alex Brick, Yaniv Boag, Amir Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

An algorithm for the fast computation of the physical optics (PO) integral describing single bounce back scattering in near-field scenarios is presented. The algorithm is based on a multilevel computation of partial contributions to the PO integral by hierarchically ordered subdomains. Phase- and amplitude-compensation of the partial contributions allows for their coarse sampling over non-uniform spherical grids. The solution is obtained by gradual aggregation of such partial contributions via interpolation on progressively denser grids. The computational complexity is further reduced by representation of small subdomains' contributions via their far-field patterns and transition to the near-field representations only at a higher level. Speed-up, accuracy, and error controllability are demonstrated.

关键词： High-frequency multilevel algorithms numerical methods physical optics (PO) scattering

来源：评论

学校读者我要写书评

暂无评论

PARTIALLY ASYNCHRONOUS CO-STATE PREDICTION ALGORITHM

引用

IEE PROCEEDINGS-CONTROL THEORY AND APPLICATIONS 1995年第2期142卷 88-94页

作者： ABDELWAHED, SS HASSAN, MF SULTAN, MA Dept. of Electron. & Commun. Cairo Univ. Giza Egypt

A partially asynchronous co-state prediction algorithm for the solution of the optimal control problem of linear large-scale systems is presented. A detailed study of the convergence behaviour of the proposed algorithm is given, taking into consideration the effect of communication delay among the processors forming the overall system. The results of applying the new algorithm to simulation examples are presented and compared with those obtained using the well-known synchronous algorithm.

关键词： PARALLEL PROCESSING CONVERGENCE multilevel algorithms POWER SYSTEMS POLLUTION CONTROL GAS ABSORPTION

来源：评论

学校读者我要写书评

暂无评论

Adaptive-multilevel BDDC and its parallel implementation

引用

COMPUTING 2013年第12期95卷 1087-1119页

作者： Sousedik, Bedrich Sistek, Jakub Mandel, Jan Univ So Calif Dept Aerosp & Mech Engn Los Angeles CA 90089 USA Acad Sci Czech Republ Inst Thermomech CZ-18200 Prague 8 Czech Republic Acad Sci Czech Republ Inst Math CR-11567 Prague 1 Czech Republic Univ Colorado Dept Math & Stat Sci Denver CO 80217 USA

We combine the adaptive and multilevel approaches to the BDDC and formulate a method which allows an adaptive selection of constraints on each decomposition level. We also present a strategy for the solution of local eigenvalue problems in the adaptive algorithm using the LOBPCG method with a preconditioner based on standard components of the BDDC. The effectiveness of the method is illustrated on several engineering problems. It appears that the Adaptive-multilevel BDDC algorithm is able to effectively detect troublesome parts on each decomposition level and improve convergence of the method. The developed open-source parallel implementation shows a good scalability as well as applicability to very large problems and core counts.

关键词： Parallel algorithms Domain decomposition Iterative substructuring BDDC Adaptive constraints multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Improving the Scalability of Distributed Network Emulations: An Algorithmic Perspective

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2023年第4期20卷 4325-4339页

作者： Zhao, Huaiyi Zhang, Xinyi Wang, Yang Diao, Zulong Li, Yanbiao Xie, Gaogang Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Chinese Acad Sci Comp Network Informat Ctr Beijing 100083 Peoples R China Purple Mt Labs Dept Future Networks Nanjing 211111 Peoples R China Univ Chinese Acad Sci Sch Comp Sci & Technol Beijing 100049 Peoples R China

By deploying virtualized network elements (hosts, switches, routers, links, etc.) on clusters of commodity machines, distributed network emulations (DNE) closely mimic the behaviors of network systems and provide real-time interactions and analysis for network service management. However, DNE encounters scalability challenges when faced with large network topologies. These challenges can be boiled down to the assignment problem: to which physical machine each virtualized network element should be assigned so that the largest possible network topology can be emulated? In this paper, we tackle this problem from an algorithmic perspective. We first propose TBR (topology balancing relaxation) as the relaxation of the assignment problem. TBR tries to maintain a balance of the hardware resource consumption, by minimizing the maximum inter-machine bandwidth. We further develop TBS (topology balancing solver), which combines mathematical techniques with multi-level algorithms to solve TBR efficiently. We integrate TBR and TBS into MaxiNet, a famous distributed network emulator. Experimental results show that with the same available physical resources, TBR and TBS can improve emulation scalability by up to 4.7x compared to baselines.

关键词： Distributed network emulations service assurance performance evaluations large-scale experimental platforms optimization theories multilevel algorithms

来源：评论

学校读者我要写书评

暂无评论

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions, Optimal Deterministic algorithms, and Higher-Order Convergence

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2014年第5期14卷 1027-1077页

作者： Dick, Josef Gnewuch, Michael Univ New S Wales Sch Math & Stat Sydney NSW 2052 Australia

We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing-dimension algorithms. More precisely, the spaces of integrands we consider are weighted, reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst-case error. We study two cost models for function evaluations that depend on the number of active variables of the chosen sample points, and we study two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.

关键词： Path integration multilevel algorithms Changing-dimension algorithms Quasi-Monte Carlo methods Polynomial lattice rules Reproducing kernel Hilbert spaces

来源：评论

学校读者我要写书评

暂无评论

RELAXATION-BASED COARSENING FOR multilevel HYPERGRAPH PARTITIONING

引用

MULTISCALE MODELING & SIMULATION 2019年第1期17卷 482-506页

作者： Shaydulin, Ruslan Chen, Jie Safro, Ilya Clemson Univ Sch Comp Clemson SC 29631 USA Thomas J Watson Res Ctr IBM Yorktown Hts NY 10598 USA

multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging from scientific computing to data science. In this paper we introduce the concept of algebraic distance on hypergraphs and demonstrate its use as an algorithmic component in the coarsening stage of multilevel hypergraph partitioning solvers. The algebraic distance is a vertex distance measure that extends hyperedge weights for capturing the local connectivity of vertices which is critical for hypergraph coarsening schemes. The practical effectiveness of the proposed measure and corresponding coarsening scheme is demonstrated through extensive computational experiments on a diverse set of problems. Finally, we propose a benchmark of hypergraph partitioning problems to compare the quality of other solvers.

关键词： hypergraph partitioning multilevel algorithms coarsening matching vertex similarity measure combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：