Accession Number:

ADA063965

Title:

Exploiting Structure in Fixed-Point Computation.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

• Todd,Michael J.

Report Date:

1978-08-01

Pagination or Media Count:

30.0

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.

Descriptors:

• *LINEAR PROGRAMMING
• *SIMULTANEOUS EQUATIONS
• ALGORITHMS
• MATRICES(MATHEMATICS)
• CONVERGENCE
• COMPUTER APPLICATIONS
• MAPPING(TRANSFORMATIONS)
• CONVEX SETS
• TRIANGULATION

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE