Computer algebra

Introduction......Page 13
The `group theory\' side......Page 15
Expansion and Simplification......Page 16
A Digression on ``Functions\'\'......Page 18
Expansion......Page 19
Simplification......Page 20
An example of simplification......Page 22
Algebraic Definitions......Page 23
Some Complexity Theory......Page 26
The simplify command......Page 28
What are polynomials?......Page 31
Polynomials in one variable......Page 33
A factored representation......Page 37
Polynomials in several variables......Page 38
Other representations......Page 39
The Newton Representation......Page 42
Rational Functions......Page 43
Candidness of rational functions......Page 44
Greatest Common Divisors......Page 45
Polynomials in one variable......Page 46
Subresultant sequences......Page 50
The Extended Euclidean Algorithm......Page 52
Partial Fractions......Page 53
Polynomials in several variables......Page 54
Square-free decomposition......Page 56
Non-commutative polynomials......Page 57
Quadratic Equations......Page 59
Cubic Equations......Page 60
Higher Degree Equations......Page 62
Reducible defining polynomials......Page 63
Solutions in Real Radicals......Page 64
Equations of curves......Page 65
How many real roots?......Page 66
Linear Equations in Several Variables......Page 68
Representations of Matrices......Page 69
Matrix Inverses: not a good idea!......Page 71
Bareiss–Dodgson Warning......Page 74
Over/under-determined Systems......Page 75
Nonlinear Multivariate Equations: Distributed......Page 76
Gröbner Bases......Page 78
How many Solutions?......Page 81
Orderings......Page 82
Complexity of Gröbner Bases......Page 84
A Matrix Formulation......Page 87
Example......Page 89
The Gianni–Kalkbrener Theorem......Page 90
Gianni–Kalkbrener Theorem......Page 91
The Faugère–Gianni–Lazard–Mora Algorithm......Page 93
The Shape Lemma......Page 96
The Hilbert function......Page 98
Non-commutative Ideals......Page 99
Triangular Sets and Regular Chains......Page 100
Zero Dimension......Page 101
Positive Dimension......Page 102
Conclusion......Page 105
Equations and Inequalities......Page 106
Applications......Page 107
Quantifier Elimination......Page 108
Algebraic Decomposition......Page 109
Cylindrical Algebraic Decomposition......Page 112
Computing Algebraic Decompositions......Page 115
Complexity......Page 116
Further Observations......Page 117
Conclusions......Page 118
Modular Methods......Page 119
Matrices with integer coefficients......Page 120
Conclusion......Page 121
Gcd in one variable......Page 122
Bounds on divisors......Page 123
The modular – integer relationship......Page 124
Computing the g.c.d.: one large prime......Page 125
Computing the g.c.d.: several small primes......Page 127
An alternative correctness check......Page 129
Conclusion......Page 130
Degree Growth in Coefficients......Page 132
The evaluation–interpolation relationship......Page 133
G.c.d. in Zp[x,y]......Page 135
G.c.d. in Z[x,y]......Page 137
Polynomials in several variables......Page 138
A worked example......Page 139
Converting this to an algorithm......Page 141
Worked example continued......Page 142
Resultants and Discriminants......Page 146
Linear Systems......Page 147
General Considerations......Page 149
The Hilbert Function and reduction......Page 150
The Modular Algorithm......Page 152
Conclusions......Page 154
Introduction to the factorization problem......Page 155
The Cantor–Zassenhaus method......Page 157
From Zp to Z?......Page 160
Linear Hensel Lifting......Page 161
Quadratic Hensel Lifting......Page 163
The recombination problem......Page 165
Univariate Factoring Solved......Page 167
Conclusions......Page 169
Algebraic Numbers and functions......Page 171
Representations of Algebraic Numbers......Page 173
The D5 approach to algebraic numbers......Page 174
Introduction......Page 175
Integration of Proper Rational Expressions......Page 177
Hermite\'s Algorithm......Page 178
The Ostrogradski–Horowitz Algorithm......Page 179
The Trager–Rothstein Algorithm......Page 180
Theory: Liouville\'s Theorem......Page 183
Liouville\'s Principle......Page 185
Finding L......Page 186
Overview of Integration......Page 187
Integration of Logarithmic Expressions......Page 189
The Rational Expression Part......Page 190
Integration of Exponential Expressions......Page 191
The Polynomial Part......Page 193
The Rational Expression Part......Page 194
Integration of Algebraic Expressions......Page 197
The Risch Differential Equation Problem......Page 198
The Parallel Approach......Page 200
Indefinite summation......Page 202
BookmarkTitle:......Page 203
Functions and Formulae......Page 205
Some Unpleasant Facts......Page 207
Possible Solutions......Page 208
Removable Branch Cuts......Page 211
Constants are often troubling......Page 212
Integrating `real\' Functions......Page 213
Other decision questions......Page 216
The resultant......Page 219
Matrices......Page 222
Coefficients of a polynomial......Page 223
Roots of a polynomial......Page 225
Root separation......Page 226
Chinese Remainder Theorem......Page 229
Chinese Remainder Theorem for Polynomials......Page 230
Vandermonde Systems......Page 232
The Budan–Fourier Theorem......Page 235
Equality of factored polynomials......Page 236
Karatsuba\'s method......Page 238
Karatsuba\'s method and sparse polynomials......Page 239
Faster still......Page 240
Strassen\'s method......Page 241
Matrix Inversion......Page 243
History......Page 245
Overview......Page 246
Data structures......Page 248
Conclusion......Page 251
History......Page 252
History......Page 253
Index of Notation......Page 255