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

A new treecode for long-range force calculation

COMPUTER PHYSICS COMMUNICATIONS 2008年第2期178卷 121-127页

作者： Ahn, Cheol-O Lee, Sang Hwan Hanyang Univ Sch Mech Engn Seoul 133791 South Korea

We propose a new hierarchical tree algorithm with high adaptivity to various particle distributions for long-range force calculations. This algorithm divides parent cells into k daughter cells using the k-means algorithm. The tree structure provided by this algorithm is independent of the coordinate system used. This method also includes a unique procedure for determining cell sizes adjusted to particle distributions. We investigated the characteristics of the tree structure and the effect on the long-range force calculation performance of various branching ratios k. The results of numerical experiments using various particle distributions showed that the number of interactions between particles and cells grows with k, but the number of distance evaluations between particles and cells decreased when k is around 5. We can therefore select an optimized value of k according to the characteristics of the problem to be analyzed. Comparing the algorithm to Barnes-Hut treecode using gravitational calculations at the same error level, we found that the calculation cost could be decreased remarkably. (C) 2007 Elsevier B.V. All rights reserved.

关键词： tree data structure treecode octtree long-range force

来源：评论

学校读者我要写书评

暂无评论

Variable order revised binary treecode

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2004年第1期200卷 192-210页

作者： Wang, QX Nanyang Technol Univ Maritime Res Ctr Singapore 630798 Singapore

Three essential improvements are described to the treecode in terms of the expansion formula, the choice of the expansion order as well as the tree structure. Firstly, the multipole expansion is based on the real spherical harmonic functions to reduce the CPU time. Secondly, the expansion order is given in terms of the ratio of the distance of a field point to a source box to the box size, which reflects the relative error of the expansion. With that, a large portion of the sources has been evaluated by the multipole expansion at low levels of the source tree, which is around two-thirds of sources at the first two levels of the tree averagely. The algorithm reduces the CPU time dependency on expansion order p from O(p(2)) of the classical treecode to be lower than a linear dependency in p(max), where p(max) is the maximum expansion order used in the variable order expansion. Thirdly, a revised binary tree is built by performing the bisections thrice at each tree level, discarding the boxes generated in the first two bisections and remaining only the boxes generated in the last one. This tree avoids the disadvantage of a binary treecode demanding significantly more CPU time than an oct-treecode. It has high adaptiveness to the source distribution and perfect load balancing for performing the parallelization. Simulations are carried out for N vortex elements and N field points distributed randomly in a cube, a 5:1:1 parallelepiped, and a 10:1:1 parallelepiped, using the oct-tree and revised binary tree, respectively. The algorithm is an order of magnitude faster than those of Strickland et al. [ESAIM: Proceedings 7 (1999) 408], Warren and Salmon [Comput. Phys. Commun. 87 (1995) 266], and Lindsay and Krasny [J. Comput. Phys. 172 (2001) 879]. Simulations also demonstrate the efficiency of the revised binary treecode for an inhomogeneous source distribution. (C) 2004 Elsevier Inc. All rights reserved.

关键词： treecode fast adaptive algorithm multipole expansion revised binary tree vortex method

来源：评论

学校读者我要写书评

暂无评论

On preconditioning the treecode-accelerated boundary integral (TABI) Poisson-Boltzmann solver

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2018年 373卷 750-762页

作者： Chen, Jiahui Geng, Weihua Southern Methodist Univ Dept Math Dallas TX 75275 USA

We recently developed a treecode-accelerated boundary integral (TABI) solver for solving Poisson-Boltzmann (PB) equation H. The solver has combined advantages in accuracy, efficiency, memory, and parallelization as it applies a well-posed boundary integral formulation to circumvent many numerical difficulties associated with the PB equation and uses an 0 (N log N) treecode to accelerate the GMRES iterative solver. However, as observed in our previous work [2], occasionally when the mesh generator produces low quality triangles, the number of GMRES iterations required to solve the discretized boundary integral equations Ax = b could be large. To address this issue, we design a preconditioning scheme using preconditioner matrix M such that M-1 A has much improved condition while M-1 z can be rapidly computed for any vector z. In this scheme, the matrix M carries the interactions between boundary elements on the same leaf only in the tree structure thus is block diagonal with many computational advantages. The sizes of the blocks in M are conveniently controlled by the treecode parameter N-0, the maximum number of particles per leaf. The numerical results show that this new preconditioning scheme improves the TABI solver with significantly reduced iteration numbers and better accuracy, particularly for protein sets on which TABI solver previously converges slowly. In addition, this preconditioning scheme potentially can improve the condition number of various multipole method accelerated boundary elements solvers in scattering, fluids, elasticity, etc. Published by Elsevier Inc.

