Saltar al contenido ForoHackers

Symbolic computation: start here

Cálculo simbólico
#643 · Ophuscado · · Denunciar

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

Inicia sesión o únete para responder.