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

multilevel OPTIMAL TRANSPORT: A FAST APPROXIMATION OF WASSERSTEIN-1 DISTANCES

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第1期43卷 A193-A220页

作者： Liu, Jialin Yin, Wotao Li, Wuchen Chow, Yat Tin Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Univ Calif Riverside Math Riverside CA 92521 USA

We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with transport cost homogeneous of degree one. Our algorithm is built on multilevel primal-dual algorithms. Several numerical examples and a complexity analysis are provided to demonstrate its computational speed. On some commonly used image examples of size 512 x 512, the proposed algorithm gives solutions within 0.2 similar to 1.5 seconds on a single CPU, which is much faster than the state-of-the-art algorithms.

关键词： multilevel algorithms optimal transport Wasserstein-1 distance primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

MULTIGRID METHODS FOR DISCRETE FRACTIONAL SOBOLEV SPACES

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第2期41卷 A948-A972页

作者： Baerland, Trygve Kuchta, Miroslav Mardal, Kent-andre Univ Oslo Dept Math N-0316 Oslo Norway

Coupled multiphysics problems often give rise to interface conditions naturally formulated in fractional Sobolev spaces. Here, both positive and negative fractionality are common. When designing efficient solvers for discretizations of such problems it would therefore be useful to have a preconditioner for the fractional Laplacian. In this work, we develop an additive multigrid preconditioner for the fractional Laplacian with positive fractionality and show a uniform bound on the condition number. For the case of negative fractionality, we reuse the preconditioner developed for the positive fractionality and left-right multiply a regular Laplacian with a preconditioner with positive fractionality to obtain the desired negative fractionality. Implementational issues are out-lined in detail as the differences between the discrete operators and their corresponding matrices must be addressed when realizing these algorithms in code. We finish with some numerical experiments verifying the theoretical findings.

关键词： fractional Laplacian multilevel algorithms operator preconditioning

来源：评论

学校读者我要写书评

暂无评论

A Class of Symmetric Factored Approximate Inverses and Hybrid Two-Level Solver

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL METHODS 2018年第6期15卷

作者： Kyziropoulos, Panagiotis E. Filelis-Papadopoulos, Christos K. Gravvanis, George A. Democritus Univ Thrace Sch Engn Dept Elect & Comp Engn Univ Campus GR-67100 Xanthi Greece

A new class of symmetric factored approximate inverses is proposed and used in conjunction with the Preconditioned Conjugate Gradient method for solving sparse symmetric linear systems. Additionally, a new hybrid two-level solver is proposed utilizing a block independent set reordering, in order to create the two level hierarchy. The Schur complement is formed explicitly by inverting the blocks created by reordering. Then, the preconditioned conjugate gradient method is used in conjunction with the symmetric factored approximate inverse to solve the reduced order linear system. Furthermore, numerical results on the performance and convergence behavior for solving various model problems are presented.

关键词： Symmetric factored approximate sparse inverses two level algebraic symmetric factored approximate inverse solver multilevel algorithms preconditioned conjugate gradient

来源：评论

学校读者我要写书评

暂无评论

Accelerated Randomized vs. Deterministic algorithms for MoM Blocks' Low-Rank Factorization

Accelerated Randomized vs. Deterministic Algorithms for MoM ...

引用

International Symposium of IEEE-Antennas-and-Propagation-Society / USNC/URSI National Radio Science Meeting

作者： Brick, Yaniv Yilmaz, Ali E. Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA

ISBN: (纸本)9781538632840

A randomized and a deterministic algorithm for the fast computation of impedance matrix blocks' low-rank factorization are contrasted. The deterministic algorithm is based on multilevel compression of non-uniformly sampled phase-and amplitude-compensated interactions between clusters of source/observer basis/testing functions. The randomized algorithm is accelerated by using fast Fourier transform-based field evaluation. The algorithms' performance are compared for various classes of problem topology and algorithm parameters.

关键词： direct solves fast methods 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

来源：评论

学校读者我要写书评

暂无评论

Low-Rank Approximation of Impedance Matrix Blocks Using Non-uniform Sampling Methods

Low-Rank Approximation of Impedance Matrix Blocks Using Non-...

引用

IEEE International Symposium on Antennas and Propagation / USNC-URSI Radio Science Meeting

作者： Brick, Yaniv Yilmaz, Ali E. Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA

ISBN: (纸本)9781509028528

Two physics-based rank-revealing multilevel algorithms are presented to efficiently compute impedance matrix blocks' low-rank representations. Both algorithms rely on non-uniform sampling of phase-and amplitude-compensated fields but use different auxiliary grids. The algorithms' computational costs and range of validity are compared.

关键词： direct solves fast methods 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：