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

3rd International Congress on Mathematical Software

作者： Moerig, Marc Univ Magdeburg Dept Simulat & Graph Fac Comp Sci D-39106 Magdeburg Germany

ISBN: (纸本)9783642155819

Expression-dag-based number-types are a very general and user-friendly way to achieve exact geometric computation, a widely accepted approach to the reliable implementation of geometric algorithms. Such number-types record the computation history of a numerical value in an expression dag in order to allow for recomputing the value or an approximation of it at a later stage. We describe how to defer dag construction by using error-free transformations into sums of floating-point numbers. We store a limited number of summands in statically allocated memory in order to postpone or avoid dag creation which involves expensive dynamic memory allocations. Furthermore we report on experiments where we compare different implementation strategies of our new approach. The experiments show that for small polynomial expressions typically arising in geometric applications our approach is superior to existing expression-dag-based number-types in the presence of degenerate and nearly degenerate configurations and competitive otherwise.

关键词： expression dag exact geometric computation error-free transformations algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Better external memory suffix array construction

引用

ACM Journal of Experimental algorithmics 2008年第pp1–24期12卷 1-24页

作者： Dementiev, Roman Kärkkäinen, Juha Mehnert, Jens Sanders, Peter Universität Karlsruhe University of Helsinki Max-Planck-Institut für Informatik Fakultät für Informatik Universität Karlsruhe 76128 Karlsruhe Germany Department of Computer Science University of Helsinki FIN-00014 Helsinki Finland Max-Planck-Institut für Informatik 66123 Saarbrücken Stuhlsatzenhausweg 85 Germany

Suffix arrays are a simple and powerful data structure for text processing that can be used for full text indexes, data compression, and many other applications, in particular, in bioinformatics. However, so far, it has appeared prohibitive to build suffix arrays for huge inputs that do not fit into main memory. This paper presents design, analysis, implementation, and experimental evaluation of several new and improved algorithms for suffix array construction. The algorithms are asymptotically optimal in the worst case or on average. Our implementation can construct suffix arrays for inputs of up to 4-GB in hours on a low-cost machine. As a tool of possible independent interest, we present a systematic way to design, analyze, and implement pipelined algorithms. © 2008 ACM.

关键词： algorithm engineering algorithms for strings External memory I/O-efficient Large data sets Secondary memory Suffix array

来源：评论

学校读者我要写书评

暂无评论

Parallel Methods for Optimizing High Order Constellations on GPUs 29

Parallel Methods for Optimizing High Order Constellations on...

引用

29th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Spallaccini, Paolo Kayhan, Farbod Chinnici, Stefano Montorsi, Guido HCL Technol Italy SpA Via Cadorna 73 I-20090 Milan Italy Politecn Torino DET I-10129 Turin Italy

ISBN: (纸本)9781467376846

The increasing demand for fast mobile data has driven transmission systems to use high order signal constellations. Conventional modulation schemes such as QAM and APSK are sub- optimal;large gains may be obtained by properly optimizing the constellation signals set under given channel constraints. The constellation optimization problem is computationally intensive and the known methods become rapidly unfeasible as the constellation order increases. Very few attempts to optimize constellations in excess of 64 signals have been reported. In this paper, we apply a simulated annealing (SA) algorithm to maximize the Mutual Information (MI) and Pragmatic Mutual Information (PMI), given the channel constraints. We first propose a GPU accelerated method for calculating MI and PMI of a constellation. For AWGN channels the method grants one order of magnitude speedup over a CPU realization. We also propose a parallelization of the Gaussian-Hermite Quadrature to compute the Average Mutual Information (AMI) and the Pragmatic Average Mutual Information (PAMI) on GPUs. Considering the more complex problem of constellation optimization over phase noise channels, we obtain two orders of magnitude speedup over CPUs. In order to reach such performance, novel parallel algorithms have been devised. Using our method, constellations with thousands of signals can be optimized.

