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

Characterization of the accuracy of the fast multipole method in particle simulations

InTERnATIOnAL JOURnAL FOR nUMERICAL METHODS In EnGInEERInG 2009年第13期79卷 1577-1604页

作者： Cruz, Felipe A. Barba, L. A. Univ Bristol Dept Math Bristol BS8 1TW Avon England

The fast multipole method (FMM) is a fast summation algorithm capable of accelerating pairwise interaction calculations, known as n-body problems, from an algorithmic complexity of O(n-2) to O(n) for n particles. The algorithm has brought a dramatic increase in the capability of particle simulations in many application areas, such as electrostatics, particle formulations of fluid mechanics, and others. Although the literature on the subject provides theoretical error bounds for the FMM approximation, there are not many reports on the measured errors in a suite of computational experiments that characterize the accuracy of the method in relation with the different parameters available to the user. We have performed such an experimental investigation, and summarized the results of about 1500 calculations using the FMM algorithm, applied to the 2D vortex particle method. In addition to the more standard diagnostic of the maximum error, we supply illustrations of the spatial distribution of the errors, offering visual evidence of all the contributing factors to the overall approximation accuracy: multipole expansion, local expansion, hierarchical spatial decomposition (interaction lists, local domain, far domain). This presentation is a contribution to any researcher wishing to incorporate the FMM acceleration to their application code, as it aids in understanding where accuracy is gained or compromised. Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： fast multipole method order-n algorithms particle methods vortex method hierarchical algorithms

来源：评论

学校读者我要写书评

暂无评论

PetRBF - A parallel O(n) algorithm for radial basis function interpolation with Gaussians

引用

COMPUTER METHODS In APPLIED MECHAnICS AnD EnGInEERInG 2010年第25-28期199卷 1793-1804页

作者： Yokota, Rio Barba, L. A. Knepley, Matthew G. Boston Univ Dept Engn Mech Boston MA 02215 USA Univ Bristol Dept Math Bristol BS8 1TW Avon England Univ Chicago Computat Inst Chicago IL 60637 USA

We have developed a parallel algorithm for radial basis function (RBF) interpolation that exhibits O(n) complexity, requires O(n) storage, and scales excellently up to a thousand processes. The algorithm uses a GMHS iterative solver with a restricted additive Schwarz method (RASM) as a preconditioner and a fast matrix-vector algorithm. Previous fast RBF methods - achieving at most O(nlogn) complexity - were developed using multiquadric and polyharmonic basis functions. In contrast, the present method uses Gaussians with a small variance with respect to the domain, but with sufficient overlap. This is a common choice in particle methods for fluid simulation, our main target application. The fast decay of the Gaussian basis function allows rapid convergence of the iterative solver even when the subdomains in the RASM are very small. At the same time we show that the accuracy of the interpolation can achieve machine precision. The present method was implemented in parallel using the PETSC library (developer version). numerical experiments demonstrate its capability in problems of RBF interpolation with more than 50 million data points, timing at 106 s (19 iterations for an error tolerance of 10(-15)) on 1024 processors of a Blue Gene/L (700 MHz PowerPC processors). The parallel code is freely available in the open-source model. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Radial basis function interpolation Domain decomposition methods GMRES order-n algorithms Particle methods Parallel computing

来源：评论

学校读者我要写书评

暂无评论

PetFMM-A dynamically load-balancing parallel fast multipole library

引用

InTERnATIOnAL JOURnAL FOR nUMERICAL METHODS In EnGInEERInG 2011年第4期85卷 403-428页

作者： Cruz, Felipe A. Knepley, Matthew G. Barba, L. A. Boston Univ Dept Mech Engn Boston MA 02215 USA Univ Bristol Dept Math Bristol BS8 1TW Avon England Univ Chicago Computat Inst Chicago IL 60637 USA

Fast algorithms for the computation of n-body problems can be broadly classified into mesh-based interpolation methods, and hierarchical or multiresolution methods. To this latter class belongs the well-known fast multipole method (FMM), which offers O(n) complexity. The FMM is a complex algorithm, and the programming difficulty associated with it has arguably diminished its impact, being a barrier for adoption. This paper presents an extensible parallel library for n-body interactions utilizing the FMM algorithm. A prominent feature of this library is that it is designed to be extensible, with a view to unifying efforts involving many algorithms based on the same principles as the FMM and enabling easy development of scientific application codes. The paper also details an exhaustive model for the computation of tree-based n-body algorithms in parallel, including both work estimates and communications estimates. With this model, we are able to implement a method to provide automatic, a priori load balancing of the parallel execution, achieving optimal distribution of the computational work among processors and minimal inter-processor communications. Using a client application that performs the calculation of velocity induced by n vortex particles in two dimensions, ample verification and testing of the library was performed. Strong scaling results are presented with 10 million particles on up to 256 processors, including both speedup and parallel efficiency. The largest problem size that has been run with the PetFMM library at this point was 64 million particles in 64 processors. The library is currently able to achieve over 85% parallel efficiency for 64 processes. The performance study, computational model, and application demonstrations presented in this paper are limited to 2D. However, the software architecture was designed to make an extension of this work to 3D straightforward, as the framework is templated over the dimension. The software library is open sou

关键词： fast multipole method order-n algorithms particle methods vortex method hierarchical algorithms parallel computing dynamic load balancing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：