Introduction to Computer Algebra

Overview

• Introduction and course overview.
• Cost models.
• Fundamental algorithms for integers and polynomials:
  • Addition, multiplication, division, fast multiplication;
  • Evaluation and interpolation, Chinese remaindering;
  • Euclidean algorithm, fraction recovery.
  • Further topics (depending on schedule): power series manipulation, the transposition principle.
• Linearly recurrent sequences, sparse polynomials and matrices:
  • Minimal polynomials;
  • Sparse linear algebra and structured matrices.
  • Further topic (depending on schedule): sparse polynomial interpolation.
• Linear algebra:
  • Matrix multiplication;
  • Matrix determinant and linear system solution, Dixon's algorithm;
  • The characteristic polynomial, Keller-Gehrig's algorithm.
  • Further topics (depending on schedule): Diophantine linear system solution, automatic differentiation.
• Lattice basis reduction:
  • The LLL algorithm;
  • Symbolic-numeric approaches;
  • Examples of applications.
  • Further topics (depending on schedule): polynomial factorization.

Useful references:

- Modern Computer Algebra. Joachim von zur Gathen and Jürgen Gerhard. Cambridge University Press, third edition 2013.
- Algorithmes Efficaces en Calcul Formel (in French), A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É Schost. Notes du cours 2-22 du MPRI, 2014.
- Algorithms for Computer Algebra. Keith O. Geddes, Stephen R. Czapor, and George Labahn. Kluwer Academic Publishers, 1992.
- Algebraic Complexity Theory. Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Grundlehren Math. Wiss. Berlin; 315. Springer-Verlag, 1997.
- The LLL Algorithm: Survey and Applications. Phong Q. Nguyen, and Brigitte Vallée, Eds. Springer Science & Business Media, 2009.