Asymptotic complexity of inverse nonstationary phase shift

Marcus R. Wilson, Robert James Ferguson

We perform a speed test on an optimized conjugate-gradient based inversion to correct for surface statics and irregular spatial sampling. An ideally preconditioned scheme is run repeatedly on synthetic trace gathers of random size, up to 215 traces. The runtime and the number of conjugate gradient iterations required for each trial is recorded. Iteratively refined polynomial regression is performed on the resulting data points to estimate the asymptotic complexity of the algorithm, and the number of conjugate gradient iterations is compared with the overall runtime to check for consistency. We find that the ideal preconditioned scheme gives a near optimal runtime of O(n1.082 ), which indicates that the method could feasibly be preconditioned to run on large data sets.