Browsing by Author "Billups, Stephen C."

Now showing 1 - 3 of 3
  • Thumbnail Image
    An augmented Jacobian matrix algorithm for tracking homotopy zero curves
    Billups, Stephen C. (Virginia Polytechnic Institute and State University, 1985)
    There are algorithms for finding zeros or fixed points of nonlinear systems of (algebraic) equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. The augmented Jacobian matrix algorithm is part of the software package HOMPACK, and is based on an algorithm developed by W.C. Rheinboldt. The algorithm exists in two forms-one for dense Jacobian matrices, and the other for sparse Jacobian matrices.
  • Thumbnail Image
    HOMPACK: A Suite of Codes for Globally Convergent Homotopy Algorithms
    Watson, Layne T.; Billups, Stephen C.; Morgan, Alexander P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotoppy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK provides three qualitatively different algorithms for tracking the homotopy zero curve: ordinary differential equation based, normal flow, and augmented Jacobian matrix. Separate routines are also provided for dense and sparse Jacobian matrices. A high level driver is included for the special case of polynomial systems.
  • Thumbnail Image
    A Probability-one Homotopy Algoithm for Non-Smooth Equations and Mixed Complementarity Problems
    Billups, Stephen C.; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 2000)
    A probability-one homotopy algorithm for solving nonsmooth equations is described. This algorithm is able to solve problems involving highly nonlinear equations,where the norm of the residual has non-global local minima.The algorithm is based on constructing homotopy mappings that are smooth in the interior of their domains.The algorithm is specialized to solve mixed complementarity problems through the use of MCP functions and associated smoothers.This specialized algorithm includes an option to ensure that all iterates remain feasible.Easily satisfiable sufficient conditions are given to ensure that the homotopy zero curve remains feasible,and global convergence properties for the MCP algorithm are developed.Computational results on the MCPLIB test library demonstrate the effectiveness of the algorithm.