Applicability of Incremental Iterative Algorithms

In computer science there has been much interest in iteration as a procedure for obtaining the solution of a system of equations. The applicability of iteration does not depend strongly on the form or properties of the system of equations. Its use ranges from solution of numerical equations to data-flow analysis. Also the problem of finding incremental algorithms which adjust a solution to a small change in parameters has received much attention recently and is of particular importance for large problems such as arise in data-flow analysis. In this paper we show that one cannot always continue iterating from a previous solution after even a small change in parameters; we give conditions under which it is legitimate to do so. This result follows a brief discussion of iteration in general. We consider finding a fixed point, X, by iteration of a monotonic function, W, on a partially ordered set Q. This differs somewhat from previous developments in that, beyond monotonicity, W is no further constrained, Q need not be a semi-lattice, and X need not be reachable by a finite number of iterations.Technical report DCS-TR-15