关键词： simulated annealing modulation constellation design Gaussian quadrature algorithm engineering GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

AN AUTOMATIZED METHODOLOGY DESIGN FOR REAL-TIME SIGNAL PROCESSING APPLICATIONS IN MULTIPLE MULTI-CORE PLATFORMS

AN AUTOMATIZED METHODOLOGY DESIGN FOR REAL-TIME SIGNAL PROCE...

引用

IEEE International Conference on Multimedia and Expo

作者： Spallaccini, Paolo Iovine, Francesco Italiano, Giuseppe F. Ericsson Telecomunicaz SpA R&D Dept Milan Italy Univ Roma Tor Vergata Dept Comp Sci Syst & Prod I-00161 Rome Italy

ISBN: (纸本)9781424442904

Implementing and engineering signal processing applications so that they effectively exploit the characteristics of novel multi-core and even multiple multi-core platforms represents a big challenge. In particular, in many signal processing applications several algorithms are invoked in cascade and concur in generating quite a complex code from the algorithmic and computational viewpoint, like for instance CODECs, which in addition must also cope with real-time constraints. In a major effort to improve the performance of this class of applications on multi-core processors, we present a novel design methodology based on a thread-level parallelization and several algorithmic optimizations, which deploy of state-of-the-art algorithm engineering techniques to obtain an "optimum job placement" on novel multiple multi-core platforms in a structured and automatized way. We introduce also some degree of parametrization, which depends on the architectural characteristics of the chosen platform. This allows the design methodology to be more flexible and adaptable to evolving hardware features such as the increasing number and the characteristics of cores, memory and/or peripherals availability. Our approach is based on the automatization of the design flow by identifying in a first step "parallel jobs", or "small threads" which, in a subsequent step, can be properly scheduled on the hardware resources available (cores), by taking into account also customized optimality criteria.

关键词： algorithm engineering signal processing CODEC multi-core methodology parallel processing

来源：评论

学校读者我要写书评

暂无评论

Time-Dependent SHARC-Routing

引用

16th Annual European Symposium on algorithms

作者： Delling, Daniel Univ Karlsruhe TH D-76128 Karlsruhe Germany

ISBN: (纸本)3540877436

In recent years, many speed-up techniques for Dijkstra's algorithm have been developed that make the computation of shortest paths in static road networks a matter of microseconds. However, only few of those techniques work in time-dependent networks which, unfortunately, appear quite frequently in reality: Roads are predictably congested by traffic jams, and efficient timetable information systems rely on time-dependent networks. Hence, a fast technique for routing in such networks is needed. In this work, we present an efficient time-dependent route planning algorithm. It is based on our recently introduced SHARC algorithm, which we adapt by augmenting its basic ingredients such that correctness can still be guaranteed in a time-dependent scenario. As a result, we are able to efficiently compute exact shortest paths in time-dependent continental-sized transportation networks, both of roads and of railways. It should be noted that time-dependent SHARC was the first efficient algorithm for time-dependent route planning.

关键词： algorithm engineering Graph algorithms Time-dependent shortest paths Timetable information

来源：评论

学校读者我要写书评

暂无评论

Tuning algorithms for Jumbled Matching 19

Tuning Algorithms for Jumbled Matching

引用

Prague Stringology Conference (PSC)

作者： Chhabra, Tamanna Ghuman, Sukhpal Singh Tarhio, Jorma Aalto Univ Dept Comp Sci POB 15400 FI-00076 Aalto Finland

ISBN: (纸本)9788001057872

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Most of our algorithms are variations of earlier algorithms. We show by practical experiments that our algorithms are competitive with the previous solutions.

关键词： jumbled matching Abelian matching permutation matching approximate string matching comparison of algorithms counting algorithm algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

An Empirical Comparison of k-Shortest Simple Path algorithms on Multicores 18

An Empirical Comparison of <i>k</i>-Shortest Simple Path Alg...

