关联维数的并行求解算法  

The Research of Parallel Correlation Dimension Calculation

作　　者：蒋廷耀[1] 李庆华[2] 杨景华 

机构地区：[1]三峡大学电气信息学院,宜昌443000 [2]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2004年第7期169-170,F004,共3页Computer Science

基　　金：国家自然科学基金(No.60273075)

摘　　要：关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要。过去的改进算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数.其应用范围和性能改善程度是有限的。本文给出了两个并行算法:基于PRAM模型的花费O(N^2/p+logp)时间p个处理机的算法,和基于LARPBS模型的花费O(N^2/p)时间p个处理机的算法。相对纯理论的PRAM算法,LARPBS算法是实际可行的,它是目前时间复杂度最低的算法,并且是最优可扩展和成本最优的。The calculation of correlation dimension is a key problem of the fractal dimension. The standard algorithm requires O(N^2) computations. The previous improvement methods endeavor to sequentially reduce redundant computation on condition that there are many different dimensional phase spaces. The application area and performance improvement degree are limited,e, g. ,they are not adequate for real time tasks. This paper presents a O(N^2/p+1ogp) time p processors parallel PRAM algorithm and a O(N^2) time p processors parallel LARPBS algorithm. The speedup of parallel algorithms is efficient. Compared with the PRAM algorithm, The LARPBS algorithm is practical. It is optimally scalable and cost optimal. To our best knowledge, it is the fastest algorithm for correlation dimension calculation so far.

关 键 词：关联维数 并行算法 分形理论 PRAM模型 LARPBS模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]