Fast Allan Variance (FAVAR) and Dynamic Fast Allan Variance (D-FAVAR) Algorithms for both Regularly and Irregularly Sampled Data

This work develops algorithms demonstrating fast implementations of Allan variance (AVAR) for regularly and irregularly sampled signals. AVAR is a technique first developed to study the frequency stability of atomic clocks. Typical AVAR algorithms calculate changes in means between differently-sized groupings of data and thus are useful in many data aggregation processes: to select the appropriate window length or timescales for estimating a signal’s moving average, to find the minimum variance of a signal, or to estimate the change in variance of a signal with complex noise contributions as a function of the number of collected data points. Unfortunately, AVAR typically involves very large signal lengths, yet the typical time required to compute AVAR increases quickly with the length of the time-series data. This paper presents a recursive algorithm inspired by the Fast Fourier Transform (FFT), specifically data organization into power-of-two groupings. This enables a fast AVAR implementation, called FAVAR, shown first for regularly sampled data. The results show a computational speed increase of three orders of magnitude versus typical AVAR calculations for data lengths often used with AVAR. Next, the FAVAR algorithm is extended to compute AVAR of irregularly sampled data by modeling these data as weighted but regularly sampled data clusters. Finally, this work analyzes Dynamic Allan variance implementations of FAVAR, called D-FAVAR, wherein AVAR is calculated at every timestep to capture window-varying statistical properties of the data stream. The recursion methods used in FAVAR, when extended to compute D-FAVAR, further increase computational speed by an additional factor of ten compared to computing the FAVAR at every timestep. They result in approximately four orders of magnitude speed improvements versus repeated calculation of AVAR with typical methods. These fast algorithms are demonstrated on signals that illustrate classical Allan variance curves, and the results agree with the classical AVAR formulations within computational accuracy.