引用

47th International Conference on Parallel Processing (ICPP)

作者： Ajwani, Deepak Duriakova, Erika Hurley, Neil Meyer, Ulrich Schickedanz, Alexander Nokia Bell Labs Dublin Ireland Univ Coll Dublin Sch Comp Sci Insight Ctr Data Analyt Dublin Ireland Goethe Univ Frankfurt Germany

ISBN: (纸本)9781450365109

We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes. We find that even though the worst-case complexity of the best undirected KSP algorithm O (k (m + n log n)) is significantly better than that of the popular and considerably simpler directed KSP algorithm O(kn(m + n log n)), the two algorithms are fairly competitive in terms of their empirical performance on small diameter graphs. Furthermore, we show that a few simple optimisations help to bridge the gap between these KSP algorithms even more. However, on moderate to large diameter graphs, the undirected KSP algorithm is considerably faster than the directed algorithms, both in sequential and parallel settings. In terms of the parallelisation strategy, simply replacing the shortest path subroutine by parallel A-stepping algorithm can provide a good speed-up for many KSP algorithms on random graphs. In contrast, for graphs with skewed degree distribution, a more complex strategy of parallelizing the different deviations and then parallelizing the shortest path computation inside the deviations with the remaining threads, provides a better performance.

关键词： algorithm engineering Parallel k-Shortest Path Parallel Graph algorithms Parallel Single Source Shortest Path

来源：评论

学校读者我要写书评

暂无评论

Multiline Addressing by Network Flow

引用

14th Annual European Symposium on algorithms (ESA 2006)

作者： Eisenbrand, Friedrich Karrenbauer, Andreas Skutella, Martin Xu, Chihao Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Max Planck Inst Informat D-66123 Saarbrucken Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Univ Saarland Lehrstuhl Mikroelekt Saarbrucken Germany

ISBN: (纸本)3540388753

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the problem in mathematical terms yields a class of network flow problems where we group the arcs and pay in each group only for the arc carrying the maximum flow. We develop (fully) combinatorial approximation heuristics suitable for being implemented in the hardware of a control device that drives an OLED display.

关键词： Combinatorial optimization Network design OLED algorithm engineering Matrix decomposition

来源：评论

学校读者我要写书评

暂无评论

Contraction of Timetable Networks with Realistic Transfers

Contraction of Timetable Networks with Realistic Transfers

引用

9th International Symposium on Experimental algorithms

作者： Geisberger, Robert Karlsruhe Inst Technol D-76128 Karlsruhe Germany

ISBN: (纸本)9783642131929

We contribute a fast routing algorithm for timetable networks with realistic transfer times. In this setting, our algorithm is the first one that successfully applies precomputation based on node contraction: gradually removing nodes from the graph and adding shortcuts to preserve shortest paths. This reduces query times to 0.5 ins with preprocessing times below 4 minutes on all tested instances, even on continental networks with 30 000 stations. We achieve this by an improved contraction algorithm and by using a station graph model. Every node in our graph has a one-to-one correspondence to a station and every edge has an assigned collection of connections. Also, our graph model does not require parallel edges.

关键词： route planning public transit algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

algorithmic Aspects of Temporal Betweenness 20

Algorithmic Aspects of Temporal Betweenness

引用

26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Buss, Sebastian Molter, Hendrik Niedermeier, Rolf Rymar, Maciej TU Berlin Algorithm & Computat Complex Berlin Germany

ISBN: (纸本)9781450379984

The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In recent years, a growing number of real-world networks is modeled as temporal graphs instead of conventional (static) graphs. In a temporal graph, we have a fixed set of vertices and there is a finite discrete set of time steps and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered "optimal" with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality, posing new challenges on the algorithmic side. We provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths both on a theoretical and empirical level.

关键词： Network Science Network Centrality Temporal Graphs Temporal Paths Counting Complexity algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：