The Numerical Solution of Systems of Polynomials Arising in Engineering and Science

The following sections are included:

• Preface

• Contents

• Conventions

The following sections are included:

• Polynomials in One Variable

• Multivariate Polynomial Systems

• Trigonometric Equations as Polynomials

• Solution Sets

• Solution by Continuation

• Overview

• Exercises

The following sections are included:

• Continuation for Polynomials in One Variable

• Complex Versus Real Solutions

• Path Tracking

• Exercises

The following sections are included:

• Motivation: Quadratic Equations

• Definition of Projective Space

• The Projective Line ℙ¹

• The Projective Plane ℙ²

• Projective Algebraic Sets

• Multiprojective Space

• Tracking Solutions to Infinity

• Exercises

The following sections are included:

• Generic Points

• Example: Generic Lines

• Probabilistic Null Test

• Algebraic Probability One

• Numerical Certainty

• Other Approaches to Genericity

• Final Remarks

• Exercises

The following sections are included:

• Some Algebraic Facts about Polynomials of One Complex Variable

• Some Analytic Facts about Polynomials of One Complex Variable (Optional)

• Some Numerical Aspects of Polynomials of One Variable

• Exercises

The following sections are included:

• Exclusion Methods

• Elimination Methods
  • Resultants
    • Hidden Variable Resultants
    • u-Resultants
  • Numerically Confirmed Eliminants
  • Dixon Determinants
  • Heuristic Eliminants

• Gröbner Methods
  • Definitions
  • From Gröbner Bases to Eigenvalues

• More Methods

• Floating Point vs. Exact Arithmetic

• Discussion

• Exercises

The following sections are included:

• Coefficient-Parameter Theory

• Parameter Homotopy in Application

• An Illustrative Example: Triangles

• Nested Parameter Homotopies

• Side Conditions

• Homotopies that Respect Symmetry Groups

• Case Study: Stewart-Gough Platforms
  • General Case
  • Platforms with Coincident Joints
  • Planar Platforms
  • Summary of Case Study

• Historical Note: The Cheater's Homotopy

• Exercises

The following sections are included:

• A Hierarchy of Structures

• Notation

• Homotopy Paths for Linearly Parameterized Families

• Product Homotopies
  • Total Degree Homotopies
  • Multihomogeneous Homotopies
  • Linear Product Homotopies
  • Monomial Product Homotopies
  • Polynomial Product Homotopies

• Polytope Structures
  • Newton Polytopes and Mixed Volume
  • Bernstein's Theorem
  • Computing Mixed Volumes
  • Polyhedral Homotopies
  • Example

• A Summarizing Example

• Exercises

The following sections are included:

• Nash Equilibria

• Chemical Equilibrium

• Stewart-Gough Forward Kinematics

• Six-Revolute Serial-Link Robots

• Planar Seven-Bar Structures
  • Isotropic Coordinates
  • Seven-Bar Equations

• Four-Bar Linkage Design
  • Four-Bar Synthesis
  • Four-Bar Equations
  • Four-Bar Analysis
  • Function Generation
  • Body Guidance
  • Five-Point Path Synthesis
  • Nine-Point Path Synthesis
  • Four-Bar Summary

• Exercises

The following sections are included:

• Nonsingular Endpoints

• Singular Endpoints
  • Basic Setup
  • Fractional Power Series and Winding Numbers

• Singular Endgames
  • Endgame Operating Zone
  • Simple Prediction
  • Power-Series Method
  • Cauchy Integral Method
  • The Clustering or Trace Method

• Losing the Endgame

• Deflation of Isolated Singularities
  • Polynomials in One Variable
  • More than One Variable

• Exercises

The following sections are included:

• Checks
  • Endpoint Quality Measures
  • Global Checks

• Corrective Actions
  • Adaptive Re-Runs
  • Verified Path Tracking
  • Multiple Precision

• Exercises

The following sections are included:

• Affine Algebraic Sets
  • The Zariski Topology and the Complex Topology
  • Proper Maps
  • Linear Projections

