Exploiting Structure in Fixed-Point Computation.

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA063965

Entities

People

  • Michael J. Todd

Organizations

  • University of Wisconsin–Madison

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Boundary Value Problems
  • Computational Complexity
  • Computational Science
  • Computations
  • Computer Programming
  • Equations
  • Linear Programming
  • Linearity
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Standards
  • Theorems
  • Triangulation
  • United States

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Graph Algorithms and Convex Optimization.