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

The split-and-merge method in general purpose computation on GPUs

PARALLEL COMPUTING 2012年第6-7期38卷 277-288页

作者： Argueello, F. Heras, D. B. Boo, M. Lamas-Rodriguez, J. Univ Santiago de Compostela Dept Elect & Comp Santiago De Compostela 15782 Spain

The split-and-merge method is an algorithm design paradigm sometimes used in the field of parallel computing. It is applied to multilevel algorithms such as the wavelet transforms and some tridiagonal system solvers. In this paper we present the application of the method in the context of general purpose computation on GPUs. The split-and-merge method allows us to efficiently use the CUDA parallel programming model, where a multithreaded program is partitioned into blocks of threads that execute independently from each other. Thus we can solve the data dependency problem at the block boundaries and efficiently take advantage of the memory hierarchy of the GPU. The results obtained show a significant acceleration compared with the direct implementation of the algorithms on the GPU. (c) 2012 Published by Elsevier B.V.

关键词： GPGPU CUDA Split-and-merge multilevel algorithm Wavelet

来源：评论

学校读者我要写书评

暂无评论

A sparse data fast fourier transform (SDFFT)

引用

IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION 2003年第11期51卷 3161-3170页

作者： Aydiner, AA Chew, WC Song, JM Cui, TJ Univ Illinois Dept Elect & Comp Engn Ctr Computat Electromagnet & Electromagnet Lab Urbana IL 61801 USA Iowa State Univ Sci & Technol Dept Elect & Comp Engn Ames IA 50011 USA SE Univ Dept Radio Engn Ctr Computat Electromagnet Nanjing 210096 Peoples R China SE Univ Dept Radio Engn State Key Lab Millimeter Waves Nanjing 210096 Peoples R China

A multilevel algorithm that efficiently Fourier transforms sparse spatial data to sparse spectral data with controllable error is presented. The algorithm termed "sparse data fast fourier transform" (SDFFT) is particularly useful for signal processing applications where only part of the k-space is to be computed-regardless of whether it is a regular region like an angular section of the Ewald sphere or it consists of completely arbitrary points scattered in the k-space. In addition, like the various nonuniform fast Fourier transforms, the O(N log N) algorithm can deal with a sparse, nonuniform spatial domain. In this paper, the parabolic reflector antenna problem is studied as an example to demonstrate its use in the computation of far-field patterns due to arbitrary aperture antennas and antenna arrays. The algorithm is also promising for various applications such as back-projection tomography, diffraction tomography, and synthetic aperture radar imaging.

关键词： far-field computation multilevel algorithm nonuniform fast Fourier transform (NUFFT) parabolic reflector physical optics synthetic aperture radar imaging tomography

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Synergetic use of different evaluation, parameterization and search tools within a multilevel optimization platform

引用

APPLIED SOFT COMPUTING 2011年第1期11卷 645-651页

作者： Kampolis, Ioannis C. Giannakoglou, Kyriakos C. Natl Tech Univ Athens Lab Thermal Turbomachines Parallel CFD & Optimizat Unit Athens 15710 Greece

This paper presents the synergetic use of different evaluation tools, parameterization schemes and search methods on the levels of a multilevel optimization platform to efficiently solve single-and multi-objective computationally demanding optimization problems. The platform is formed by a number of levels which concurrently search for optimal solutions, by regularly exchanging promising individual solutions. Each level is associated with a problem-specific evaluation tool with its own accuracy and computational cost, a parameterization scheme which determines the design variables and their mapping to generate individual solutions and a search algorithm which is either a metamodel-assisted evolutionary algorithm or a gradient-based method. The use of the multilevel platform with only one of the aforementioned features changing from level to level was presented in a previous paper by the authors. The present paper shows that the combined use of hierarchical evaluation, hierarchical parameterization and hierarchical search decreases further the computational cost by increasing the efficiency of the optimization method. This is demonstrated on function minimization and aerodynamic shape optimization problems;though only two levels are used herein, this is not a restriction and the optimization platform may accommodate any number of them. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Design optimization Evolutionary algorithms Metamodels Gradient-based optimization multilevel algorithm Hierarchical search

来源：评论

学校读者我要写书评

暂无评论

A Cartesian non-uniform grid interpolation method for fast field evaluation on elongated domains

引用

INTERNATIONAL JOURNAL OF NUMERICAL MODELLING-ELECTRONIC NETWORKS DEVICES AND FIELDS 2012年第5-6期25卷 645-655页

作者： Costa, Nadav Boag, Amir Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

An algorithm for performing a fast evaluation on time harmonic fields radiated by two-dimensional source constellations with elongated geometry is introduced. The suggested scheme attains a linear computational complexity. At the core of the algorithm is the idea of phase and amplitude compensation facilitating the conversion of fields radiated by spatially confined sources into bandlimited functions of the suitable coordinates. Thus, the fields or potentials are represented by their samples on sparse left-side and right-side non-uniform Cartesian grids. These grids are employed both for the representation of outgoing fields and as targets for accumulating the incoming fields. Integrating this approach with the divide-and-conquer strategy, the algorithm relies on a binary hierarchical decomposition of the computational domain. The total field is computed via a two-way multilevel process, which passes through all of the left-side and right-side grids, while systematically aggregating all subdomains' contributions, ending with the field interpolation back to the desired observation points. Copyright (c) 2012 John Wiley & Sons, Ltd.