• The Irreducible Decomposition for Affine Algebraic Sets
  • The Dimension of an Algebraic Set

• Further Remarks on Projective Algebraic Sets

• Quasiprojective Algebraic Sets

• Constructible Algebraic Sets

• Multiplicity

• Exercises

The following sections are included:

• Introduction to Witness Sets

• Linear Slicing
  • Extrinsic and Intrinsic Slicing

• Witness Sets
  • Witness Sets for Reduced Components
  • Witness Sets for Deflated Components
  • Witness Sets for Nonreduced Components

• Rank of a Polynomial System

• Randomization and Nonsquare Systems

• Witness Supersets
  • Examples

• Probabilistic Algorithms About Algebraic Sets
  • An Algorithm for the Dimension of an Algebraic Set
  • An Algorithm for the Dimension of an Algebraic Set at a Point
  • An Algorithm for Deciding Inclusion and Equality of Reduced Algebraic Sets

• Summary

• Exercises

The following sections are included:

• The Cascade Algorithm

• Examples

• Exercises

The following sections are included:

• Membership Tests and the Numerical Irreducible Decomposition

• Sampling a Component
  • Sampling a Reduced Component
  • Sampling a Deflated Component
  • Witness Sets in the Nonreduced Case

• Numerical Elimination Theory

• Homotopy Membership and Monodromy
  • Monodromy
  • Completeness of Monodromy

• The Trace Test
  • Traces of Functions
  • The Simplest Traces
  • Traces in the Parameterized Situation
  • Writing Down Defining Equations: An Example
  • Linear Traces

• Singular Path Tracking

• Exercises

The following sections are included:

• Intersection of Irreducible Algebraic Sets

• Equation-by-Equation Solution of Polynomial Systems
  • An Example

• Exercises

The following sections are included:

• Appendix A: Algebraic Geometry
  • Holomorphic Functions and Complex Analytic Spaces
  • Some Further Results on Holomorphic Functions
    • Manifold Points and Singular Points
    • Normal Spaces
  • Germs of Complex Analytic Sets
  • Useful Results About Algebraic and Complex Analytic Sets
    • Generic Factorization
  • Rational Mappings
  • The Rank and the Projective Rank of an Algebraic System
  • Universal Functions and Systems
    • One Variable Polynomials
    • Polynomials of Several Variables
    • A More General Case
    • Universal Systems
  • Linear Projections
    • Grassmannians
    • Linear Projections on ℙ^N
    • Further Results on System Ranks
    • Some Genericity Properties
  • Bertini's Theorem and Some Consequences
  • Some Useful Embeddings
    • Veronese Embeddings
    • The Segre Embedding
    • The Secant Variety
    • Some Genericity Results
  • The Dual Variety
  • A Monodromy Result
  • Line Bundles and Vector Bundles
    • Bihomogeneity and Multihomogeneity
    • Line Bundles and Their Sections
    • Some Remarks on Vector Bundles
    • Detecting Positive-Dimensional Components
  • Generic Behavior of Solutions of Polynomial Systems
    • Generic Behavior of Solutions
    • Analytic Parameter Spaces

• Appendix B: Software for Polynomial Continuation

• Appendix C: HomLab User's Guide
  • Preliminaries
    • “As is” Clause
    • License Fee
    • Citation and Attribution
    • Compatibility and Modifications
    • Installation
    • About Scripts
  • Overview of HomLab
  • Defining the System to Solve
    • Fully-Expanded Polynomials
    • Straight-Line Functions
    • Homogenization
    • Function Utilities and Checking
  • Linear Product Homotopies
  • Parameter Homotopies
    • Initializing Parameter Homotopies
  • Defining a Homotopy Function
    • Defining a Parameter Path
    • Homotopy Checking
  • The Workhorse: Endgamer
    • Control Settings
    • Verbose Mode
    • Path Statistics
  • Solutions at Infinity and Dehomogenization

• Bibliography

• Index