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