关键词： treecode Electrostatic Boundary integral Poisson-Boltzmann Preconditioning GMRES

来源：评论

学校读者我要写书评

暂无评论

A FAST treecode FOR MULTIQUADRIC INTERPOLATION WITH VARYING SHAPE PARAMETERS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2012年第2期34卷 A1126-A1140页

作者： Deng, Quan Driscoll, Tobin A. Univ Delaware Dept Math Newark DE 19716 USA

A treecode algorithm is presented for the fast evaluation of multiquadric radial basis function (RBF) approximations. The method is a dual approach to one presented by Krasny and Wang, which applies far-field expansions to clusters of RBF centers (source points). The new approach clusters evaluation points instead and is therefore easily able to cope with basis functions that have different multiquadric shape parameters. The new treecode is able to evaluate an approximation on N centers at M points in O((N + M) log M) time in the ideal case when evaluation points are uniformly distributed. When coupled with a two-level restricted additive Schwarz preconditioner for GMRES iterations, the treecode is well suited for use within an adaptive RBF iteration, previously described by Driscoll and Heryudono, as is demonstrated by experiments on test functions.

关键词： radial basis function interpolation treecode restricted additive Schwarz method

来源：评论

学校读者我要写书评

暂无评论

A treecode-accelerated boundary integral Poisson-Boltzmann solver for electrostatics of solvated biomolecules

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2013年 247卷 62-78页

作者： Geng, Weihua Krasny, Robert Univ Alabama Dept Math Tuscaloosa AL 35487 USA Univ Michigan Dept Math Ann Arbor MI 48109 USA

We present a treecode-accelerated boundary integral (TABI) solver for electrostatics of solvated biomolecules described by the linear Poisson-Boltzmann equation. The method employs a well-conditioned boundary integral formulation for the electrostatic potential and its normal derivative on the molecular surface. The surface is triangulated and the integral equations are discretized by centroid collocation. The linear system is solved by GMRES iteration and the matrix-vector product is carried out by a Cartesian treecode which reduces the cost from O(N-2) to O(N log N), where N is the number of faces in the triangulation. The TABI solver is applied to compute the electrostatic solvation energy in two cases, the Kirkwood sphere and a solvated protein. We present the error, CPU time, and memory usage, and compare results for the Poisson-Boltzmann and Poisson equations. We show that the treecode approximation error can be made smaller than the discretization error, and we compare two versions of the treecode, one with uniform clusters and one with non-uniform clusters adapted to the molecular surface. For the protein test case, we compare TABI results with those obtained using the grid-based APBS code, and we also present parallel TABI simulations using up to eight processors. We find that the TABI solver exhibits good serial and parallel performance combined with relatively simple implementation, efficient memory usage, and geometric adaptability. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Electrostatics Solvated biomolecule Poisson-Boltzmann equation Boundary integral equation treecode

来源：评论

学校读者我要写书评

暂无评论

A Parallel Adaptive treecode Algorithm for Evolution of Elastically Stressed Solids

引用

Communications in Computational Physics 2014年第2期15卷 365-387页

作者： Hualong Feng Amlan Barua Shuwang Li Xiaofan Li Department of Applied Mathematics Illinois Institute of TechnologyChicagoIL 60616USA. School of Science Nanjing University of Science and TechnologyNanjingJiangsu 210094P.R.China.

The evolution of precipitates in stressed solids is modeled by coupling a quasi-steady diffusion equation and a linear elasticity equation with dynamic boundary *** governing equations are solved numerically using a boundary integral method(BIM).A critical step in applying BIM is to develop fast algorithms to reduce the arithmetic operation count of matrix-vector *** this paper,we develop a fast adaptive treecode algorithm for the diffusion and elasticity problems in two dimensions(2D).We present a novel source dividing strategy to parallelize the *** results show that the speedup factor is nearly perfect up to a moderate number of *** approach of parallelization can be readily implemented in other treecodes using either uniform or non-uniform point *** demonstrate the effectiveness of the treecode by computing the long-time evolution of a complicated microstructure in elastic media,which would be extremely difficult with a direct summation method due to CPU time *** treecode speeds up computations dramatically while fulfilling the stringent precision requirement dictated by the spectrally accurate BIM.

关键词： treecode parallel elasticity boundary integral method.

来源：评论

学校读者我要写书评

暂无评论

FAST EVALUATION OF MULTIQUADRIC RBF SUMS BY A CARTESIAN treecode

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2011年第5期33卷 2341-2355页

作者： Krasny, Robert Wang, Lei Univ Michigan Dept Math Ann Arbor MI 48109 USA Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA

A treecode is presented for evaluating sums defined in terms of the multiquadric radial basis function (RBF), phi(x) = (vertical bar x vertical bar(2) + c(2))(1/2), where x is an element of R-3 and c >= 0. Given a set of N nodes, evaluating an RBF sum directly requires CPU time that scales like O(N-2). For a given level of accuracy, the treecode reduces the CPU time to O(N log N) using a far-field expansion of phi(x). We consider two options for the far-field expansion: (1) a Laurent series previously used in applications of the Fast Multipole Method to multiquadric RBFs, and (2) a certain Taylor series previously used in treecode particle simulations, but not yet in the context of multiquadric RBFs. It is known that the Laurent series converges when the RBF parameter c lies in an interval 0 <= c <= (c) over bar, where (c) over bar is proportional to the minimum node spacing, but here we show that the Taylor series converges uniformly for c >= 0. We implement the treecode in Cartesian coordinates and use a recurrence relation to compute the Taylor coefficients. Numerical results exhibit the treecode error, CPU time, and memory usage in two test cases, random nodes in a cube and on the surface of a sphere. The treecode approach presented here is applicable to generalized multiquadrics in any dimension.

关键词： fast summation multiquadric radial basis function treecode Taylor series

来源：评论

学校读者我要写书评

暂无评论

Hermite Interpolation In The treecode Algorithm

Hermite Interpolation In The Treecode Algorithm

引用

作者： Benjamin St. Aubin University of Wisconsin – Milwaukee

学位级别：硕士

In this thesis, a treecode implementing Hermite interpolation is constructed to approximate a summation of pairwise interactions on large data sets. Points are divided into a hierarchical tree structure and the interactions between points and well-separated clusters are approximated by interpolating the kernel function over the cluster. Performing the direct summation takes O(N^2) time for system size N, and evidence is presented to show the method presented in this paper scales with O(N logN) time. Comparisons between this method and existing ones are made, highlighting the relative simplicity and adaptability of this process. Parallelization of the computational step is implemented by splitting the data set into pieces whose interactions are independently calculated on separate CPU cores. Additionally, steps are taken to make this approximation more efficient, allowing greater precision to be achieved without increasing completion time. Results are presented for the 3D 1/r and Screened Coulomb Potential exp(-kr)/r kernels on random data sets in size up to 10^7.

关键词： hermite treecode Mathematics

来源：评论

学校读者我要写书评

暂无评论

A treecode to simulate dust-plasma interactions

引用

PLASMA PHYSICS AND CONTROLLED FUSION 2017年第2期59卷 025002-025002页

作者： Thomas, D. M. Holgate, J. T. Imperial Coll London Blackett Lab London SW7 2BW England

The interaction of a small object with surrounding plasma is an area of plasma-physics research with a multitude of applications. This paper introduces the plasma octree code pot, a microscopic simulator of a spheroidal dust grain in a plasma. pot uses the Barnes-Hut treecode algorithm to perform N-body simulations of electrons and ions in the vicinity of a chargeable spheroid, employing also the Boris particle-motion integrator and Hutchinson's reinjection algorithm from SCEPTIC;a description of the implementation of all three algorithms is provided. We present results from pot simulations of the charging of spheres in magnetised plasmas, and of spheroids in unmagnetized plasmas. The results call into question the validity of using the Boltzmann relation in hybrid PIC codes.

关键词： dusty plasma treecode Boris integrator SCEPTIC reinjection

来源：评论

学校读者我要写书评

暂无评论

Relativistic space-charge field calculation by interpolation-based treecode

引用

COMPUTER PHYSICS COMMUNICATIONS 2023年第1期286卷

作者： Kan, Yi-Kai Kaertner, Franz X. Le Borne, Sabine Zemke, Jens-Peter M. Deutsch Elektronen Synchrotron DESY Ctr Free Electron Laser Sci CFEL Hamburg Germany Univ Hamburg Dept Phys Hamburg Germany Hamburg Univ Technol Inst Math Hamburg Germany

Space-charge effects are of great importance in particle accelerator physics. In the computational modeling, tree-based methods are increasingly used because of their effectiveness in handling nonuniform particle distributions and/or complex geometries. However, they are often formulated using an electrostatic force which is only a good approximation for low energy particle beams. For high energy, i.e., relativistic particle beams, the relativistic interaction kernel may need to be considered and the conventional treecode fails in this scenario. In this work, we formulate a treecode based on Lagrangian interpolation for computing the relativistic space-charge field. Two approaches are introduced to control the interpolation error. In the first approach, a modified admissibility condition is proposed for which the treecode can be used directly in the lab-frame. The second approach is based on the transformation of the particle beam to the rest-frame where the conventional admissibility condition can be used. Numerical simulation results using both methods will be compared and discussed.(c) 2023 Elsevier B.V. All rights reserved.

关键词： treecode Space-charge field calculation Separable approximation Admissibility condition Special relativity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：