熊海灵, 杨志敏, 李航. 基于非并行布朗运动的土壤胶体分形凝聚模拟算法改进[J]. 农业工程学报, 2015, 31(6): 129-134. DOI: doi:10.3969/j.issn.1002-6819.2015.06.018
    引用本文: 熊海灵, 杨志敏, 李航. 基于非并行布朗运动的土壤胶体分形凝聚模拟算法改进[J]. 农业工程学报, 2015, 31(6): 129-134. DOI: doi:10.3969/j.issn.1002-6819.2015.06.018
    Xiong Hailing, Yang Zhimin, Li Hang. Improved simulation algorithm for soil colloid fractal aggregation based on unparallel Brownian motion[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2015, 31(6): 129-134. DOI: doi:10.3969/j.issn.1002-6819.2015.06.018
    Citation: Xiong Hailing, Yang Zhimin, Li Hang. Improved simulation algorithm for soil colloid fractal aggregation based on unparallel Brownian motion[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2015, 31(6): 129-134. DOI: doi:10.3969/j.issn.1002-6819.2015.06.018

    基于非并行布朗运动的土壤胶体分形凝聚模拟算法改进

    Improved simulation algorithm for soil colloid fractal aggregation based on unparallel Brownian motion

    • 摘要: 耗时长是目前进行大规模体系分形凝聚模拟的主要障碍。该文采用优化存储结构来降低时间复杂度的思路,对传统On-lattice集团凝聚模型算法进行了改进。用三维数组表征模拟体系,用链表表征团簇结构,实现了在体系中直接访问任意团簇,以及确定组成团簇单粒在三维数组中对应数组元素具体位置的新方法。论文基于新的存储结构重新设计了集团凝聚模型中布朗运动、碰撞检测和凝聚的算法,使得模拟算法的总时间复杂度从立方阶变为了线性阶。该改进算法为研究人员进行大规模体系分形凝聚模拟提供了技术支撑。

       

      Abstract: Abstract: The cluster-cluster aggregation (CCA) model bridges the study of colloid aggregation by computer simulation and laboratory experiment. Two distinct and limiting regimes of irreversible colloid aggregation have been identified by computer simulation with the CCA model. One regime is diffusion-limited cluster aggregation (DLCA) corresponding to the rapid colloid aggregation. The other is reaction-limited cluster aggregation (RLCA) corresponding to the slow colloid aggregation. The simulations of the two regimes are both start with N non-overlapping identical particles distributed randomly in a cubic box with side-lengths of L. A three dimensional array, hypothetically named CubeLLL, was usually used to represent the cubic box. Each particle in the cubic box occupies an element of the three dimensional array and are labeled with a different integer. When particles and/or clusters collide and aggregate, all particles in the resulting cluster are modified with the same label (one of them). The progression of Brownian movement and aggregation are realized by updating the labels of the corresponding array elements. However, a critical issue in this kind of simulation is how to efficiently distinguish all of the particles in any selected cluster only based on the three dimensional array CubeLLL when the cluster is to be moved. Similarly, there are difficulties in the process of collision detection to locate all neighboring positions of the cluster. The traditional method must perform exhaustive search in the whole system, what's more, this kind of exhaustive search will repeated over and over again in the simulation progression. In this paper, the traditional on-lattice CCA algorithm is optimized by improving the storage structure to reduce the time complexity, in which the simulation system is represented by a three dimensional array, while the clusters in the system are simultaneously stored by the linked lists respectively in programming. Another one dimensional array ClusterN is used to organize the linked lists and store the basic attributes of the clusters in the system. Initially, N linked lists, each only has one node, are created for the N randomly placed particles. After a cluster is moved, its particles is examined to determine whether any other clusters have been contacted via nearest neighbor occupancy. If aggregation does occur after the collision detection, the simple operation is to link the corresponding clusters. After an aggregation, the array Cluster should be indexed simultaneously because there may be some vacant linked lists. In the later random selection for the potential movement, these vacant linked lists should not be in the candidate lists. For the indexing, a one dimensional array IndexN is used to store the non-vacant linked list subscripts of the array ClusterN. The current length of the Index is the number of the remaining clusters in the system. For example, if the new generated random number for the random selection is k, the label of the next moving cluster should be Index k, and the linked list of this cluster is exactly linked by Cluster Indexk. From this entry, all the particles in the cluster can be easily accessed. And then, the positions of the six neighboring boxes of each particle in the cluster can also be accessed by the element subscripts of the array Cube, which is needed for the collision detection. Brownian motion, collision detection and aggregation as the basic operations in the CCA simulation are all improved based on the compounded data structure. The results show that the new algorithm achieves linear time complexity from three cubed time complexity. This is a great contribution for researchers in large scale simulation of fractal aggregation.

       

    /

    返回文章
    返回