On Paths Generated by Fixed Point Algorithms

This paper considers algorithms that compute fixed points (or more generally solve equations) which are based on complementary pivoting. These algorithms, starting with a map f⁰ and its fixed point x₀, deform f^t to f^∞ = f as t goes from 0 to ∞, and follow the path x_t of fixed points of f^t. In this paper we study these paths. In particular, we treat some special applications of these algorithms from a global point of view, and thus look at the behavior and properties of these paths sufficiently far from the solution. Our methods are motivated by methods of global analysis.

We show that in many implementations of these algorithms the path can be specified. These include the cases when the mapping is linear and when it is smooth and monotone. The results of the linear analysis are used to study the local behavior of these paths (i.e., properties and behavior sufficiently close to the solution) for smooth mappings.

An important implication of this study is that the paths can be modified and thus the work done by these algorithms can be controlled. We also show, for smooth mappings, how our results can be implemented to increase the efficiency of some standard algorithms.