Computational Mathematics
Instructor: Curtis Bright
This class provides a broad introduction to discrete computational mathematics with a focus on symbolic computation.
That is, we cover how to effectively do mathematics on computers. This involves topics such as:
- Using a computer algebra system like Maple or Sage
- Algorithms for performing arithmetic on polynomials and arbitrarily large integers
- Solving linear Diophantine equations and the extended Euclidean algorithm
- Efficient modular arithmetic and the Chinese remainder algorithm
- Primality testing and factorization
- Polynomial evaluation and interpolation
- Karatsuba multiplication, fast multiplication, and the discrete Fourier transform
- Fast division and Newton iteration
- Satisfiability solving and the Davis–Putnam–Logemann–Loveland procedure
A number of applications of these topics will be discussed, such as to coding theory, cryptography, and computer-assisted proofs.
Lecture Notes
- Sage Introduction (pdf, ipynb)
- Basic Algebraic Operations (pdf, ipynb)
- The Euclidean Algorithm (pdf, ipynb)
- Modular Arithmetic (pdf, ipynb)
- Cryptography and Coding Theory (pdf, ipynb)
- Finite Fields and Reed–Solomon Codes (pdf, ipynb)
- Satisfiability Solving (pdf, ipynb)
- Polynomial Evaluation and Interpolation (pdf, ipynb)
- Fast Multiplication and the Discrete Fourier Transform (pdf, ipynb)
- Primality Testing and Factoring (pdf, ipynb)
- A Modular Euclidean Algorithm (pdf, ipynb)
- Factoring Polynomials (pdf, ipynb)
The lectures roughly cover the first eight chapters of Modern Computer Algebra as well as chapters 14 and 18 to 20. A few topics do not appear in MCA (such as satisfiability solving).
References
There is no required textbook for the course, but the following books are excellent references:
Software
Programming in this class will be done in either Maple or Sage.
Maple is a commercial computer algebra system developed by Maplesoft.
Sage is a computer algebra system that is freely available and runs on Linux, Windows, and MacOS.
Previous Versions
The course was also taught in 2022 and 2021.