Computer algebra: concepts and techniques

Cover......Page 1
Half Title......Page 2
Title Page......Page 3
Copyright Page......Page 4
DEDICATION......Page 5
Table of Contents......Page 6
Preface......Page 10
Acknowledgments......Page 18
 1.1 What is Computer Algebra?......Page 20
  1.2.1 Celestial Mechanics......Page 23
  1.2.2 Chemical Stoichiometry......Page 26
  1.2.3 Geometry......Page 27
 1.3 History......Page 29
  1.3.1 Early Systems (1961-1980)......Page 30
  1.3.2 More Recent Systems (1981-present)......Page 35
 1.4 Exercises......Page 41
Chapter 2: Computer Algebra Systems......Page 48
  2.1.1 Numbers......Page 49
  2.1.2 Polynomials and Rational Functions......Page 53
  2.1.3 Variables and Functions......Page 56
  2.1.4 Calculus......Page 58
  2.1.5 Equation Solving......Page 63
  2.1.6 Data Structures and Programming......Page 65
  2.2.1 Numbers......Page 71
  2.2.2 Polynomials and Rational Functions......Page 74
  2.2.3 Variables and Functions......Page 76
  2.2.4 Calculus......Page 78
  2.2.5 Equation Solving......Page 82
  2.2.6 Lists......Page 84
  2.2.7 Programming......Page 87
 2.3 Exercises......Page 91
Chapter 3: Big Number Arithmetic......Page 100
 3.1 Representation of Numbers......Page 101
 3.2 Basic Arithmetic......Page 103
  3.2.1 Addition and Subtraction......Page 104
  3.2.2 Multiplication......Page 105
  3.2.3 Karatsuba's Algorithm......Page 106
  3.2.4 Division......Page 108
  3.3.1 Euclid's Algorithm......Page 113
  3.3.2 Analysis of Euclid's Algorithm......Page 115
  3.3.3 Extended Euclidean Algorithm......Page 117
  3.3.4 Binary GCD Algorithm......Page 120
 3.4 Rational Arithmetic......Page 122
 3.5 Exponentiation......Page 124
 3.6 Exercises......Page 128
Chapter 4: Polynomial Manipulation......Page 134
  4.1.1 Dense and Sparse Representations......Page 135
  4.1.2 Addition and Multiplication......Page 136
  4.1.3 Karatsuba's Algorithm......Page 138
  4.1.4 Sparse Polynomial Multiplication......Page 140
  4.1.5 Division......Page 142
  4.1.6 Pseudo-division......Page 143
  4.2.1 Adapting Euclid's Algorithm......Page 146
  4.2.2 Polynomial Remainder Sequences......Page 151
  4.2.3 Extended Euclidean Algorithm......Page 155
 4.3 Multivariate Polynomials......Page 156
  4.3.2 Data Structures for Polynomials......Page 157
  4.3.3 Multivariate GCD Computation......Page 161
 4.4 Exercises......Page 163
Chapter 5: Algebraic Simplification......Page 168
 5.1 Issues in Simplification......Page 169
 5.2 Normal and Canonical Forms......Page 172
  5.3.1 Algebraic Numbers and Functions......Page 176
  5.3.2 Rationalizing Denominators......Page 180
  5.3.3 Denesting Radicals......Page 183
 5.4 Transcendental Functions......Page 188
  5.4.1 Brown's Normal Form Algorithm......Page 189
  5.4.2 Structure Theorem......Page 192
  5.4.3 Expanded and Combined Forms......Page 196
  5.4.4 Euler's Formula......Page 199
  5.4.5 Trigonometric Functions......Page 202
 5.5 Exercises......Page 206
 6.1 What is Factoring?......Page 212
 6.2 Rational Roots and Linear Factors......Page 214
 6.3 Schubert-Kronecker Factorization......Page 215
  6.4.1 Monic Polynomials......Page 218
  6.4.2 Square-Free Decomposition......Page 219
  6.5.1 Factoring Polynomials mod m......Page 223
  6.5.2 Choosing a Modulus m......Page 226
  6.5.3 Roundabout Factorization Algorithm......Page 228
  6.6.1 Finding Distinct Degree Factors......Page 229
  6.6.2 Splitting Equal Degree Factors......Page 231
 6.7 Hensel Lifting......Page 235
 6.8 Exercises......Page 239
Chapter 7: Symbolic Integration......Page 244
 7.1 Antidifferentiation......Page 245
 7.2 Heuristic Methods......Page 247
  7.2.1 Derivative-Divides Method......Page 248
  7.2.2 Integration by Parts......Page 249
  7.2.3 Elementary Transformations......Page 250
 7.3 Rational Function Integration......Page 251
 7.4 Hermite's Method......Page 254
 7.5 Horowitz' Method......Page 259
 7.6 Rothstein-Trager Method......Page 262
 7.7 Liouville's Principle......Page 268
  7.8.1 Polynomial Part......Page 270
  7.8.2 Logarithmic Part......Page 274
  7.8.3 Rational Part......Page 276
  7.9.1 Polynomials of Exponentials......Page 277
  7.9.2 Rational Functions of Exponentials......Page 280
 7.10 Exercises......Page 281
Chapter 8: Gröbner Bases......Page 288
 8.1 Solution of Polynomial Equations......Page 289
  8.2.1 Linear Algebra......Page 291
  8.2.2 Greatest Common Divisors......Page 293
  8.2.3 Implicitization of Parametric Equations......Page 294
  8.2.4 Integer Programming......Page 295
  8.3.1 Ordering of Monomials......Page 296
  8.3.2 Issues in Polynomial Division......Page 297
  8.4.1 S-polynomials......Page 301
  8.4.2 An Example......Page 303
  8.4.3 Buchberger's Algorithm......Page 304
  8.4.4 Reduced Gröbner Bases......Page 305
  8.4.5 Effciency Considerations......Page 306
 8.5 Exercises......Page 308
Chapter 9: Mathematical Correctness......Page 316
 9.1 Software Bugs......Page 317
 9.2 Limitations of Computer Algebra......Page 318
  9.3.1 Cancellation of Polynomial GCDs......Page 319
  9.3.2 Integrating ∫ xk dx......Page 320
 9.4 Indeterminate Forms......Page 321
  9.5.1 Extraneous Roots......Page 322
  9.5.2 Improper Integrals......Page 323
  9.5.3 Discontinuities in Antiderivatives......Page 324
 9.6 Branch Cuts......Page 329
  9.6.1 Fractional Powers......Page 332
  9.6.2 Logarithms......Page 333
  9.6.3 Trigonometric Functions......Page 334
 9.7 Solution of Equations......Page 335
  9.7.1 Linear and Polynomial Equations......Page 336
  9.7.2 Equations with Algebraic Functions......Page 337
  9.7.3 Exponentials and Logarithms......Page 339
  9.7.4 Trigonometric Equations......Page 341
 9.8 Concluding Remarks......Page 344
 9.9 Exercises......Page 345
Bibliography......Page 350
Index......Page 360
About the Author......Page 368