Computational complexity of a piecewise linear homotopy algorithm

DOI10.1007/BF02612356MaRDI QIDQ3321342zbMATH OpenOpenAlexFDO

Authors Romesh Saigal

Publication date 1984

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02612356

zbMATH Keywords

arithmetic complexityaverage behaviorlarge sparse nonlinear systemsworst case behaviorsimplicial homotopy algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to systems of equations (65H10)

Recommendations

• A Homotopy for Solving Large, Sparse and Structured Fixed Point Problems
• A new simple homotopy algorithm for linear programming. I
• Fast linear homotopy to find approximate zeros of polynomial systems
• scientific article; zbMATH DE number 710644
• An Optimal Complexity Algorithm for Computing the Topological Degree in Two Dimensions

Cites work

• scientific article; zbMATH DE number 3700117 (Why is no real title available?)
• A new variable dimension algorithm for the fixed point problem
• Computational complexity of complementary pivot methods
• Homotopies for computation of fixed points on unbounded regions
• On Paths Generated by Fixed Point Algorithms
• On the computational complexity of piecewise-linear homotopy algorithms
• The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
• The fundamental theorem of algebra and complexity theory

Cited in

(5)

• Model transform and local parameters. Application to instantaneous attractors
• Rudiments of an average case complexity theory for piecewise-linear path following algorithms
• A Homotopy for Solving Large, Sparse and Structured Fixed Point Problems
• Computing homotopic line simplification
• Efficiency and implementation of simplicial zero point algorithms

This page was built for publication: Computational complexity of a piecewise linear homotopy algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3321342)