Numerical Algebra 
Spring 2008

92.564

This site was updated on 17 May  2008

Final

 

 

 

 

 

HOME | SYLLABUS | STUDENTS | SCHEDULE | MATERIALS | FORUM | LINKS

 

 

 

 

Class Number 

Topics / Reading

Problems due: see the board photos for Homework Assignments. The general rule is that each problem is due in two weeks since it had been assigned.

Assigned on this date (see the board photos)

1

Discrete Fourier Transform. Discrete Fourier Transform Matrix. Multiplication of numbers as multiplication of polynomials. Recursion. Fast Fourier Transform.  Board Photos.

 

 

2

Multiplication of Integers Based on Fast Fourier Transform. Convolution. Dealing with Roots of Unity.

 

Prove the formula for the complexity of Karatsuba  multiplication(extra credit)

3

Strassen-Schunhage Algorithm. Division with Remainder. (Partial) Mimicking roots of unity in modular arithmetic. Board Photos.

Possible project: install and test Strassen-Schunhage fast multiplication algorithm:

http://www.informatik.uni-bonn.de/~schoe/tp/TPpage.html

 

4

Idea of Reduction. Extended Euclidean Algorithm. Applications of Extended Euclidean Algorithm. Multiple g.c.d. problem.   Division with remainder for polynomials. Norm. Norms for matrices. Notion of Lp-norm. Trace. Notion of Lattice. Board Photos.

 

 

5

Euclidean norm. Valuation. Additive norm. Bases of Lattices and their Gram matrices. Applications of Lattices. Low-dimensional Lattices. Lattices in Crystallography. Board  Photos.

 

 

6

Board Photos.  Proof of Blichfeldt's Lemma (I did not have time in class to cover this – let us consider this for now as extra curricular material)

 

 

7

 LLL-reduction. (note that on DSC00800.JPG ``all diagonal mu's are 0" should read ``all diagonal mu's are 1")

 

 

8

Hermite normal form of an integer matrix.

 

 

9

Hermite normal form continued: Board Photos

 

 

10

Finishing Hermite normal form. Introduction to CSparse library. Elements of C programming language. Storing sparse matrices in the triplet and column compressed forms. Board Photos

 

 

11

Sparse matrices in Matlab and in C continued.

Board Photos

 

Midterm

12

Solving some homework problems:

The problem on Fermat's primes, Karatsuba multiplication.

Strassen matrix multiplication. Divide-and-conquer algorithms on parallel and distributed systems.

Solving underdetermined sparse systems.

Linkages. Rigidity and flexibility of large linkages.

Board Photos

 

 

13

Board Photos

 

 

14

Board Photos

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 
 

 

 

 

© 2000 University of Massachusetts Lowell, Class Connections

Graphics & Design by: Thomas Pimental & Michelle Christman
In Association with: CLASS Connections