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

Stability of a pivoting strategy for parallel Gaussian elimination

BIT NUMERICAL MATHEMATICS 2001年第3期41卷 633-639页

作者： Mead, JL Renaut, RA Welfert, BD Boise State Univ Dept Math & Comp Sci Boise ID 83725 USA Arizona State Univ Dept Math Tempe AZ 85287 USA

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as a means for reducing communications in parallel implementations, In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by mu (n) < 3(n-1), as compared to 2(n-1) for the standard partial pivoting. This bound (n), close to 3(n-2), is attainable for a class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.

关键词： Gaussian elimination parallel algorithm growth factor stability

来源：评论

学校读者我要写书评

暂无评论

Solving the hydrodynamic formulation of quantum mechanics: A parallel MLS method

引用

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY 2001年第4-5期85卷 263-271页

作者： Brook, RG Oppenheimer, PE Weatherford, CA Banicescu, I Zhu, JP Mississippi State Univ Engn Res Ctr Mississippi State MS 39762 USA Florida A&M Univ Dept Phys Tallahassee FL 32307 USA Mississippi State Univ Dept Comp Sci Mississippi State MS 39762 USA Mississippi State Univ Dept Math & Stat Mississippi State MS 39762 USA

This article documents the first implementation of a parallel algorithm for solving the governing equations of the hydrodynamic formulation of quantum mechanics. The algorithm employs a quantum trajectory method (QTM) based on the serial algorithm introduced by Wyatt and Lopreore. The OpenMP API is employed to parallelize the code across the quantum trajectories in a shared memory environment. An outline of the parallel algorithm is provided;the analytical solution for a moving free particle is used to verify the solution obtained by the parallel algorithm. Further validation against several of the results obtained by Wyatt and Lopreore is also provided. The parallel speedups and runtimes are presented, and several performance issues are noted. Finally, the results of a preliminary accuracy study examining a moving free particle are provided. (C) 2001 John Wiley & Sons, Inc.

关键词： scattering theory wave-packet methods hydrodynamic formulation meshless methods quantum trajectory methods parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving the hydrodynamic formulation of quantum mechanics: A parallel MLS method

Solving the hydrodynamic formulation of quantum mechanics: A...

引用

41st International Symposium on Atomic, Molecular, and Condensed Matter Theory

关键词： scattering theory wave-packet methods hydrodynamic formulation meshless methods quantum trajectory methods parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Study of the parallel block one-sided Jacobi method 9th

引用

9th International Conference on High-Performance Computing and Networking

作者： Daoudi, EM Lakhouaja, A Outada, H Univ Mohamed 1st Fac Sci Dept Math & Comp Sci LaRI Lab Oujda 60000 Morocco

ISBN: (纸本)3540422935

In this paper, we study the paxallelization of the one-sided Jacobi method for computing the eigenvalues and the eigenvectors of a real and symmetric matrix. We use a technique to overlap the communications by the computations in order to decrease the global communication time. We also extend the obtained results to the block version for using the level-3 BLAS.

关键词： eigenvalue problem Jacobi method parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved generalization of mesh-connected computers with multiple buses

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2001年第3期12卷 293-305页

作者： Pan, Y Zheng, SQ Li, KQ Shen, H Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Univ Texas Dept Comp Sci Richardson TX 75083 USA SUNY Albany Dept Math & Comp Sci New Paltz NY 12561 USA Griffith Univ Sch Comp & Informat Technol Nathan Qld 4111 Australia

Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant 0 < < 1, one can construct an N-1/2 x N-1/2 square IMMB using which semigroup and prefix computations on N operands can be carried out in O(N-) time, while maintaining 0(1) broadcasting time. Compared with the previous best complexities O(N-1/6) and O(N-1/16) achieved on a rectangular MMB and GMMB, respectively, for the same computations, our results show that IMMBs are more powerful than MMBs and GMMBs.

关键词： bus mesh-connected computer mesh-connected computer with multiple buses parallel algorithm parallel architecture parallel computing processor array

来源：评论

学校读者我要写书评

暂无评论

parallel implementation of a large-scale 3-D air pollution model 3rd

引用

3rd International Conference on Large-Scale Scientific Computing (ICLSSC 2001)

作者： Ostromsky, T Zlatev, Z Bulgarian Acad Sci Cent Lab Parallel Processing BU-1113 Sofia Bulgaria Natl Environm Res Inst Dept Atmospher Environm DK-4000 Roskilde Denmark

ISBN: (纸本)3540430431

