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

parallel Scientific Computation: A Structured Approach using BSP and MPI

2004年

作者： Rob H. Bisseling

ISBN: (数字)9780191712869

ISBN: (纸本)9780198529392

This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.

关键词： bulk synchronous parallel communication fast Fourier transform linear system message-passing interface parallel algorithm parallel programming sparse matrix-vector multiplication

来源：评论

学校读者我要写书评

暂无评论

K-medoids Clustering Based on MapReduce and Optimal Search of Medoids 9

K-medoids Clustering Based on MapReduce and Optimal Search o...

引用

9th IEEE International Conference on Computer Science and Education (ICCSE)

作者： Zhu, Ying-ting Wang, Fu-zhang Shan, Xing-hua Lv, Xiao-yan China Acad Railway Sci Railway Technol Res Coll Beijing Peoples R China China Acad Railway Sci Inst Comp Technol Beijing Peoples R China

ISBN: (纸本)9781479929511

When there are noises and outliers in the data, the traditional k-medoids algorithm has good robustness, however, that algorithm is only suitable for medium and small data set for its complex calculation. MapReduce is a programming model for processing mass data and suitable for parallel computing of big data. Therefore, this paper proposed an improved algorithm based on MapReduce and optimal search of medoids to cluster big data. Firstly, according to the basic properties of triangular geometry, this paper reduced calculation of distances among data elements to help search medoids quickly and reduce the calculation complexity of k-medoids. Secondly, according to the working principle of MapReduce, Map function is responsible for calculating the distances between each data element and medoids, and assigns data elements to their clusters;Reduce function will check for the results from Map function, search new medoids by the optimal search strategy of medoids again, and return new results to Map function in the next MapReduce process. The experiment results showed that our algorithm in this paper has high efficiency and good effectiveness.

关键词： MapReduce k-medoids parallel algorithm cluster analysis data mining

来源：评论

学校读者我要写书评

暂无评论

Application of the alternating direction method of multipliers to separable convex programming problems

引用

Computational Optimization and Applications 1992年第1期1卷 93-111页

作者： Fukushima, Masao Department of Applied Mathematics and Physics Faculty of Engineering Kyoto University Kyoto 606 Japan

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established. © 1992 Kluwer Academic Publishers.

关键词： alternating direction method of multipliers Convex programming decomposition parallel algorithm separable problems

来源：评论

学校读者我要写书评

暂无评论

Practical Message-passing Framework for Large-scale Combinatorial Optimization 3

Practical Message-passing Framework for Large-scale Combinat...

引用

IEEE International Conference on Big Data

作者： Cho, Inho Park, Soya Park, Sejun Han, Dongsu Shin, Jinwoo Korea Adv Inst Sci & Technol Daejeon South Korea

ISBN: (纸本)9781479999255

Graphical Model (GM) has provided a popular framework for big data analytics because it often lends itself to distributed and parallel processing by utilizing graph-based 'local' structures. It models correlated random variables where in particular, the max-product Belief Propagation (BP) is the most popular heuristic to compute the most-likely assignment in GMs. In the past years, it has been proven that BP can solve a few classes of combinatorial optimization problems under certain conditions. Motivated by this, we explore the prospect of using BP to solve generic combinatorial optimization problems. The challenge is that, in practice, BP may converge very slowly and even if it does converge, the BP decision often violates the constraints of the original problem. This paper proposes a generic framework that enables us to apply BP-based algorithms to compute an approximate feasible solution for an arbitrary combinatorial optimization task. The main novel ingredients include (a) careful initialization of BP messages, (b) hybrid damping on BP updates, and (c) post-processing using BP beliefs. Utilizing the framework, we develop parallel algorithms for several large-scale combinatorial optimization problems including maximum weight matching, vertex cover and independent set. We demonstrate that our framework delivers high approximation ratio, speeds up the process by parallelization, and allows large-scale processing involving billions of variables.

关键词： Combinatorial optimization Belief propagation parallel algorithm Maximum weighted matching

来源：评论

学校读者我要写书评

暂无评论

Planar Graph Perfect Matching is in NC 59

Planar Graph Perfect Matching is in NC

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Anari, Nima Vazirani, Vijay V. Stanford Univ Dept Comp Sci Stanford CA 94305 USA Univ Calif Irvine Dept Comp Sci Irvine CA USA

ISBN: (纸本)9781538642306

Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution. In this paper, we give an NC algorithm for finding a perfect matching in a planar graph. Our algorithm uses the above-stated fact about counting matchings in a crucial way. Our main new idea is an NC algorithm for finding a face of the perfect matching polytope at which many new conditions, involving constraints of the polytope, are simultaneously satisfied. Several other ideas are also needed, such as finding a point in the interior of the minimum weight face of this polytope and finding a balanced tight odd set in NC.

关键词： parallel algorithm planar graph perfect matching Tutte matrix Pfaffian

来源：评论

学校读者我要写书评

暂无评论

Handel-c design enhancement for FPGA-based DV decoder

引用

2nd International Workshop on Reconfigurable Computing

作者： Cichon, Slawomir Gorgon, Marek Pac, Miroslaw AGH Univ Sci & Technol Biocybernet Lab Dept Automat PL-30059 Krakow Poland

ISBN: (纸本)354036708X

In the paper the authors present an implementation of the algorithm of DV Decoder conformant to IEC-61834-2 standard in reprogrammable resources. A software implementation has been realized and then transferred to the Handel-C language. By parallelization of the algorithm and using language mechanisms in Handel-C the processing efficiency has been increased 10 times with respect to the initial hardware implementation. The implementation has been verified in hardware-software environment with real data transmitted on-line from a DV camcorder.

关键词： parallel algorithm high level languages video decompression field programmable gate array

来源：评论

学校读者我要写书评

