Symbolic Computation (Computer Algebra)

• Introduction (2 chapters)

  Basic concepts of computer algebra, internal representation of expressions (trees, DAGs, hash consing)

• Basic (5 chapters)

  Polynomial representation and operations, interpolation, GCD, resultants and subresultants

• Intermediate (7 chapters)

  Partial fraction decomposition of rational functions, various factorizations, p-adic computation, Gröbner bases

• Advanced (16 chapters)

  Rewriting systems, simplification, symbolic differentiation / integration / limits / summation, exact linear algebra, algebraic numbers, differential algebra, CAD, computational algebraic geometry, formal power series

Introduction — Basic Concepts

1. Chapter 1 Introduction to Computer Algebra

   What is computer algebra, the history of CAS (MACSYMA to SymPy), tree representation of expressions, canonical and normal forms, thinking about complexity

2. Chapter 2 Internal Representation of Expressions — Trees, DAGs, Hash Consing

   Detailed implementation of expression trees, flattening of n-ary operations, sharing common subexpressions via DAGs, hash consing, comparison of internal representations across major CAS

Basic — Foundations of Polynomial Arithmetic

1. Chapter 3 Polynomial Representation

   Dense and sparse representations, recursive and distributed representations, choice of term order, structure of multivariate polynomials

2. Chapter 4 Basic Polynomial Operations

   Addition, subtraction, multiplication and division, Horner evaluation, long division, pseudo-division, symbolic differentiation, Newton and Bernstein bases

3. Chapter 5 Polynomial Interpolation

   Lagrange interpolation, Newton's divided differences, Neville's algorithm, FFT-based fast interpolation, Chinese Remainder interpolation, Chebyshev nodes

4. Chapter 6 Polynomial GCD Computation

   Expression swell, subresultant algorithm, modular GCD, sparse modular GCD, multivariate GCD

5. Chapter 7 Resultants and Subresultants

   Sylvester determinant, detecting common roots, Euclidean algorithm and resultants, subresultant PRS, Collins-Brown-Traub, implicit elimination

Intermediate — Rational Functions, Factorization, Ideals

1. Chapter 8 Partial Fraction Decomposition of Rational Functions

   Undetermined coefficients, Heaviside cover-up, Hermite reduction, Horowitz's algorithm, preprocessing for symbolic integration

2. Chapter 9 Factorization (over Finite Fields)

   Square-free factorization, distinct-degree factorization, Cantor-Zassenhaus, Berlekamp, Kaltofen-Shoup

3. Chapter 10 Factorization (over Integers and Rationals)

   Hensel lifting, Zassenhaus, the factor combination problem, LLL lattice reduction, van Hoeij's algorithm

4. Chapter 11 Factorization over Algebraic Number Fields

   Factorization over $\mathbb{Q}(\alpha)$, use of the norm, Trager's algorithm, Tschirnhaus transformation, factor combination via LLL

5. Chapter 12 p-adic Computation and Hensel Lifting

   p-adic numbers, p-adic absolute value, Hensel's lemma, single- and multiple-factor lifting, Dixon's p-adic linear algebra

6. Chapter 13 Gröbner Bases

   Polynomial ideals, S-polynomials, Buchberger's algorithm, sugar strategy, F4 and F5 algorithms

7. Chapter 14 Applications of Gröbner Bases

   Solving systems of equations, variable elimination, ideal operations, automatic theorem proving in geometry, robotics

Advanced — High-Level Symbolic Computation

Chapters marked 🔗 are "bridge" chapters: shorter chapters that connect two major topics and explain why the next subject follows naturally. "(Parts 1–2)" denotes a longer chapter split across two files.

1. Simplification and Normal Forms (Parts 1–2)

   Term rewriting systems, Knuth-Bendix completion, simplification of trigonometric functions, the zero-recognition problem, Richardson's theorem

2. 🔗 From Computer Algebra to Rewriting Systems (Bridge)

   Generalization from Gröbner bases to abstract rewriting systems, the reach of Knuth-Bendix, undecidability

3. Expression Rewriting Systems

   Term rewriting systems, confluence and termination, Knuth-Bendix completion, pattern matching, AC matching

4. Symbolic Differentiation

   Formalizing the chain rule, recursive transformation of expression trees, higher-order derivatives, multivariate partial derivatives, Faà di Bruno's formula, contrast with automatic differentiation

5. 🔗 From Mechanical Differentiation to Hard Integration (Bridge)

   Why differentiation is easy and integration is hard (the three layers: representation, decision, construction), from Liouville to Bronstein

6. Symbolic Integration (Parts 1–2)

   Liouville's theorem, Hermite reduction, the Risch algorithm (logarithmic and exponential parts), heuristic methods

7. Symbolic Limit Computation

   Limitations of L'Hôpital's rule, Hardy fields, the Gruntz algorithm, MrvSet and level, extension to special functions

8. Differential Algebra and Symbolic Solution of ODEs

   Differential fields, Picard-Vessiot theory, differential Galois groups, Kovacic's algorithm, Liouvillian solutions

9. Formal Power Series and Outlook (Parts 1–2)

   The algebra of formal power series, Newton iteration, composition and reversion, series solutions of differential equations, fast computation

10. Symbolic Summation and Hypergeometric Series (Parts 1–2)

    Gosper's algorithm, Zeilberger's algorithm, WZ theory, holonomic systems

11. Difference Equations and q-Hypergeometric Series

    Linear difference equations, Petkovšek's algorithm, q-differences, q-hypergeometric series, q-analogues of summation algorithms

12. Exact Linear Algebra (Parts 1–2)

    Bareiss algorithm, Hermite normal form, Smith normal form, Dixon's p-adic method, LLL lattice reduction

13. 🔗 From Exact Linear Algebra to Algebraic Numbers (Bridge) (Parts 1–2)

    Characteristic and minimal polynomials, companion matrices, multiplication matrices, resultants, recovering minimal polynomials via LLL

14. Algebraic Numbers and Field Extensions (Parts 1–2)

    Minimal polynomials, root isolation, arithmetic of algebraic numbers, algebraic extension fields, Trager factorization, Galois groups

15. Computational Algebraic Geometry

    Radical of ideals, primary decomposition, Hilbert functions, singularity detection, dimension computation

16. Quantifier Elimination and CAD

    Tarski-Seidenberg theorem, Collins' CAD, projection and lifting, partial CAD, QEPCAD and Redlog

• The Dream of Making Machines Do Algebra [Reading]

  How do Mathematica and SymPy expand, differentiate, and integrate expressions? The difference between numeric and symbolic, the idea of treating an expression as a tree, and the puzzle of "differentiation is easy, integration is hard" — told in a relaxed, informal style.