Theoretical Computer Science, Volume 315, Issues 2-3, Pages 307-672 (6 May 2004), Algebraic and Numerical Algorithms

Preface......Page 1
Introduction......Page 3
Solvability condition for Problem I......Page 5
The minimizer of Problem II......Page 7
Demonstration by an example......Page 9
References......Page 11
Introduction......Page 13
Bezoutians of polynomials in Bernstein form......Page 16
The displacement structure of Bernstein--Bezoutian matrices......Page 20
Numerical experiments......Page 24
Future work......Page 25
References......Page 26
Polynomial equation solving by lifting procedures for ramified fibers......Page 28
Introduction......Page 29
Geometric solutions......Page 30
Space curves......Page 31
Lifting procedures for ramified fibers......Page 33
Properties of the ideal I(,k)......Page 34
The unramifiedness of the morphism pi(,k) at T=0......Page 37
A global Newton--Hensel lifting......Page 40
Unramifiedness and flatness conditions......Page 42
Algorithms and complexity estimates......Page 44
Systems coming from a semidiscretization of certain parabolic differential equations......Page 50
A common approach to both examples......Page 52
Reimer systems......Page 55
References......Page 59
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon......Page 63
Related results......Page 64
Our results and methods we use......Page 66
Structure of the paper......Page 68
On spaces of non-positive curvature......Page 69
The configuration space......Page 70
Technical notations......Page 72
Initial approximation for the shortest path......Page 74
Bounds on eigenvalues of the Hessian of the path length......Page 75
The second variation formula for the path length......Page 76
Lower bound on eigenvalues of......Page 77
Upper bound on the norm of......Page 79
Choosing parameters a1 and a2 to satisfy (A) and (B) of Proposition 3......Page 80
Length approximation from a position approximation......Page 82
Initial gradient descent to initial approximation of Newton's method......Page 83
Complexity of the algorithm......Page 86
Complexity of gradient descent......Page 87
Complexity of Newton's method......Page 89
Separated obstacles......Page 90
Separability and random separated balls......Page 91
Approximation algorithm and its complexity......Page 92
References......Page 95
Introduction......Page 97
Reciprocal square root......Page 100
Rough bounds......Page 101
Sharper bounds assuming the abc conjecture......Page 102
The abc conjecture, Roth theorem and Liouville's estimates......Page 105
Conclusions......Page 107
References......Page 108
Introduction......Page 110
Gauß periods......Page 112
Towers of groups and fields......Page 114
Cyclotomic polynomials......Page 115
The product of normal elements......Page 116
The trace of a normal element......Page 117
An algorithm for fast multiplication......Page 118
A sum of Gauß periods......Page 119
Applying the trace map......Page 126
The complete algorithm......Page 131
Decomposable Gauß periods......Page 133
Fast multiplication for decomposable Gauß periods......Page 136
A constructive proof......Page 137
From general to decomposable Gauß periods......Page 138
A criterion for the existence of a normal Gauß period......Page 139
Experiments......Page 142
References......Page 143
Introduction......Page 144
Inversion formula......Page 146
Recursion background......Page 148
Split algorithms......Page 150
Solution of linear systems......Page 153
Generalized ZW-factorization......Page 155
References......Page 158
The aggregation and cancellation techniques as a practical tool for faster matrix multiplication......Page 160
Introduction......Page 161
A recursive procedure for two disjoint MM......Page 162
The algorithm for n2n by 2nn product......Page 164
The recursive algorithm for square matrices......Page 167
Reduction to the case of zero row and column sums......Page 170
A compact form of the aggregation-cancellation algorithm......Page 172
Asymptotics for bilinear multiplicative cost......Page 174
Implementation details for 3-procedure......Page 175
An algorithm for a single matrix product......Page 178
Recursive algorithm and its best-case performance......Page 181
Cross-over point between PK and SW algorithms......Page 182
Estimating numerical stability of the 3-Procedure......Page 184
One-level algorithms for medium-size matrices......Page 188
The comparison of performance for odd-sized matrices......Page 189
Adjustment of fast algorithms for rectangular MM......Page 190
Numerical results......Page 194
Conclusions......Page 199
References......Page 200
Introduction......Page 202
Inversion by interpolation......Page 204
Approximate method......Page 205
The revised version of Bini's algorithm......Page 209
Numerical examples......Page 212
References......Page 214
Introduction......Page 215
Stronger results via mixed metrics......Page 218
Some basic definitions and examples......Page 221
Toric actions and the momentum map......Page 224
The condition matrix......Page 226
Proof of Theorem 1......Page 228
Proof of Theorem 2......Page 229
Proof of Theorem 4......Page 230
The idea behind the proof of Theorem 5......Page 231
Proof of Theorem 5......Page 233
Proof of Theorem 3......Page 237
Proof of Theorem 6......Page 239
Acknowledgements......Page 240
Appendix A. The coarea formula......Page 241
References......Page 244
Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate......Page 246
Introduction......Page 247
Tools, definitions and main results......Page 248
Negative results: the tau case......Page 256
Negative results: the circulant case......Page 262
Acknowledgements......Page 266
References......Page 267
Introduction......Page 269
Iterative matrix inversion......Page 270
Structured matrices......Page 271
Compression of the iterates via the truncation of singular values or via substitution......Page 272
Compression using a least-squares criterion......Page 273
Numerical experiments......Page 275
Conclusion......Page 277
References......Page 278
Introduction......Page 281
Main statements......Page 283
Kronecker's encoding......Page 287
Straight-line programs......Page 289
Straight-line program encoding for varieties......Page 290
Non-Archimedean approximants......Page 291
Basic notions and notations......Page 294
Deforming a generalised Pham system......Page 296
Lifting step......Page 300
Proofs of the main Theorems 1 and 3......Page 304
Universal behaviour......Page 306
References......Page 311
Introduction......Page 314
Numerical parametrization by lines......Page 316
Parametrization of approximate curves......Page 318
Examples......Page 324
Error analysis......Page 330
References......Page 335
Numerical factorization of multivariatecomplex polynomials......Page 338
Introduction......Page 339
Algorithms......Page 341
How clusters of zeroes spread out under differentiation......Page 342
Computational experiments......Page 346
A numerical implementation......Page 347
Singularities of Stewart--Gough platforms......Page 348
General platform, fixed position......Page 349
Planar base and platform, fixed position......Page 351
Planar base and platform, parallel planes......Page 352
Monodromy compared to the enumeration method......Page 353
Acknowledgements......Page 354
References......Page 355