关联维数的并行求解算法

摘要：

关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要.过去的改进算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N2)次的向量距离计算、距离比较和求和次数,其应用范围和性能改善程度是有限的.本文给出了两个并行算法:基于PRAM模型的花费O(N2/p+1ogp)时间p个处理机的算法,和基于LARPBS模型的花费O(N2/p)时间p个处理机的算法.相对纯理论的PRAM算法,LARPBS算法是实际可行的,它是目前时间复杂度最低的算法,并且是最优可扩展和成本最优的.

关键词：关联维数、并行、算法

所属期刊栏目：31

分类号：TV2;TP3

资助基金：国家自然科学基金60273075

在线出版日期：2004-08-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：169-170,封四