Exploiting Structure in Fixed-Point Computation.
Technical summary rept.,
WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
We consider the recent algorithms for computing fixed points of zeros of continuous functions from R to the nth power to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings that arise when these fixed-point algorithms with their usual triangulations are applied to computing zeros of functions f with special structure f is either linear in certain variables, separable, or has Jacobian with small bandwidth. Each of these structures leads to a property we call modularity the algorithmic path within a simplex can be continued into an adjacent simplex without a function evaluation or linear programming pivot. Modularity also arises without any special structure on f from the linearity of the function that is deformed to f.
- Theoretical Mathematics