Iterative Algorithms for Fixed Point Comutation

Abstract

We compare two algorithms for computing fixed points of functionals of the kind arising in static program analysis. One is a rather direct calculation of the iterands, whereas the other employs the technique of iterative squaring. To give meaningful results about the time and space requirements we need to be more specific about the form of the functionals and the properties of the functions upon which the functionals operate. In this paper we consider functionals in iterative versus (two kinds of) primitive recursive forms, and functions that are monotone versus completely additive.

The time complexity of the direct algorithm is proportional to the number of iterations and the size of the domain of the functions. Replacing the direct algorithm with the iterative squaring algorithm gives an exponential reduction in the number of iterations needed. If the program analysis can be formulated in the completely additive framework, we will in some instances obtain an exponential reduction in the cost of each iteration.