Preface |
|
xi | |
Acknowledgments |
|
xix | |
|
|
1 | (28) |
|
1.1 What is Computer Algebra? |
|
|
1 | (3) |
|
|
4 | (6) |
|
1.2.1 Celestial Mechanics |
|
|
4 | (3) |
|
1.2.2 Chemical Stoichiometry |
|
|
7 | (1) |
|
|
8 | (2) |
|
|
10 | (12) |
|
1.3.1 Early Systems (1961--1980) |
|
|
11 | (5) |
|
1.3.2 More Recent Systems (1981--present) |
|
|
16 | (6) |
|
|
22 | (7) |
|
2 Computer Algebra Systems |
|
|
29 | (52) |
|
|
30 | (22) |
|
|
30 | (4) |
|
2.1.2 Polynomials and Rational Functions |
|
|
34 | (3) |
|
2.1.3 Variables and Functions |
|
|
37 | (2) |
|
|
39 | (5) |
|
|
44 | (2) |
|
2.1.6 Data Structures and Programming |
|
|
46 | (6) |
|
|
52 | (20) |
|
|
52 | (3) |
|
2.2.2 Polynomials and Rational Functions |
|
|
55 | (2) |
|
2.2.3 Variables and Functions |
|
|
57 | (2) |
|
|
59 | (4) |
|
|
63 | (2) |
|
|
65 | (3) |
|
|
68 | (4) |
|
|
72 | (9) |
|
|
81 | (34) |
|
3.1 Representation of Numbers |
|
|
82 | (2) |
|
|
84 | (10) |
|
3.2.1 Addition and Subtraction |
|
|
85 | (1) |
|
|
86 | (1) |
|
3.2.3 Karatsuba's Algorithm |
|
|
87 | (2) |
|
|
89 | (5) |
|
3.3 Greatest Common Divisor |
|
|
94 | (9) |
|
|
94 | (2) |
|
3.3.2 Analysis of Euclid's Algorithm |
|
|
96 | (2) |
|
3.3.3 Extended Euclidean Algorithm |
|
|
98 | (3) |
|
3.3.4 Binary GCD Algorithm |
|
|
101 | (2) |
|
|
103 | (2) |
|
|
105 | (4) |
|
|
109 | (6) |
|
4 Polynomial Manipulation |
|
|
115 | (34) |
|
4.1 Arithmetic on Polynomials |
|
|
116 | (11) |
|
4.1.1 Dense and Sparse Representations |
|
|
116 | (1) |
|
4.1.2 Addition and Multiplication |
|
|
117 | (2) |
|
4.1.3 Karatsuba's Algorithm |
|
|
119 | (2) |
|
4.1.4 Sparse Polynomial Multiplication |
|
|
121 | (2) |
|
|
123 | (1) |
|
|
124 | (3) |
|
|
127 | (10) |
|
4.2.1 Adapting Euclid's Algorithm |
|
|
127 | (5) |
|
4.2.2 Polynomial Remainder Sequences |
|
|
132 | (4) |
|
4.2.3 Extended Euclidean Algorithm |
|
|
136 | (1) |
|
4.3 Multivariate Polynomials |
|
|
137 | (7) |
|
4.3.1 Expanded and Recursive Forms |
|
|
138 | (1) |
|
4.3.2 Data Structures for Polynomials |
|
|
138 | (4) |
|
4.3.3 Multivariate GCD Computation |
|
|
142 | (2) |
|
|
144 | (5) |
|
5 Algebraic Simplification |
|
|
149 | (44) |
|
5.1 Issues in Simplification |
|
|
150 | (3) |
|
5.2 Normal and Canonical Forms |
|
|
153 | (4) |
|
5.3 Simplification of Radicals |
|
|
157 | (12) |
|
5.3.1 Algebraic Numbers and Functions |
|
|
157 | (4) |
|
5.3.2 Rationalizing Denominators |
|
|
161 | (3) |
|
|
164 | (5) |
|
5.4 Transcendental Functions |
|
|
169 | (18) |
|
5.4.1 Brown's Normal Form Algorithm |
|
|
170 | (3) |
|
|
173 | (4) |
|
5.4.3 Expanded and Combined Forms |
|
|
177 | (3) |
|
|
180 | (3) |
|
5.4.5 Trigonometric Functions |
|
|
183 | (4) |
|
|
187 | (6) |
|
|
193 | (32) |
|
|
193 | (2) |
|
6.2 Rational Roots and Linear Factors |
|
|
195 | (1) |
|
6.3 Schubert-Kronecker Factorization |
|
|
196 | (3) |
|
6.4 Simplifying Polynomial Factorization |
|
|
199 | (5) |
|
|
199 | (1) |
|
6.4.2 Square-Free Decomposition |
|
|
200 | (4) |
|
6.5 Roundabout Factorization |
|
|
204 | (6) |
|
6.5.1 Factoring Polynomials mod m |
|
|
204 | (3) |
|
6.5.2 Choosing a Modulus m |
|
|
207 | (2) |
|
6.5.3 Roundabout Factorization Algorithm |
|
|
209 | (1) |
|
6.6 Distinct Degree Factorization |
|
|
210 | (6) |
|
6.6.1 Finding Distinct Degree Factors |
|
|
210 | (2) |
|
6.6.2 Splitting Equal Degree Factors |
|
|
212 | (4) |
|
|
216 | (4) |
|
|
220 | (5) |
|
|
225 | (44) |
|
|
226 | (2) |
|
|
228 | (4) |
|
7.2.1 Derivative-Divides Method |
|
|
229 | (1) |
|
7.2.2 Integration by Parts |
|
|
230 | (1) |
|
7.2.3 Elementary Transformations |
|
|
231 | (1) |
|
7.3 Rational Function Integration |
|
|
232 | (3) |
|
|
235 | (5) |
|
|
240 | (3) |
|
7.6 Rothstein-Trager Method |
|
|
243 | (6) |
|
7.7 Liouville's Principle |
|
|
249 | (2) |
|
7.8 Risch Algorithm: Logarithmic Case |
|
|
251 | (7) |
|
|
251 | (4) |
|
|
255 | (2) |
|
|
257 | (1) |
|
7.9 Risch Algorithm: Exponential Case |
|
|
258 | (4) |
|
7.9.1 Polynomials of Exponentials |
|
|
258 | (3) |
|
7.9.2 Rational Functions of Exponentials |
|
|
261 | (1) |
|
|
262 | (7) |
|
|
269 | (28) |
|
8.1 Solution of Polynomial Equations |
|
|
270 | (2) |
|
8.2 Mathematical Applications |
|
|
272 | (5) |
|
|
272 | (2) |
|
8.2.2 Greatest Common Divisors |
|
|
274 | (1) |
|
8.2.3 Implicitization of Parametric Equations |
|
|
275 | (1) |
|
8.2.4 Integer Programming |
|
|
276 | (1) |
|
8.3 General Polynomial Division |
|
|
277 | (5) |
|
8.3.1 Ordering of Monomials |
|
|
277 | (1) |
|
8.3.2 Issues in Polynomial Division |
|
|
278 | (4) |
|
8.4 Construction of Grobner Bases |
|
|
282 | (7) |
|
|
282 | (2) |
|
|
284 | (1) |
|
8.4.3 Buchberger's Algorithm |
|
|
285 | (1) |
|
8.4.4 Reduced Grobner Bases |
|
|
286 | (1) |
|
8.4.5 Efficiency Considerations |
|
|
287 | (2) |
|
|
289 | (8) |
|
9 Mathematical Correctness |
|
|
297 | (34) |
|
|
298 | (1) |
|
9.2 Limitations of Computer Algebra |
|
|
299 | (1) |
|
|
300 | (2) |
|
9.3.1 Cancellation of Polynomial GCDs |
|
|
300 | (1) |
|
9.3.2 Integrating ∫ xk dx |
|
|
301 | (1) |
|
|
302 | (1) |
|
|
303 | (7) |
|
|
303 | (1) |
|
|
304 | (1) |
|
9.5.3 Discontinuities in Antiderivatives |
|
|
305 | (5) |
|
|
310 | (6) |
|
|
313 | (1) |
|
|
314 | (1) |
|
9.6.3 Trigonometric Functions |
|
|
315 | (1) |
|
9.7 Solution of Equations |
|
|
316 | (9) |
|
9.7.1 Linear and Polynomial Equations |
|
|
317 | (1) |
|
9.7.2 Equations with Algebraic Functions |
|
|
318 | (2) |
|
9.7.3 Exponentials and Logarithms |
|
|
320 | (2) |
|
9.7.4 Trigonometric Equations |
|
|
322 | (3) |
|
|
325 | (1) |
|
|
326 | (5) |
Bibliography |
|
331 | (10) |
Index |
|
341 | (8) |
About the Author |
|
349 | |