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

On Coxeter spectral study of finite posets using computer algebra tools

Electronic Notes in Discrete Mathematics 2013年 40卷 121-127页

作者： Gasiorek, Marcin Simson, Daniel Zajac, Katarzyna Faculty of Mathematics and Computer Science Nicolaus Copernicus University Toruń Poland

We study a class of posets with a non-negativity condition by means of Coxeter spectral properties of the simply-laced Euclidean diagrams {D~n,n≥4,E~6,E~7,E~8}. We show that symbolic and numerical computer calculatio... 详细信息

We study a class of posets with a non-negativity condition by means of Coxeter spectral properties of the simply-laced Euclidean diagrams {D~_n,n≥4,E~₆,E~₇,E~₈}. We show that symbolic and numerical computer calculations in Python, C and Linux tools allow us to compute a complete list of these posets J, with at most 15 points, by means of their Coxeter spectra speccJ⊆C. © 2013 Elsevier B.V.

关键词： combinatorial algorithms Coxeter polynomial Euclidean diagram Poset Principal quadratic form Python

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Time algorithms for Compressive Phase Retrieval

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第11期66卷 7302-7310页

作者： Li, Yi Nakos, Vasileios Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore Saarland Univ D-66123 Saarbrucken Germany

In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately k-sparse vector x epsilon C-n given access to y = | phi x|, where |v| denotes the vector obtained from taking the absolute value of v epsilon Cn coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements.

关键词： Signal processing algorithms Phase measurement Time measurement Decoding Approximation algorithms Compressed sensing Computer science Phase retrieval compressive sensing sparse recovery sublinear-time algorithms combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Estimating all possible SUR models with permuted exogenous data matrices derived from a VAR process

引用

JOURNAL OF ECONOMIC DYNAMICS & CONTROL 2006年第5期30卷 721-739页

作者： Gatu, C Kontoghlorghes, EJ Univ Neuchatel Inst Informat CH-2007 Neuchatel Switzerland Univ Cyprus Dept Publ & Business Adm CY-1678 Nicosia Cyprus Univ London Birkbeck Coll Sch Comp Sci & Informat Syst London WC1E 7HX England

The Vector Autoregressive (VAR) process with zero coefficient constraints can be formulated as a Seemingly Unrelated Regressions (SUR) model. Within the context of subset VAR model selection a computationally efficient strategy to generate and estimate all G! SUR models when permuting the exogenous data matrices is proposed, where G is the number of the regression equations. The combinatorial algorithm is based on orthogonal transformations, exploits the particular structure of the modified models and avoids the estimation of these models afresh by utilizing previous computation. Theoretical measurements of complexity are derived to prove the efficiency of the proposed algorithm. (c) 2005 Elsevier B.V. All rights reserved.

关键词： subset vector autoregressive model selection seemingly unrelated regressions models least squares QR decomposition combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Parameter Control Applied to the Grouping Genetic Algorithm with Controlled Gene Transmission 10

Deterministic Parameter Control Applied to the Grouping Gene...

引用

10th International Conference on Soft Computing and Machine Intelligence (ISCMI)

作者： Flores-Torres, Leonardo Amador-Larrea, Stephanie Quiroz-Castellanos, Marcela Ramos-Figueroa, Octavio Univ Veracruzana Artificial Intelligence Res Inst Xalapa Veracruz Mexico

ISBN: (纸本)9798350359374

An experimental study was performed where deterministic parameter control is applied to the crossover and mutation ratios of the Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) considering several control functions with different characteristics in order to solve the off-line One-Dimensional Bin Packing Problem (1-D BPP). Such control is mainly based on sinusoidal behavior to allow the algorithm to experience small variations in the parameter to control, and another control scheme based on the same sinusoidal behavior was designed to experiment smaller and larger parameter stepsize values even in the last stages of the run. An additional form of control is also included based on linear growth. The obtained performance is compared against the tuned version of the algorithm. Obtained results show that the GGA-CGT could benefit from the sinusoidal control scheme under small variations for the crossover ratio and from the linear control scheme for the mutation ratio. Lastly, the control schemes that showed the best results were tested in the Grouping Genetic Algorithm with Intelligent Heuristic Strategies (GGA-IHS) designed to solve the Parallel-machine scheduling problem with unrelated machines and makespan minimization (R||C-max) showing promising results.

