Evaluation of three iterative
fixpoint algorithms
on randomly generated input
Niels Jørgensen
Abstract
Three iterative fixpoint algorithms are evaluated experimentally. The
input is a benchmark of randomly generated systems of equations over
boolean functions. The randomizer is designed to target certain presumed
weaknesses of the algorithms, rather than generate equations that are
presentative of real world input. The "winner" is perhaps the simplest of
the algorithms. It uses a variant of naive Kleene iteration and is found
to perform surprisingly well even on the benchmark's largest problems
comprising 1000 simultaneous equations. The second algorithm is a smarter
algorithm using a principle referred to in the paper as local
stabilization and which is based on an algorithm proposed by Le Charlier
et al. The test indicates
that the algorithm may perform a considerable amount of redundant work
when the dependency graph associated with the fixpoint problem contains
strongly connected components that are very large. Finally, the paper
presents a new variant of a chaotic worklist algorithm that incorporates
depth-first evaluation. It performs well on the given input, remaining on
the average within 25 % above the optimal number of iterations.
The difference between the latter two algorithms is discussed, on the
basis of their definition within a common setting.