Algorithms in Algebraic Geometry (eBook)

FOREWORD 6
PREFACE 7
Table of Contents 
10 
APPLICATION OF A NUMERICAL VERSION OF TERRACINI'S LEMMA FOR SECANTS AND JOINS 
11 
1. Introduction 11
2. Background 13
2.1. Homotopy continuation 13
2.2. Singular value decomposition 14
2.3. Terracini's lemma 15
2.4. Bertini software package 16
3. Five illustrative examples 16
3.1. Secant variety of the Veronese surface in P5 
17 
3.2. Two more examples 19
4. Further computational experiments 20
4.1. Computations on systems which are close together 20
4.2. Determining equations from a generic point 21
5. Conclusions 22
REFERENCES 23
ON THE SHARPNESS OF FEWNOMIAL BOUNDS AND THE NUMBER OF COMPONENTS OF FEWNOMIAL HYPERSURFACES 
25 
1. Introduction 25
1.1. A lower bound for fewnomial systems 26
1.2. An upper bound for fewnomial hypersurfaces 27
REFERENCES 29
INTERSECTIONS OF SCHUBERT VARIETIES AND OTHER PERMUTATION ARRAY SCHEMES 
31 
1. Introduction 31
2. The flag manifold and Schubert varieties 33
3. Permutation arrays 36
4. Permutation array varieties/schemes and their pathologies 41
5. Intersecting Schubert varieties 46
5.1. Permutation array algorithm 47
5.2. Algorithmic complexity 51
6. The key example: triple intersections 53
7. Monodromy and Galois groups 58
8. Acknowledgments 62
REFERENCES 63
EFFICIENT INVERSION OF RATIONAL MAPS OVER FINITE FIELDS 
65 
1. Introduction 65
1.1. Outline of our approach 66
2. Notions and notations 67
2.1. Data structures 68
2.2. The algorithmic model 68
2.3. Cost of the basic operations 69
3. Geometric solutions 69
3.1. Algorithmic aspects of the computation of a geometric solution 
71 
4. Preparation of the input data 72
4.1. The graph of the mapping F 
72 
4.2. Random choices 73
5. The algorithm 76
5.1. The computation of the polynomial ms 78
5.2. A geometric solution of C 81
5.3. Computation of the points of F-1(y((O)) nFqn 
83 
6. Conclusions 85
REFERENCES 86
HIGHER-ORDER DEFLATION FOR POLYNOMIAL SYSTEMS WITH ISOLATED SINGULAR SOLUTIONS 
89 
1. Introduction 89
2. Statement of the main theorem & algorithms
3. Multiplicity structure 93
3.1. Standard bases 94
3.2. Dual space of differential functionals 94
3.3. Dual bases versus standard bases 95
4. Computing the multiplicity structure 96
4.1. The Dayton-Zeng algorithm 96
4.2. The Stetter-Thallinger algorithm 97
5. Proofs and algorithmic details 99
5.1. First-order deflation 99
5.2. Higher-order deflation with fixed multipliers 100
5.3. Indeterminate multipliers 103
6. Computational experiments 103
6.1. A first example 103
6.2. A larger example 104
7. Conclusion 105
REFERENCES 105
POLARS OF REAL SINGULAR PLANE CURVES 109
1. Introduction 109
2. Polar varieties 110
2.1. Classical polar varieties 110
2.2. Reciprocal polar varieties 113
3. Polar varieties of real singular curves 116
3.1. Classical polar varieties of real singular affine curves 117
3.2. Reciprocal polar varieties of affine real singular curves 119
REFERENCES 125
SEMIDEFINITE REPRESENTATION OF THE K-ELLIPSE 127
1. Introduction 127
2. Derivation of the matrix representation 130
3. More pictures and some semidefinite aspects 132
4. Generalizations 137
4.1. Weighted k-ellipse 137
4.2. k-Ellipsoids 138
5. Open questions and further research 139
REFERENCES 142
SOLVING POLYNOMIAL SYSTEMS EQUATION BY EQUATION 
143 
1. Introduction 143
2. A numerical irreducible decomposition 144
2.1. An illustrative example 144
2.2. Witness sets 145
2.3. Geometric resolutions and triangular representations 146
2.4. Embeddings and cascades of homotopies 148
3. Application of diagonal homotopies 149
3.1. Symbols used in the algorithms 149
3.2. Solving subsystem by subsystem 151
3.3. Solving equation by equation 154
3.4. Seeking only nonsingular solutions 156
4. Computational experiments 157
4.1. An illustrative example 157
4.2. Adjacent minors of a general 2-by-9 matrix 157
4.3. A general 6-by-6 eigenvalue problem 159
5. Conclusions 160
REFERENCES 161
LIST OF WORKSHOP PARTICIPANTS 163
IMA VOLUMES 171