暂无评论

A Large-Scale Distributed Sorting algorithm Based on Cloud Computing 6th

A Large-Scale Distributed Sorting Algorithm Based on Cloud C...

引用

6th International Conference on Applications and Techniques in Information Security (ATIS)

作者： Pang, Na Zhu, Dali Fan, Zheming Rong, Wenjing Feng, Weimiao Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

ISBN: (纸本)9783662486832;9783662486825

Large amounts of data processing bring parallel computing into sharp focus. In order to solve the sorting problem of large-scale data in the era of internet, a large-scale distributed sorting algorithm based on cloud computing is proposed. The algorithm uses the ideas of quick-sort and merge-sort to sort and integrate the data on each cloud, which making best of clouds' computing and storage resources. Taking advantage of the idea of parallel computing, we can reduce the computing time and improve the efficiency of sorting. By evaluating algorithm's time complexity and organizing a simulation test, the effectiveness was verified.

关键词： Cloud computing parallel algorithm Quick sort Merge sort Distributed computing

来源：评论

学校读者我要写书评

暂无评论

Novel algorithms for quantum simulation of 3D atom-diatom reactive scattering

Novel algorithms for quantum simulation of 3<i>D</i> atom-di...

引用

International Conference on Computational Science and Its Applications (ICCSA 2007)

作者： Gevorkyan, Ashot S. Balint-Kurti, Gabriel G. Bogdanov, Alexander Nyman, Gunnar NAS Armenia Inst Informat & Automat Problems P Sevak St 1 Yerevan 375014 Armenia Univ Bristol Sch Chem Bristol BS8 1TS Avon England Inst High Performance Comp & Informat Syst St Petersburg 195251 Russia Univ Gothenburg Dept Chem SE-41296 Gothenburg Sweden

ISBN: (纸本)9783540744825

A new approach is described to the evaluation of the S-matrix in three-dimensional atom-diatom reactive quantum scattering theory. A theory based on natural collision coordinates is developed, where the reaction coordinate can be viewed as fulfilling the same role as time in a time-dependent formulation. By writing the full wavefunction in coupled-channel form it is proved that the 3D multi-channel quantum reactive scattering problem can be treated in the same way as an inelastic single-arrangement problem. In particularly in the work two type coupled-channel representations;which lead to to two different systems of coupled-channel differential equations. The first system of coupled-channel equations is solved with the help of the R-matrix propagation method yielding simultaneously the full wavefunction and all S-matrix elements without further calculation. The second one is treated similarly. In this way we avoid a great volume of grid computations for 1D Schrodinger problem. The both algorithms use the intrinsic symmetry of scattering body-system;which allows to carry out maximally effective parallel computations of 3D scattering problem.

关键词： quantum scattering S-matrix elements coupled-channel differential equations R-matrix method parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Large Scale Distributed Matrix Computation with Spark 3

Efficient Large Scale Distributed Matrix Computation with Sp...

引用

IEEE International Conference on Big Data

作者： Gu, Rong Tang, Yun Wang, Zhaokang Wang, Shuai Yin, Xusen Yuan, Chunfeng Huang, Yihua Nanjing Univ Collaborat Innovat Ctr Novel Software Technol & I Natl Key Lab Novel Software Technol Nanjing 210093 Jiangsu Peoples R China Intel Corp Beijing 100190 Peoples R China

ISBN: (纸本)9781479999255

Matrix computation is the core of many massive data-intensive analytical applications such mining social networks, recommendation systems and nature language processing. Due to the importance of matrix computation, it has been widely studied for many years. In the Big Data ear, as the scale of the matrix grows, traditional single-node matrix computation systems can hardly cope with such large data and computation. Existing distributed matrix computation solutions are still not efficient enough, or have poor fault tolerance and usability. In this paper, we propose Marlin, an efficient distributed matrix computation library which is built on top of Spark. Marlin contains several distributed matrix operation algorithms and provides high-level matrix computation primitives for users. In Marlin, we proposed three distributed matrix multiplication algorithms for different situations. Based on this, we designed an adaptive model to choose the best approach for different problems. Moreover, to improve the computation performance, instead of naively using Spark, we put forward some optimizations including taking advantage of the native linear algebra library, reducing shuffle communication and increasing parallelism. Experimental results show that Marlin is over an order of magnitude faster than R (a widely-used statistical computing system) and the existing distributed matrix operation algorithms based on MapReduce. Moreover, Marlin achieves comparable performance to the specialized MPI-based matrix multiplication algorithm SUMMA but uses a general dataflow engine and gains common dataflow features such as scalability and fault tolerance.

关键词： matrix computation parallel algorithm in-memory computing Spark

来源：评论

学校读者我要写书评

暂无评论

Efficient for RCS computation of long and complex dielectric objects

Efficient for RCS computation of long and complex dielectric...

引用

36th European Microwave Conference

作者： Perez, Saul Fares, M'Barek Souny, Bernard ENAC 7 Ave Edouard Belin BP 4005 F-31055 Toulouse France CERFACS F-31057 Toulouse France ENAC F-31055 Toulouse France

ISBN: (纸本)9782960055160

We propose a new method for RCS computation of long internally complex dielectric objects such as wind turbine blades. The method proposed here is an improved iterative algorithm whose convergence is proven. Thanks to the geometrical decomposition technique, three accelerating methods can be used efficiently In an iterative algorithm. The first accelerating method allows the elimination of the internal degrees of freedom with minimal cost. The second accelerating method (matrix compression QR) accelerates all the matrix vector products used in the preconditioning procedure as well as in the GMRES iterative resolution. The third accelerating method consists in using a "geometric neighboring" preconditioner adapted to the physical aspect of the problem.

关键词： integral equations method of moment parallel algorithm iterative methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：