The Numerical Solution of Systems of Polynomials: Arising in Engineering And Science

by Sommese, Andrew John; Wampler, Charles W., II

• ISBN13: 9789812561848
• ISBN10: 9812561846
• Format: Hardcover
• Copyright: 2005-03-21
• Publisher: World Scientific Pub Co Inc

Table of Contents

Preface	vii
Conventions	xxi
I Background	1	(88)
1. Polynomial Systems	3	(12)
1.1 Polynomials in One Variable	3	(2)
1.2 Multivariate Polynomial Systems	5	(2)
1.3 Trigonometric Equations as Polynomials	7	(1)
1.4 Solution Sets	8	(1)
1.5 Solution by Continuation	9	(1)
1.6 Overview	10	(1)
1.7 Exercises	11	(4)
2. Homotopy Continuation	15	(12)
2.1 Continuation for Polynomials in One Variable	15	(3)
2.2 Complex Versus Real Solutions	18	(2)
2.3 Path Tracking	20	(4)
2.4 Exercises	24	(3)
3. Projective Spaces	27	(16)
3.1 Motivation: Quadratic Equations	27	(2)
3.2 Definition of Projective Space	29	(1)
3.3 The Projective Line P¹	30	(2)
3.4 The Projective Plane P²	32	(2)
3.5 Projective Algebraic Sets	34	(1)
3.6 Multiprojective Space	35	(1)
3.7 Tracking Solutions to Infinity	36	(3)
3.8 Exercises	39	(4)
4. Genericity and Probability One	43	(12)
4.1 Generic Points	44	(2)
4.2 Example: Generic Lines	46	(2)
4.3 Probabilistic Null Test	48	(2)
4.4 Algebraic Probability One	50	(1)
4.5 Numerical Certainty	51	(1)
4.6 Other Approaches to Genericity	52	(1)
4.7 Final Remarks	53	(1)
4.8 Exercises	53	(2)
5. Polynomials of One Variable	55	(12)
5.1 Algebraic Facts for One Variable Polynomials	55	(3)
5.2 Analytic Facts for One Variable Polynomials	58	(3)
5.3 Some Numerical Aspects of Polynomials of One Variable	61	(4)
5.4 Exercises	65	(2)
6. Other Methods	67	(22)
6.1 Exclusion Methods	68	(4)
6.2 Elimination Methods	72	(9)
6.2.1 Resultants	73	(3)
6.2.1.1 Hidden Variable Resultants	73	(3)
6.2.1.2 u-Resultants	76	(1)
6.2.2 Numerically Confirmed Eliminants	76	(1)
6.2.3 Dixon Determinants	77	(2)
6.2.4 Heuristic Eliminants	79	(2)
6.3 Gröbner Methods	81	(3)
6.3.1 Definitions	81	(2)
6.3.2 From Gröbner Bases to Eigenvalues	83	(1)
6.4 More Methods	84	(1)
6.5 Floating Point vs. Exact Arithmetic	84	(1)
6.6 Discussion	85	(1)
6.7 Exercises	86	(3)
II Isolated Solutions	89	(116)
7. Coefficient-Parameter Homotopy	91	(26)
7.1 Coefficient-Parameter Theory	92	(6)
7.2 Parameter Homotopy in Application	98	(1)
7.3 An Illustrative Example: Triangles	99	(2)
7.4 Nested Parameter Homotopies	101	(1)
7.5 Side Conditions	102	(1)
7.6 Homotopies that Respect Symmetry Groups	103	(1)
7.7 Case Study: Stewart-Gough Platforms	104	(7)
7.7.1 General Case	106	(2)
7.7.2 Platforms with Coincident Joints	108	(2)
7.7.3 Planar Platforms	110	(1)
7.7.4 Summary of Case Study	110	(1)
7.8 Historical Note: The Cheater's Homotopy	111	(1)
7.9 Exercises	112	(5)
8. Polynomial Structures	117	(32)
8.1 A Hierarchy of Structures	118	(2)
8.2 Notation	120	(1)
8.3 Homotopy Paths for Linearly Parameterized Families	120	(2)
8.4 Product Homotopies	122	(16)
8.4.1 Total Degree Homotopies	122	(4)
8.4.2 Multihomogeneous Homotopies	126	(4)
8.4.3 Linear Product Homotopies	130	(3)
8.4.4 Monomial Product Homotopies	133	(1)
8.4.5 Polynomial Product Homotopies	134	(4)
8.5 Polytope Structures	138	(8)
8.5.1 Newton Polytopes and Mixed Volume	138	(1)
8.5.2 Bernstein's Theorem	139	(1)
8.5.3 Computing Mixed Volumes	140	(3)
8.5.4 Polyhedral Homotopies	143	(1)
8.5.5 Example	144	(2)
8.6 A Summarizing Example	146	(1)
8.7 Exercises	147	(2)
9. Case Studies	149	(28)
9.1 Nash Equilibria	149	(3)
9.2 Chemical Equilibrium	152	(2)
9.3 Stewart-Gough Forward Kinematics	154	(2)
9.4 Six-Revolute Serial-Link Robots	156	(3)
9.5 Planar Seven-Bar Structures	159	(2)
9.5.1 Isotropic Coordinates	160	(1)
9.5.2 Seven-Bar Equations	160	(1)
9.6 Four-Bar Linkage Design	161	(9)
9.6.1 Four-Bar Synthesis	162	(1)
9.6.2 Four-Bar Equations	163	(1)
9.6.3 Four-Bar Analysis	164	(1)
9.6.4 Function Generation	164	(1)
9.6.5 Body Guidance	165	(1)
9.6.6 Five-Point Path Synthesis	166	(1)
9.6.7 Nine-Point Path Synthesis	167	(2)
9.6.8 Four-Bar Summary	169	(1)
9.7 Exercises	170	(7)
10. Endpoint Estimation	177	(20)
10.1 Nonsingular Endpoints	178	(1)
10.2 Singular Endpoints	179	(2)
10.2.1 Basic Setup	179	(1)
10.2.2 Fractional Power Series and Winding Numbers	180	(1)
10.3 Singular Endgames	181	(7)
10.3.1 Endgame Operating Zone	182	(1)
10.3.2 Simple Prediction	183	(1)
10.3.3 Power-Series Method	183	(3)
10.3.4 Cauchy Integral Method	186	(1)
10.3.5 The Clustering or Trace Method	187	(1)
10.4 Losing the Endgame	188	(2)
10.5 Deflation of Isolated Singularities	190	(4)
10.5.1 Polynomials in One Variable	191	(1)
10.5.2 More than One Variable	192	(2)
10.6 Exercises	194	(3)
11. Checking Results and Other Implementation Tips 197
11.1 Checks	197	(3)
11.1.1 Endpoint Quality Measures	197	(2)
11.1.2 Global Checks	199	(1)
11.2 Corrective Actions	200	(2)
11.2.1 Adaptive Re-Runs	201	(1)
11.2.2 Verified Path Tracking	201	(1)
11.2.3 Multiple Precision	201	(1)
11.3 Exercises	202	(3)
III Positive Dimensional Solutions	205	(92)
12. Basic Algebraic Geometry	207	(20)
12.1 Affine Algebraic Sets	209	(6)
12.1.1 The Zariski Topology and the Complex Topology	211	(1)
12.1.2 Proper Maps	212	(1)
12.1.3 Linear Projections	212	(3)
12.2 The Irreducible Decomposition for Affine Algebraic Sets	215	(2)
12.2.1 The Dimension of an Algebraic Set	216	(1)
12.3 Further Remarks on Projective Algebraic Sets	217	(2)
12.4 Quasiprojective Algebraic Sets	219	(1)
12.5 Constructible Algebraic Sets	220	(3)
12.6 Multiplicity	223	(2)
12.7 Exercises	225	(2)
13. Basic Numerical Algebraic Geometry	227	(28)
13.1 Introduction to Witness Sets	229	(2)
13.2 Linear Slicing	231	(4)
13.2.1 Extrinsic and Intrinsic Slicing	234	(1)
13.3 Witness Sets	235	(4)
13.3.1 Witness Sets for Reduced Components	236	(1)
13.3.2 Witness Sets for Deflated Components	237	(1)
13.3.3 Witness Sets for Nonreduced Components	238	(1)
13.4 Rank of a Polynomial System	239	(2)
13.5 Randomization and Nonsquare Systems	241	(3)
13.6 Witness Supersets	244	(5)
13.6.1 Examples	247	(2)
13.7 Probabilistic Algorithms About Algebraic Sets	249	(4)
13.7.1 An Algorithm for the Dimension of an Algebraic Set	250	(1)
13.7.2 An Algorithm for the Dimension of an Algebraic Set at a Point	250	(2)
13.7.3 An Algorithm for Deciding Inclusion and Equality of Reduced Algebraic Sets	252	(1)
13.8 Summary	253	(1)
13.9 Exercises	253	(2)
14. A Cascade Algorithm for Witness Supersets	255	(10)
14.1 The Cascade Algorithm	256	(5)
14.2 Examples	261	(1)
14.3 Exercises	262	(3)
15. The Numerical Irreducible Decomposition	265	(24)
15.1 Membership Tests and the Numerical Irreducible Decomposition	267	(5)
15.2 Sampling a Component	272	(2)
15.2.1 Sampling a Reduced Component	272	(1)
15.2.2 Sampling a Deflated Component	273	(1)
15.2.3 Witness Sets in the Nonreduced Case	273	(1)
15.3 Numerical Elimination Theory	274	(1)
15.4 Homotopy Membership and Monodromy	275	(4)
15.4.1 Monodromy	276	(1)
15.4.2 Completeness of Monodromy	277	(2)
15.5 The Trace Test	279	(5)
15.5.1 Traces of Functions	280	(1)
15.5.2 The Simplest Traces	280	(1)
15.5.3 Traces in the Parameterized Situation	281	(1)
15.5.4 Writing Down Defining Equations: An Example	282	(1)
15.5.5 Linear Traces	283	(1)
15.6 Singular Path Tracking	284	(4)
15.7 Exercises	288	(1)
16. The Intersection Of Algebraic Sets	289	(8)
16.1 Intersection of Irreducible Algebraic Sets	290	(2)
16.2 Equation-by-Equation Solution of Polynomial Systems	292	(2)
16.2.1 An Example	293	(1)
16.3 Exercises	294	(3)
Appendices	297	(82)
Appendix A Algebraic Geometry	299	(54)
A.1 Holomorphic Functions and Complex Analytic Spaces	300	(2)
A.2 Some Further Results on Holomorphic Functions	302	(6)
A.2.1 Manifold Points and Singular Points	306	(2)
A.2.2 Normal Spaces	308	(1)
A.3 Germs of Complex Analytic Sets	308	(2)
A.4 Useful Results About Algebraic and Complex Analytic Sets	310	(7)
A.4.1 Generic Factorization	316	(1)
A.5 Rational Mappings	317	(1)
A.6 The Rank and the Projective Rank of an Algebraic System	318	(2)
A.7 Universal Functions and Systems	320	(4)
A.7.1 One Variable Polynomials	321	(1)
A.7.2 Polynomials of Several Variables	322	(1)
A.7.3 A More General Case	322	(1)
A.7.4 Universal Systems	323	(1)
A.8 Linear Projections	324	(7)
A.8.1 Grassmannians	325	(2)
A.8.2 Linear Projections on PN	327	(2)
A.8.3 Further Results on System Ranks	329	(1)
A.8.4 Some Genericity Properties	330	(1)
A.9 Bertini's Theorem and Some Consequences	331	(3)
A.10 Some Useful Embeddings	334	(3)
A.10.1 Veronese Embeddings	334	(1)
A.10.2 The Segre Embedding	334	(1)
A.10.3 The Secant Variety	335	(1)
A.10.4 Some Genericity Results	336	(1)
A.11 The Dual Variety	337	(2)
A.12 A Monodromy Result	339	(2)
A.13 Line Bundles and Vector Bundles	341	(3)
A.13.1 Bihomogeneity and Multihomogeneity	341	(1)
A.13.2 Line Bundles and Their Sections	341	(2)
A.13.3 Some Remarks on Vector Bundles	343	(1)
A.13.4 Detecting Positive-Dimensional Components	343	(1)
A.14 Generic Behavior of Solutions of Polynomial Systems	344	(11)
A.14.1 Generic Behavior of Solutions	347	(2)
A.14.2 Analytic Parameter Spaces	349	(4)
Appendix B Software for Polynomial Continuation	353	(2)
Appendix C HomLab User's Guide	355	(24)
C.1 Preliminaries	356	(2)
C.1.1 "As is" Clause	356	(1)
C.1.2 License Fee	356	(1)
C.1.3 Citation and Attribution	356	(1)
C.1.4 Compatibility and Modifications	356	(1)
C.1.5 Installation	357	(1)
C.1.6 About Scripts	358	(1)
C.2 Overview of HOMLAB	358	(2)
C.3 Defining the System to Solve	360	(6)
C.3.1 Fully-Expanded Polynomials	360	(2)
C.3.2 Straight-Line Functions	362	(2)
C.3.3 Homogenization	364	(1)
C.3.4 Function Utilities and Checking	365	(1)
C.4 Linear Product Homotopies	366	(3)
C.5 Parameter Homotopies	369	(2)
C.5.1 Initializing Parameter Homotopies	370	(1)
C.6 Defining a Homotopy Function	371	(1)
C.6.1 Defining a Parameter Path	371	(1)
C.6.2 Homotopy Checking	372	(1)
C.7 The Workhorse: Endgamer	372	(4)
C.7.1 Control Settings	373	(2)
C.7.2 Verbose Mode	375	(1)
C.7.3 Path Statistics	375	(1)
C.8 Solutions at Infinity and Dehomogenization	376	(3)
Bibliography	379	(18)
Index	397