Browsing by Author "Walker, Homer F."

Now showing 1 - 5 of 5
  • Thumbnail Image
    Experiments with Conjugate Gradient Algorithms for Homotopy Curve Tracking
    Irani, Kashmira M.; Kamat, Manohar P.; Ribbens, Calvin J.; Walker, Homer F.; Watson, Layne T. (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 homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernal of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. Here variants of the conjugate gradient algorithm are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned conjugate gradient method used in HOMPACK. The test problems used include actual large scale, sparse structural mechanics problems.
  • HOMPACK90: A Suite of FORTRAN 90 Codes for Globally Convergent Homotopy Algorithms
    Watson, Layne T.; Sosonkina, Masha; Melville, Robert C.; Morgan, Alexander P.; Walker, Homer F. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1996-07-01)
    HOMPACK90 is a FORTRAN 90 version of the FORTRAN 77 package HOMPACK (Algorithm 652), a collection of codes for finding zeros or fixed points of nonlinear systems using globally convergent probability-one homotopy algorithms. Three qualitatively different algorithms - ordinary differential equation based, normal flow, quasi-Newton augmented Jacobian matrix - are provided for tracking homotopy zero curves, as well as separate routines for dense and sparse Jacobian matrices. A high level driver for the special case of polynomial systems is also provided. Changes to HOMPACK include numerous minor improvements, simpler and more elegant interfaces, use of modules, new end games, support for several sparse matrix data structures, and new iterative algorithms for large sparse Jacobian matrices.
  • Thumbnail Image
    Least Change Secant Update Methods for Undetermined Systems
    Walker, Homer F.; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)
    Least-change secant updates for nonsquare matrices have been addressed recently in [6]. Here we consider the use of these updates in iterative procedures for the numerical solution of underdetermined systems. Our model method is the normal flow algorithm used in homotopy or continuation methods for determining points on an implicitly defined curve. A Kantorovich-type local convergence analysis is given which supports the use of least-change secant updates in this algorithm. This analysis also provides a Kantorovich-type local convergence analysis for least-change secant update methods in the usual case of an equal number of equations and unknowns. This in turn gives a local convergence analysis for augmented Jacobian algorithms which use least-change secant updates. We conclude with the results of some numerical experiments. Key words. underdetermined systems, least-change secant update methods, quasi-Newton methods, normal flow algorithm, augmented Jacobian matrix algorithm, continuation methods, homotopy methods, curve-tracking algorithms, parameter-dependent systems
  • Thumbnail Image
    Preconditioned Conjugate Gradient Algorithms for Homotopy CurveTracking
    Irani, Kashmira M.; Ribbens, Calvin J.; Walker, Homer F.; Watson, Layne T.; Kamat, Manohar P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)
    These are alogorithms 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 homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian Matrices. The HOMPACK alogorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. Here variants of the conjugate gradient algorithms are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned conjugate gradient method used in HOMPACK. The test problems used include actual large scale, sparse structural mechanics problems.
  • Thumbnail Image
    Preconditioned Iterative Methods for Homotopy Curve Tracking
    DeSa, Colin; Irani, Kashmira M.; Ribbens, Calvin J.; Watson, Layne T.; Walker, Homer F. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1991-05-01)
    Homotopy algorithms are a class of methods for solving systems of nonlinear equations that are globally convergent with probability one. All homotopy algorithms are based on the construction of an appropriate homotopy map and then the tracking of a curve in the zero set of this homotopy map. The curve-tracking algorithms used here require the solution of a series of very special systems. In particular, each (n + 1) x (n + 1) system is in general nonsymmetric but has a leading symmetric indefinite n x n submatrix (typical of large structural mechanics problems, for example). Furthermore, the last row of each system may by chosen (almost) arbitrarily. The authors seek to take advantage of these special properties. The iterative methods studied here include Craig's variant of the conjugate gradient algorithm and the SYMMLQ algorithm for symmetric indefinite problems. The effectiveness of various preconditioning strategies in this context are also investigated, and several choices for the last row of the systems to be solved are explored.