关键词： integral equations fast solvers multilevel algorithm field computation non-uniform grid

来源：评论

学校读者我要写书评

暂无评论

A multilevel decoupled method for a mixed Stokes/Darcy model

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2012年第9期236卷 2452-2465页

作者： Cai, Mingchao Mu, Mo Worcester Polytech Inst Dept Math Sci Worcester MA USA Hong Kong Univ Sci & Technol Dept Mathematics Hong Kong Hong Kong Peoples R China

This paper studies decoupled numerical methods for a mixed Stokes/Darcy model for coupling fluid and porous media flows. A two-level algorithm is proposed and analyzed in Mu and Xu (2007) [10]. We generalize the two-level algorithm to a multilevel algorithm in this paper and present numerical analysis on the error estimates for the multilevel algorithm. The multilevel algorithm solves the mixed Stokes/Darcy system by applying efficient legacy code for single model solvers to solve two decoupled Stokes and Darcy subproblems on all the subsequently refined meshes, except for a much smaller global problem only on a very coarse initial mesh. Numerical experiments are conducted for both the two-level and multilevel algorithms to illustrate their effectiveness and efficiency, and validate the related theoretical analysis. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Coupling fluid and porous media flows Stokes equations Darcy's law Multi-domain problems Two-level method multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive nonuniform-grid (NG) algorithm for fast capacitance extraction

引用

IEEE TRANSACTIONS ON MICROWAVE THEORY AND TECHNIQUES 2006年第9期54卷 3565-3570页

作者： Boag, Amix Livshitz, Boris Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

A novel method for computing the capacitance matrices of arbitrary shaped three-dimensional geometries is presented. The proposed approach combines a novel nommiform-grid (NG) algorithm for fast evaluation of potentials due to given source distributions with an iterative solution of the pertinent integral equations. The NG algorithm is based on the observation that locally the potential produced by a finite size source can be interpolated from its samples at a small number of points of a nonuniform spherical grid. This observation leads to a multilevel algorithm comprising interpolation and aggregation of potentials. The resulting hierarchical algorithm attains an O(N) asymptotic complexity and memory requirements. The computational efficiency is further improved for quasi-planar geometries by the use of adaptive grids.

关键词： capacitance extraction circuit simulation fast algorithm iterative solver multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

A multilevel DIFFUSION METHOD FOR DYNAMIC LOAD BALANCING

引用

PARALLEL COMPUTING 1993年第2期19卷 209-218页

作者： HORTON, G Lehrstuhl f&uuml r Rechnerstrukturen Universit&auml t Erlangen-N&uuml rnberg Martensstr. 3 8520 Erlangen Federal Republic of Germany

We consider the problem of dynamic load balancing for multiprocessors, for which a typical application is a parallel finite element solution method using non-structured grids and adaptive grid refinement. This type of application requires communication between the subproblems which arises from the interdependencies in the data. A load balancing algorithm should ideally not make any assumptions about the physical topology of the parallel machine. Further requirements are that the procedure should be both fast and accurate. An new multi-level algorithm is presented for solving the dynamic load balancing problem which has these properties and whose parallel complexity is logarithmic in the number of processors used in the computation.

关键词： DYNAMIC LOAD BALANCING PARALLEL COMPUTING DISTRIBUTED-MEMORY MULTIPROCESSOR multilevel algorithm

来源：评论

学校读者我要写书评

暂无评论

Improving the convergence rate of the DIRECT global optimization algorithm

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第4期67卷 851-872页

作者： Liu, Qunfeng Yang, Guang Zhang, Zhongzhi Zeng, Jinping Dongguan Univ Technol Coll Comp Sci & Technol Dongguan 523808 Peoples R China

DIRECT is derivative-free global-search algorithm has been found to perform robustly across a wide variety of low-dimensional test problems. The reason DIRECT's robustness is its lack of algorithmic parameters that need be "tuned" to make the algorithm perform well. In particular, there is no parameter that determines the relative emphasis on global versus local search. Unfortunately, the same algorithmic features that enable DIRECT to perform so robustly have a negative side effect. In particular, DIRECT is usually quick to get close to the global minimum, but very slow to refine the solution to high accuracy. This is what we call DIRECT's "eventually inefficient behavior." In this paper, we outline two root causes for this undesirable behavior and propose modifications to eliminate it. The paper builds upon our previously published "MrDIRECT" algorithm, which we can now show only addressed the first root cause of the "eventually inefficient behavior." The key contribution of the current paper is a further enhancement that allows MrDIRECT to address the second root cause as well. To demonstrate the effectiveness of the enhanced MrDIRECT, we have identified a set of test functions that highlight different situations in which DIRECT has convergence issues. Extensive numerical work with this test suite demonstrates that the enhanced version of MrDIRECT does indeed improve the convergence rate of DIRECT.

关键词： Global optimization multilevel algorithm DIRECT algorithm MrDIRECT algorithm Convergence rate

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：