Air pollution models can efficiently be used in different environmental studies. The atmosphere is the most dynamic component of the environment, where the pollutants can be transported over very long distances. Therefore the models must be defined on a large space domain. Moreover, all relevant physical and chemical processes must be adequately described. This leads to huge computational tasks. That is why it is difficult to handle numerically such models even on the most powerful up-to-date supercomputers. The particular model used in this study is the Danish Eulerian Model. The numerical methods used in the advection-diffusion part of this model consist of finite elements (for discretizing the spatial derivatives) followed by predictor-corrector schemes with several different correctors (in the numerical treatment of the resulting systems of ordinary differential equations). Implicit methods for the solution of stiff systems of ordinary differential equations are used in the chemistry part. This implies the use of Newton-like iterative methods. A special sparse matrix technique is applied in order to increase the efficiency. The model is constantly updated with new faster and more accurate numerical methods. The three-dimensional version of the Danish Eulerian Model is presented in this work. The model is defined on a space domain of 4800 km x 4800 km that covers the whole of Europe together with parts of Asia, Africa and the Atlantic Ocean. A chemical scheme with 35 species is used in this version. Two parallel implementations are discussed;the first one for shared memory parallel computers, the second one - the newly developed version for distributed memory computers. Standard tools are used to achieve parallelism: OpenMP for shared memory computers and MPI for distributed memory computers. Results from many experiments, which were carried out on a SUN SMP cluster and on a CRAY T3E at the Edinburgh parallel Computer Centre (EPCC), are presented and analyzed.

关键词： air pollution model system of PDE's parallel algorithm shared memory computer distributed memory computer OpenMP MPI

来源：评论

学校读者我要写书评

暂无评论

Constructing voronoi diagrams in the L₁ metric using the geographic nearest neighbors

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2001年第7期E84A卷 1755-1760页

作者： Wee, Y Faculty members of Ajou University Suwon South Korea

This paper introduces a new approach based on the geographic nearest neighbors for constructing the Delaunay triangulation (a dual of the Voronoi diagram) of a aet of n sites in the plane under the L-1 metric. In general, there is no inclusion relationship between the Delaunay triangulation and the octant neighbor graph. We however find that under the L1 metric the octant neighbor graph contains at least one edge of each triangle in the Delaunay triangulation. By using this observation and employing a range tree scheme, we design an algorithm for constructing the Delaunay triangulation (thus the Voronoi diagram) in the L1 metric. This algorithm takes O(n log n) sequential time for constructing the Delaunay triangulation in the L1 metric. This algorithm can easily be parallelized, and takes O(log n) time with O(n) processors on a CREW-PRAM.

关键词： computational geometry Voronoi diagram parallel algorithm L-1 metric

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant algorithm for Fast Fourier Transform on hypercubes

引用

INFORMATION PROCESSING LETTERS 2001年第1期79卷 11-16页

作者： Chen, YW Chung, KL Natl Taiwan Univ Sci & Technol Dept Informat Manaagement Taipei 10672 Taiwan Natl Taiwan Univ Sci & Technol Inst Informat Engn Taipei 10672 Taiwan Aletheia Univ Dept Comp & Informat Sci Taipei 25103 Taiwan

Consider an input sequence of 2(n) data and an n-dimensional hypercube, H-n, with n - 1 faulty nodes. This short paper presents an efficient fault-tolerant algorithm for Fast Fourier Transform (FFT) with these 2(n) data on the faulty H-n in 9n - 15 communication steps and O(n) computation steps. To the best of our knowledge, this is the first time that such a fault-tolerant algorithm for FFT on hypercubes is proposed in the literature. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： Fast Fourier Transform fault tolerance free dimensions faulty hypercube parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved fault-tolerant sorting algorithm in hypercubes

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期255卷 649-658页

作者： Chen, YW Chung, KL Natl Taiwan Univ Sci & Technol Inst Comp Sci & Informat Engn Dept Informat Management Taipei 10672 Taiwan Natl Taiwan Univ Sci & Technol Inst Comp Sci & Informat Engn Inst Informat Engn Taipei 10672 Taiwan

Consider M unsorted elements and an n-dimensional hypercube H-n with [3n/2] - 1 faulty nodes, where M much greater than N = 2(n). Employing a newly proposed partition strategy and the light-occupied dimension concept, this paper improves Sheu et al.'s algorithm [Sheu, Chen, Chang, J. parallel Distributed Comput, 16 (1992) 185] for sorting these M unsorted elements on the faulty H-n. With the same time bound O((M/N)log(M/N) + (M/N)log(2) N) as [Sheu et al., 1992], the proposed algorithm can tolerate [n/2] more faulty nodes than Sheu et al.'s algorithm which can tolerate at most n -1 faulty nodes. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： fault tolerance hypercube parallel algorithm parallel sorting

来源：评论

学校读者我要写书评

暂无评论

Optimal parallelization of a recursive algorithm for triangular matrix inversion on MIMD computers

引用

parallel COMPUTING 2001年第13期27卷 1767-1782页

作者： Nasri, W Mahjoub, Z Fac Sci Tunis Dept Informat Tunis 1060 Tunisia

This paper studies the parallelization of a recursive algorithm for triangular matrix inversion (TMI), using the "divide and conquer" paradigm. For a (large scale) matrix of size n = m2(k) (m,k greater than or equal to 1) and p = 2(q) (less than or equal to n/2) available processors, we first construct an adequate 2-phases task segmentation and inducing a balanced layered task graph. Then. we design a greedy scheduling leading to a cost optimal parallel algorithm, i.e. whose efficiency is equal to 1 for large n. The practical interest of the contribution is proven through an experimental study of two versions of the original algorithm on an IBM SP1 distributed memory multiprocessor. (C) 2001 Published by Elsevier Science B.V.

关键词： divide and conquer parallel algorithm recursive schemes scheduling load balancing triangular matrix inversion

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：