A sorting-assisted fast algorithm for fractal dimension and BDS-type statistics

Abstract

Presentamos un algoritmo rápido para calcular el histograma de distancias C(m, E ) en el que se basan los estadísticos de tipo BDS, que se apoya en el ordenamiento de los datos. El algoritmo calcula el histograma simultáneamente para conjuntos de valores de m y E, como el algoritmo rápido generalizado de Mayer (2000) sin perder mucha velocidad. Cuando el conjunto de valores de E se limita a valores pequeños, el algoritmo es de orden N. Implementamos también el algoritmo de cajas de orden N de Grassberger (1990), incluyendo los casos m = 1 y r> 1. Utilizando corridas experimentales encontramos que el algoritmo basado en el ordenamiento rebasa en un orden de magnitud al de cajas cuando N toma valores en los cientos de miles.

We present a sorting-assisted fast algorithm to calculate the distance histogram C(m, E) on which BDS-type statistics are based. The algorithm calculates C(m, E) for sets of values of m and E simultaneously, as in Mayer's (2000) generalized fast algorithm, without loosing much speed. When the E set has a small bound, the algorithm is order N. We also implement Grassberger's (1990) order N box-assisted algorithm including the cases m = 1 and r> 1. In experimental runs we find that the sorting-assisted overtakes the box-assisted algorithm by an order of magnitude for values of N in the hundred thousands.