关键词： genetic algorithms combinatorial algorithms algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

Boundary Integral Solver Approaches for Particle Accelerator Simulation Problems and Deployment on NERSC Hardware

Boundary Integral Solver Approaches for Particle Accelerator...

引用

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Wei, Julia Langston, M. Harper Letourneau, Pierre-David Morse, Matthew J. Weintraub, Larry Nogoy, Aimee Amsel, Noah Lethin, Richard Reservoir Labs Inc New York NY 10012 USA

ISBN: (纸本)9781665423694

Reservoir Labs, through a project titled MACHB (Multipole Accelerator Codes for Hadron Beams)(1), is developing a Fast Multipole Method [1]-[7] (FMM)-based tool for higher fidelity modeling of particle accelerators for high-energy physics with an initial focus on the next generation of Fermilab's Synergia simulation package [8]. MACH-B incorporates (1) highly-scalable, high-performance and generally-applicable FMM-based algorithms [5]-[7], [9] to accurately model space-charge effects in high-intensity hadron beams and (2) boundary integral approaches [10]-[12] to handle singular effects near the beam pipe using advanced quadratures. MACH-B will allow for more complex beam dynamics simulations that more accurately capture bunch effects and predict beam loss. By introducing an abstraction layer to hide FMM implementation and parallelization complexities, this project will also remove one of the key impediments to the adoption of FMMs by the accelerator physics community. In this work, we focus on the following results for the boundary integral solver components of the MACH-B project: Study of the relative accuracies of the hedgehog [12] boundary integral solver when evaluating potential and gradient solutions to Laplace's equation with Dirichlet boundary conditions Study of a single-bunch, Gaussian-distributed set of charges within a conducting pipe, using an embedded boundary solver Results show the ability to simulate charge densities inside of a pipe-shaped object for accelerator simulations, running experiments on a collection of NERSC's Cori Cray XC40 Intel Xeon "Haswell" processor nodes 2 and Reservoir's internal computational resources.

关键词： combinatorial algorithms spectral support solver linear systems fast solvers preconditioners multigrid graph laplacian benchmarking iterative solvers

来源：评论

学校读者我要写书评

暂无评论

Approximate Function Matching under δ- and γ- Distances

Approximate Function Matching under δ- and γ- Distances

引用

19th International Symposium on String Processing and Information Retrieval (SPIRE) / 8th Latin American Web Congress (LA-WEB)

作者： Mendivelso, Juan Lee, Inbok Pinzon, Yoan J. Univ Nacl Colombia Res Grp Algorithms & Combinator ALGOS UN Dept Comp Sci & Ind Engn Bogota Colombia

ISBN: (纸本)9783642341083;9783642341090

This paper defines a new string matching problem by combining two paradigms: function matching and delta gamma-matching. The result is an approximate variant of function matching where two equal-length strings X and Y match if there exists a function that maps X to a string X' such that X' and Y are delta gamma-similar. We propose an O(nm) algorithm for finding all the matches of a pattern P-1...m in a text T-1...n.

关键词： combinatorial algorithms delta-matching gamma-matching delta gamma-matching function matching

来源：评论

学校读者我要写书评

暂无评论

A Minimum Cover Algorithm for PMU Placement in Power System Networks Under Line Observability Constraints

A Minimum Cover Algorithm for PMU Placement in Power System ...

引用

General Meeting of the IEEE-Power-and-Energy-Society

作者： Anderson, Joel E. Chakrabortty, Aranya N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

ISBN: (纸本)9781467327299

