
MAT007  Aspects of Computer Algebra  Felix Fontein  FS 13     Di  13.0014.45  Y27H12     Lecture notes
Chapter 1: Basic Arithmetic Chapter 2: A Short Introduction to Python for Mathematicians Chapter 3: Fast Arithmetic (updated: 27.03.2013) Chapter 4: Algorithms and Data Structures (updated: 27.03.2013) Chapter 5: Interpolation and the Chinese Remainder Theorem (updated: 26.04.2013) Chapter 6: Linear Algebra (updated: 21.05.2013) Chapter 7: Finite Groups (with end of Chapter 6, bibliography, list of algorithms and listings, and index) Complete lecture notes (02.08.2013)
Python modules from the lecture notes and exercises
gcd.py (functions simple_gcd , extended_gcd as a module from Section 2.2.2)vector.py (class Vector from Listing 2.1; updated 26.02.2013)rings.py (classes Integers and Rationals for Exercises 2, 3 and 7; updated 05.03.2013)polynomials.py (classes Polynomial and PolynomialRing for Exercises 4, 6, 7, 10, 15 and 18; updated 21.03.2013)polynomialstiming.py (timing tests for the Polynomial class for Exercises 10 and 15; updated 12.03.2013)bits.py (Exercise 11; updated 03.05.2013 with a ceil_log2() function)binaryexp.py (Exercise 12)benor.py (Exercise 13)exercise_14.py (Exercise 14)exercise_17.py (Exercise 17)taylor.py (Exercise 19)radix.py (Exercise 20)exercise_21.py (Exercise 21)heap.py (an implementation of a binary heap, compare Chapter 4)integerroot.py (Exercises 23 and 24)huffman.py (an implementation of a Huffman tree creator, compare Chapter 4)exercise_26.py (Exercise 26)fasteuclidean.py (Exercise 27)section_5_2.py (code from Section 5.2)fft.py (Exercises 33, 34 and 35)exercise_36.py (Exercise 36)matrix.py (matrix library for Chapter 6; updated 06.08.2013)permutation.py (Exercises 44 and 46; updated 14.05.2013)exercise_40.py (Exercise 40)exercise_41.py (Exercise 41)primes.py (algorithms from Section 6.5)exercise_45.py (Exercise 45)exercise_46.py (Exercise 46)groups.py (some abelian groups)exercise_47.py (Exercise 47)exercise_48.py (Exercise 48)exercise_49.py (Exercise 49)exercise_50.py (Exercise 50)smith.py (Smith Normal Form computation, see Section 6.11)hnf.py (HNF algorithm; Exercises 51 to 54)groupstest.py (simple example for groups.py )groupsorder.py (computes order of elements)groupsexp.py (computes exponent of group)groupsstructure.py (computes structure of subgroup generated by two elements)groupsstructure2.py (computes structure of generated subgroup)
Exercises
Exercise sheet 1 — ringstest.py (for Exercise 3) Exercise sheet 2 — moduloint.py (for Exercise 9; updated 21.03.2013) Exercise sheet 3 Exercise sheet 4 Exercise sheet 5 Exercise sheet 6 Exercise sheet 7 (updated 09.04.2013 Exercise sheet 8 (updated 26.04.2013) Exercise sheet 9 Exercise sheet 10 Exercise sheet 11
The following document contains solutions to certain exercises. It will be updated with new solutions throughout the semester. Solutions to exercises 5, 8, 16, 22, 25, 28, 29, 30, 31, 32, 37, 38, 39 and 44 (May 17, 2013)
Slides from the lectures
Lecture 1, theoretical part — Lecture 1, practical part — Python code (26.02.2013) Lecture 2, practical part Lecture 3, practical part Lecture 4, practical part Lecture 5, practical part Lecture 6, practical part Lecture 7, practical part Lecture 8, practical part Lecture 9, practical part Lecture 11, practical part Lecture 12, practical part Lecture 13, practical part
Corrections of the lecture notes
 Chapter 3, page 86, line 6: The subscript of rev in "Since rev_{m}(g)(0) = ..." should be m1 and not m. (13.03.2013)
 Chapter 3, page 90, Algorithm 3.6, line 4: both occurences of q̂ should be a p̂. (13.03.2013)
 Chapter 3, page 91, Proposition 3.4.7, second line of the first displaystyle formula: M(m,n) should be M(mn). (13.03.2013)
 Chapter 3, page 94, Algorithm 3.7, line 6: the return value should be g + p̂ · h. (13.03.2013)
 Chapter 3, page 95, Theorem 3.4.10: both asymptotic running times should be O(M(log N + log d) log log N) instead of O(M(log N + log d) log d). (13.03.2013)
 Chapter 3, page 103, at the bottom in the displaystyle formula for deg(r  r'), second line: the deg g after the equality should be deg g. (13.03.2013)
 Chapter 3, page 97, line 1 of Algorithm 3.9: "2adic" instead of "badic". (20.03.2013)
 Chapter 3, page 99, Algorithm 3.11 and page 100, proof of Theorem 3.5.6: everything having exponent e_{3} should be 3 (and not 2). (Appears twice in the algorithm and twice in the proof.) (20.03.2013)
 Chapter 3, page 112, Definition 3.7.4(a): the ℝ in the definition of the map DFT_{ω} should be an R. (20.03.2013)
 Chapter 3, page 106, Algorithm 3.12: after line 7, another line should be inserted which tests whether â_{j+1} = 0. (21.03.2013)
 Chapter 3, page 109, Algorithm 3.13: in the last case, (a, b, c) should be computed from (1 0) A and not from (0 1) A. (21.03.2013)
 Chapter 3, page 109, Algorithm 3.13: in the last lines, a does not need to be normalized anymore. Therefore, the second last line can be removed. (27.03.2013)
 Chapter 3, page 109, Theorem 3.6.8: the constant in the running time should be modified to 13. This also applies to the corresponding cases in the proof. (27.03.2013)
 Chapter 3, page 111, Lemma 3.7.3 (c): l can also be 1. 27.03.2013)
 Chapter 3, page 112, Definition 3.7.4 (a): in the definition of b_{i}, the index of a should be k and not i. (27.03.2013)
 Chapter 3, page 114, Algorithm 3.14, lines 2 and 3: b should be an a. (27.03.2013)
 Chapter 3, page 117, Algorithm 3.15, line 1: the condition should be m ≤ 2 and not n ≤ 2. (27.03.2013)
 Chapter 4, page 145, Theorem 4.2.26: in the second displayed formula, f' should be used instead of f at the beginning, and h should be denoted h_{T} in the first displayed equation and h_{T'} in the second. (27.03.2013)
 Chapter 4, page 146, the large graph: inside the red boxes sometimes p was used instead of f. (27.03.2013)
 Chapter 5, page 160, Algorithm 5.1: the loop in 3(b) should only go until l_{k}2 and not until l_{k}1. (26.04.2013)
 Chapter 5, page 160, Algorithm 5.1: in step 3(c), i must be replaced by l_{k}1. (26.04.2013)
 Chapter 5, page 171, Algorithm 5.4: the loop in 3(b) should only go until l_{k}2 and not until l_{k}1. (26.04.2013)
 Chapter 5, page 171, Algorithm 5.4: in step 3(c), i must be replaced by l_{k}1. (26.04.2013)
 Chapter 5, page 174, Algorithm 5.6: the loop in 3(b) should only go until l_{k}2 and not until l_{k}1. (26.04.2013)
 Chapter 5, page 174, Algorithm 5.6: in step 3(c), i must be replaced by l_{k}1. (26.04.2013)
 Chapter 5, page 176, Algorithm 5.9: the loop in 3(b) should only go until l_{k}2 and not until l_{k}1. (26.04.2013)
 Chapter 5, page 176, Algorithm 5.9: in step 3(c), i must be replaced by l_{k}1. (26.04.2013)
 Chapter 6, page 193, Algorithm 6.3: in step 6, D has format k_{2} × (m  k_{1}), and the topleft entry of the first displaystyle matrix in the note should be L_{1}Ũsub>1. (17.05.2013)
 Chapter 6, page 197, Algorithm 6.6: in step 2(c), U_{i•} should be swapped with U_{r+1,•} and not with A_{r+1,•}. (17.05.2013)
 Chapter 6, page 197, Algorithm 6.6: in step 2(g), mU_{r•} should be subtracted from U_{i•} and not mA_{r•}. (21.05.2013)
 Chapter 6, page 202, proof of Theorem 6.5.6: in the first line, 0.65 should be replaced with 1.1; the same is true for the next two occurences of 0.65 throughout this proof on the next page. (17.05.2013)
 Chapter 6, page 203, Algorithm 6.9, step 2: the constant 0.65 should be replaced by 1.1. (17.05.2013)
 Chapter 6, page 204, Algorithm 6.10, step 4: the CRT algorithm's number is 5.10. (17.05.2013)
 Chapter 6, page 207, Algorithm 6.11, step 5(a): it should be b' := b  Ax. (17.05.2013)
 Chapter 6, page 207, Algorithm 6.11, step 5(c): it should be b' := b'/p^{k}. (17.05.2013)
 Chapter 6, page 213, Algorithm 6.12, step 2, first line: m^{i/2}A_{∞}^{i/2} should be m^{i/2}A_{∞}^{i}. (17.05.2013)
 Chapter 6, page 216, Algorithm 6.14, step 4: i should run up to t and not d. (17.05.2013)
 Chapter 6, page 218, Algorithm 6.15, output description: the sum inside the gcd should sum over c_{i}b_{i}. (21.05.2013)
 Chapter 6, page 218, Corollary 6.9.5: the number of basic eoperations is in O((n + m)M(m)logm) (the logm factor was missing). (21.05.2013)
 Chapter 6, page 220, Algorithm 6.16, step 2: the
for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
 Chapter 6, page 220, Algorithm 6.16, step 2: the
for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
 Chapter 6, page 225, Algorithm 6.19, step 6: instead of (j_{2}, ..., j_{r1}), return (j_{2}1, ..., j_{r1}1). (21.05.2013)
Exercise classes in April and May
 April 9/10: exercise classes as usual
 April 16/17: no exercise classes (and no lecture)
 April 23/24: exercise classes as usual
 April 30: exercise class in Y27 H28
 May 1: no exercise class
 May 7/8: exercise classes in Y27 H28
 May 14/15: exercise classes as usual
 May 21/22: exercise classes as usual
 May 28/29: exercise classes as usual
(From April 16 to May 8, the computer room Y27 H52 is most of the time used for block course STA 220.) Exam The projects will be handed out and have to be returned and presented during August 2013. Alternatively, it is possible to pass a written exam instead of working on a project.Module: 26.08.2013 9:0012:00, Room:Y27H12, Typ: schriftlich http://www.vorlesungen.uzh.ch/ 