摘要
关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要。过去的改进算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低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.
出处
《计算机科学》
CSCD
北大核心
2004年第7期169-170,F004,共3页
Computer Science
基金
国家自然科学基金(No.60273075)
