MAT 5932 - Computational Mathematics: Preliminary Course Information
This course offers an introduction to the algorithmic foundations of computer algebra. Most of the material presented will be taken from the book J. von zur Gathen and J. Gerhard: Modern Computer Algebra (Cambridge University Press), subsequently cited as [GaGe99]but buying the book is not necessary for attending the course. Acquaintance with elementary algbraic tools like modular arithmetic, finite fields and polynomial rings certainly helps in following the material discussed in this course.
The focus will be on understanding algorithms and their complexity for fundamental tasks like fast integer arithmetic, fast polynomial arithmetic and fast linear algebra. Suggestions of participants for particular topics of interest are most welcome. Homework projects may involve some programming, but the main emphasis of the course is on understanding the underlying theoretical concepts and techniques.
More information on the course is available in the preliminary syllabus, and comments are welcome.
Topics discussed in class
- 01/05/09: representation of numbers
Literature: [GaGe99, Ch. 2.1]
- 01/07/09: Big Oh notation, Landau symbols
Literature: [GaGe99, Ch. 25.7]
- 01/09/09: addition and multiplication of numbers, Euclidean Algorithm
Literature: [GaGe99, Ch. 2.2.-2.3, Ch. 3.2]
- 01/12/09: binary Euclidean algorithm, gcd computation in GF(q)[x,y]
Literature: [GaGe99, Ex. 3.25, Ch. 6.3]
- 01/14/09: Karatsuba's multiplication algorithm
Literature: [GaGe99, Ch. 8.1]
- 01/16/09: Master Theorem for Recurrences, Discrete Fourier Transform; Homework 1 is available
Literature: [GaGe99, Ch. 8.2], Master Theorem: Practice Problems and Solutions
- 01/19/09: Algebraic Properties of the Discrete Fourier Transform
Literature: [GaGe99, Ch. 8.2]
- 01/21/09: Discrete Fourier Transform and Fast Fourier Transform
Literature: [GaGe99, Ch. 8.2]
- 01/23/09: Fast Fourier Transform
Literature: [GaGe99, Ch. 8.2]
- 01/26/09: FFT-based multiplication of integers of bounded length
Literature: [GaGe99, Ch. 8.3]
- 01/28/09: continuous and discrete Fourier transform
Literature: [GaGe99, Ch. 13]
- 01/30/09: division with remainder using Newton iteration
Literature: [GaGe99, Ch. 9.1]
- 02/02/09: division with remainder using Newton iteration, formal derivatives and Taylor expansion of order 2
Literature: [GaGe99, Ch. 9.1, Ch. 9.2]
- 02/04/09: solving polynomial equations via Newton iteration
Literature: [GaGe99, Ch. 9.4]
- 02/06/09: Strassen's matrix multiplication
Literature: [GaGe99, Ch. 12.1], V. Strassen: Gaussian Elimination is not Optimal
- 02/09/09: fast modular composition of polynomials; Homework 2 is available
Literature: [GaGe99, Ch. 12.2]
- 02/11/09: introduction to linearly recurrent sequences
Literature: [GaGe99, Ch. 12.3]
- 02/13/09: linear feedback shift registers; minimal polynomial of a linearly recurrent sequence
Literature: [GaGe99, Ch. 12.3]
- 02/16/09: Wiedemann's algorithm
Literature: [GaGe99, Ch. 12.4]
- 02/18/09: factorization of polynomials, distinct-degree factorization
Literature: [GaGe99, Ch. 14.1, Ch. 14.2]
- 02/20/09: distinct-degree and equal-degree factorization in GF(q)[x]
Literature: [GaGe99, Ch. 14.2, Ch. 14.3]
- 02/23/09: a complete factoring algorithm for polynomials over a finite field; application: root finding of polynomials over GF(q)
Literature: [GaGe99, Ch. 14.4, Ch. 14.5]
- 02/25/09: fast multipoint evaluation of polynomials; Exam 1 is available
Literature: [GaGe99, Ch. 10.1]
- 02/27/09: iterated Frobenius computation by means of fast multipoint evaluation; Lagrange interpolant
Literature: [GaGe99, Ch. 14. 7, Ch. 5.2]
- 03/09/09: fast interpolation
Literature: [GaGe99, Ch. 10.2]
- 03/11/09: no class
- 03/13/09: Pollard's p-1 method and Lenstra's elliptic curve method for factoring integers
Literature: [GaGe99, Ch. 19.6, Ch. 19.7]
- 03/16/09: Dixon's random square method for factoring integers
Literature: [GaGe99, Ch. 19.5]
- 03/18/09: Landau's inequality
Literature: [GaGe99, Ch. 6.6]
- 03/20/09: Mignotte's bound; Homework 3 is available
Literature: [GaGe99, Ch. 6.6]
- 03/23/09: a factoring algorithm for polynomials with rational coefficients
Literature: [GaGe99, Ch. 15.1, Ch. 15.2]
- 03/25/09: Hensel lifting
Literature: [GaGe99, Ch. 15.4]
- 03/27/09: multifactor Hensel lifting, introduction to lattices
Literature: [GaGe99, Ch. 15.5, Ch 16.1]
- 03/30/09: Gram-Schmidt orthogonalization, bounding the length of a non-zero lattice vector
Literature: [GaGe99, Ch. 16.2]
- 04/01/09: LLL algorithm
Literature: [GaGe99, Ch. 16.2]
- 04/03/09: knapsack problems
Literature: [GaGe99, Ch. 17.1]
- 04/06/09: knapsack problems and lattice reduction
Literature: [GaGe99, Ch. 17.1]
- 04/08/09: solution of Homework 3
- 04/10/09: factoring polynomials over the integers and lattice reduction
Literature: [GaGe99, Ch. 16.4]
- 04/13/09-04/22/09: review for the final exam
For questions or comments, please feel free to contact me anytime
(see my homepage for email, phone number, etc.).
Apr 18, 2009