In this paper we develop a graph-theoretic PMU placement algorithm for multi-area power system networks with the objective of identifying a dynamic equivalent model for the system. The system is considered to be divided into clusters or areas of synchronous generators, with each area connected to other sets of areas through designated transmission networks. The buses in the system are accordingly divided into two types, namely - boundary buses of the areas and boundary buses of the transmission networks. We first show that in order to derive the equivalent line parameters connecting the different areas we must have PMUs placed at the minimum vertex cover of the bipartite graphs formed between every pair of node-sets arising out of the boundary buses of the areas and those of the corresponding transmission networks they are connected to. Considering further that the number of tie-lines observable from any given PMU is constrained by an upper limit, we derive an algorithm to compute the sub-optimal minimum cover for the multi-area system. The method is illustrated via a 4-6 bipartite network, as well as with two small examples from the WECC system. Statistical analyses of the algorithm are also presented describing how the final set of chosen PMU locations as well as the computational time needed to run the algorithm are dependent on the size, complexity and measurement constraints of the network.

关键词： Phasor measurement unit (PMU) placement equivalent models graph theory minimum cover combinatorial algorithms Konig's theorem

来源：评论

学校读者我要写书评

暂无评论

Extreme elevation on a 2-manifold

Extreme elevation on a 2-manifold

引用

20th ACM Symposium on Computational Geometry

作者： Agarwal, Pankaj K. Edelsbrunner, Herbert Harer, John Wang, Yusu Duke Univ Dept Comp Sci Durham NC 27708 USA Raindrop Geometr Res Triangle Pk NC 27709 USA Duke Univ Dept Math Durham NC 27708 USA

Given a smoothly embedded 2-manifold in R-3, we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant under rigid motions and can be used to define features such as lines of discontinuous or continuous but non-smooth elevation. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions and are useful in matching shapes as for example in protein docking.

关键词： combinatorial algorithms Critical points Morse functions Pedal function Persistence Surgery Triangulations

来源：评论

学校读者我要写书评

暂无评论

Engineering a Distributed Histogram Sort

Engineering a Distributed Histogram Sort

引用

IEEE International Conference on Cluster Computing (IEEE CLUSTER)

作者： Kowalewski, Roger Jungblut, Pascal Fuerlinger, Karl Ludwig Maximilians Univ Munchen Inst Informat Munich Germany

ISBN: (纸本)9781728147345

Sorting is one of the most critical non-numerical algorithms and covers use cases in a wide spectrum of scientific applications. Although we can build upon excellent research over the last decades, scaling to thousands of processing units on modern many-core architectures reveals a gap between theory and practice. We adopt ideas of the well-known quickselect and sample sort algorithms to minimize data movement. Our evaluation demonstrates that we can keep up with recently proposed distribution sort algorithms in large-scale experiments, without any assumptions on the input keys. Additionally, our implementation outperforms an efficient multi-threaded merge sort on a single node. Our implementation is based on a C++ PGAS approach with an STL-like interface and can easily be integrated into many application codes. As part of the presented experiments, we further reveal challenges with multi-threaded MPI and one-sided communication.

关键词： Sorting Searching combinatorial algorithms PGAS

来源：评论

学校读者我要写书评

暂无评论

Maximum Flow by Augmenting Paths in n^2+o(1) Time 65

Maximum Flow by Augmenting Paths in n<SUP>2+o</SUP>(1) Time

引用

65th Symposium on Foundations of Computer Science

作者： Bernstein, Aaron Blikstad, Joakim Saranurak, Thatchaphol Tu, Ta-Wei NYU New York NY 10012 USA KTH Royal Inst Technol Stockholm Sweden Max Planck Inst Informat Saarbrucken Germany Univ Michigan Ann Arbor MI 48109 USA Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9798331516758;9798331516741

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from {1,..., U} in n(2+o(1)) log U time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework;we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing O(m center dot min{root m, n(2/3)}) time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has m = omega(n(4/3)) edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the n(2+o(1)) time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

关键词： maximum flow augmenting paths combinatorial algorithms directed expander hierarchy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：