Analysis of the numerical stability of algorithms

The aim of this paper is to show the importance of the numerical behavior of formulations in the field of the concrete complexity of algorithms. Up to now many studies have been published to propose an implementation of a given algorithm requiring the least number of computations. This code sometimes provides results which are less accurate than a code requiring more computations because its numerical stability is worse. Since the numerical value of the data influences the numerical behavior of algorithms, it is not generally possible to obtain the optimum implementation. Consequently it is necessary to have a tool to automatically analyze the numerical stability of algorithms. This tool is the Permutation-Perturbation software. This paper analyzes the numerical stability of four implementations of the Fast Fourier algorithm using this software.