摘要
The calculation of correlation dimension is a key problem of the fractals. The standard algorithm requires O（N2） computations. The previous improvement methods endeavor to sequentially reduce redundant computation on condition that there are many different dimensional phase spaces, whose application area and performance improvement degree are limited. This paper presents two fast parallel algorithms： O （N^2/p ＋ logp） time p processors PRAM algo- rithm and O（N^2/p） time p processors LARPBS algorithm. Analysis and results of numeric computation indicate that the speedup of parallel algorithms relative to sequence algorithms is efficient. Compared with the PRAM algorithm, The LARPBS algorithm is practical, optimally scalable and cost optimal.
The calculation of correlation dimension is a key problem of the fractals. The standard algorithm requires O（N2） computations. The previous improvement methods endeavor to sequentially reduce redundant computation on condition that there are many different dimensional phase spaces, whose application area and performance improvement degree are limited. This paper presents two fast parallel algorithms： O （N^2/p ＋ logp） time p processors PRAM algo- rithm and O（N^2/p） time p processors LARPBS algorithm. Analysis and results of numeric computation indicate that the speedup of parallel algorithms relative to sequence algorithms is efficient. Compared with the PRAM algorithm, The LARPBS algorithm is practical, optimally scalable and cost optimal.
基金
This project was supported by the National Natural Science Foundation of China(60273075) .
