Skip to the content ForoHackers
Log inJoin

Symbolic computation: start here

Symbolic computation
#3149 · · Quote · Report

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

  1. Build an expression tree in a language of your choice and print it.
  2. Implement differentiation by rules and a simplifier that removes zeros and ones.
  3. Represent polynomials and implement addition, multiplication and gcd.
  4. Use a computer algebra system to solve equations and integrals, and compare with hand results.
  5. Study how symbolic and numerical methods are combined in practice.

Related tags

#linear-algebra #numerical-analysis #lisp #python #logic

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply