Algebraic Systems of Equations and Computational Complexity Theory

Inhaltsverzeichnis

• Chpater 1 Kuhn’s algorithm for algebraic equations.
• §1. Triangulation and labelling.
• §2. Complementary pivoting algorithm.
• §3. Convergence, I.
• §4. Convergence, II.
• 2 Efficiency of Kuhn’s algorithm.
• §1. Error estimate.
• §2. Cost estimate.
• §3. Monotonicity problem.
• §4. Results on monotonicity.
• 3 Newton method and approximate zeros.
• §1. Approximate zeros.
• §2. Coefficients of polynomials.
• §3. One step of Newton iteration.
• §4. Conditions for approximate zeros.
• 4 A complexity comparison of Kuhn’s algorithm and Newton method.
• §1. Smale’s work on the complexity of Newton method.
• §2. Set of bad polynomials and its volume estimate.
• §3. Locate approximate zeros by Kuhn’s algorithm.
• §4. Some remarks.
• 5 Incremental algorithms and cost theory.
• §1. Incremental algorithms Ih, f.
• §2. Euler’s algorithm is of efficiency k.
• §3. Generalized approximate zeros.
• §4. Ek iteration.
• §5. Cost theory of Ek as an Euler’s algorithm.
• §6. Incremental algorithms of efficiency k.
• 6 Homotopy algorithms.
• §1. Homotopies and Index Theorem.
• §2. Degree and its invariance.
• §3. Jacobian of polynomial mappings.
• §4. Conditions for boundedness of solutions.
• 7 Probabilistic discussion on zeros of polynomial mappings.
• §1. Number of zeros of polynomial mappings.
• §2. Isolated zeros.
• §3. Locating zeros of analytic functions in bounded regions.
• 8 Piecewise linear algorithms.
• §1. Zeros of PL mapping and their indexes.
• §2. PL approximations.
• §3. PL homotopy algorithms work with probability one.
• References.
• Acknowledgments.