Algebraic Systems of Equations and Computational Complexity Theory, Softcover reprint of the original 1st ed. 1994 Coll. Mathematics and Its Applications, Vol. 269

Significant progress has been made during the last fifteen years in the solution of nonlinear systems, particularly in computing fixed points, solving systems of nonlinear equations and applications to equilibrium models. This volume presents a self-contained account of recent work on simplicial and continuation methods applied to the solution of algebraic equations. The contents are divided into eight chapters. Chapters 1 and 2 deal with Kuhn's algorithm, Chapter 3 considers Newton's method, and a comparison between Kuhn's algorithm and Newton's method is presented in Chapter 4. The following four chapters discuss respectively, incremental algorithms and their cost theory, homotopy algorithms, zeros of polynomial mapping, and piecewise linear algorithms. For researchers and graduates interested in algebraic equations and computational complexity theory.

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.