Computer Algebra

# Computer Algebra

 Start: 6 Februari 2007 Location: Amsterdam, VU: WG S205 Day and Time: Tuesday, 14:00 - 17:45

The course material will consist of the pdf files for the slides, handouts (copies of Chapters of books) and exercises sets that will be handed out and posted here as well.

In the twelfth (and thirteenth) lecture we discussed some ideas behind the factorization of integer polynomials (Berlekamp-Hensel) and the relation with Newton iteration for the location of real zeroes of a polynomial, as well as Newton poytopes.

The eleventh lecture (May 1, 2007) will be concerned with Gröbner bases of noncommutative polynomials; handout available. We will also discuss the more general Knuth-Bendix methods; recommmended reading: A.J.J. Dick, An introduction to Knuth-Bendix completion. Exercises

The tenth lecture (April 24, 2007) is concerned with group theoretic algorithms. Recommended reading: Chapter 8 of the TAPAS book. Exercises.

In the ninth lecture we covered the basic theory for (commutative) Gröbner bases.

The eighth lecture was concerned with some applications of LLL, including those mentioned in the original LLL paper. Also, a few exercises.

In the seventh lecture the LLL algorithm was treated, along the lines of sections of Henri Cohen's book on Computational Algebraic Number Theory.

The fifth and sixth lectures dealt with the Gaussian elimination algorithm, in particular PRS-like variants to compute fraction free determinants (Bareiss), and Hermite and Smith normal forms. We followed essentially Chapter 10 of Yap, which was handed out.

The fourth lecture dealt with the Chinese Remainder Algorithm, and with Polynomial Remainder Sequences. I handed out part of a Chapter on this topic by Geddes, Czapor, Labahn. Also handed out were some elementary exercises to get going with Magma.

The third and fourth sets of exercises were also handed out.

In the first part of the third lecture I discussed Euclidean domains and the Euclidean algorithm; the second part was mainly about the integer case, in the guise of continued fractions. I handed out (in week 4) a copy of my notes on continued fractions (in Dutch). For the hands-on sessions I handed out the Appendix by Geoff Bailey on the Magma language (from Bosma/Cannon: Discovering Mathematics with Magma)

The second lecture was concerned with the Fast Fourier transform. Some sections of Modern Computer Algebra were handed out. There are three exercises; two on FFT and one on Huffman coding. Here is the missing page from Johnsonbaugh's description of Huffman coding.

The first lecture concerned a general introduction, as well as some examples.

I handed out copies of Chapter 0 of Yap.

Here is the first exercise set.

Last update: 11 april 2007