Symbolic computation, or computer algebra, manipulates formulas exactly instead of approximating them with floating-point numbers. It expands and factors polynomials, solves equations, differentiates, integrates and simplifies expressions, and works with exact rationals and arbitrary-size integers. It sits behind proof tools, compilers' optimisers and automatic differentiation.
Key concepts
- Expression trees: a formula is stored as a tree of operators and operands, and rules rewrite the tree.
- Canonical forms: a standard shape, such as an expanded polynomial, makes equality of expressions decidable.
- Exact arithmetic: rationals and big integers avoid rounding, at the cost of growth in size.
- Polynomial algorithms: gcd, factorisation and Gröbner bases solve systems of polynomial equations.
- Symbolic calculus: differentiation by rules; integration is harder and sometimes has no closed form.
Vocabulary
- Term rewriting: applying rules to replace parts of an expression until no rule applies.
- Simplification: choosing the nicest form of an expression, which depends on what you mean by nice.
- Closed form: an answer written with a finite number of standard operations and functions.
- Automatic differentiation: exact derivatives of a program by applying the chain rule, distinct from both symbolic and numerical methods.
What to study, in order
- Build an expression tree in a language of your choice and print it.
- Implement differentiation by rules and a simplifier that removes zeros and ones.
- Represent polynomials and implement addition, multiplication and gcd.
- Use a computer algebra system to solve equations and integrals, and compare with hand results.
- Study how symbolic and numerical methods are combined in practice.