Computer Algebra II: Fast arithmetic and Factorization (Lecture)
How many field operations are needed to multiply two univariate polynomials
of degree n over some field K?
How about the number of field operations needed for factoring a polynomial
or computing a greatest common divisor of two polynomials?
Efficient algorithms for these and other problems were presented in
Computer Algebra I, but are they as efficient as can be?
It turns out that they are not. In Computer Algebra II we will present
faster algorithms, including some of the fastest algorithms known today
for solving algebraic problems.
- Lecturer: Manuel Kauers
- If you are regular JKU student, please register to this course via
- Exam/credits mode: will be discussed in the first meeting
- Wednesdays, 9.00--10.30, Seminar room Hagenberg
- First meeting: Wednesday, March 3
- No meeting on March 10
- Prerequisits: Students are expected to be familiar with the material of
Computer Algebra I
- Literature: Modern Computer Algebra by von zur Gathen and Gerhard,
Algorithms for Computer Algebra by Geddes, Czapor, and Labahn, Kluwer 1992.
Computing in homomorphic images (2010-04-21)
- Animation for solving a linear system over Q: sysQ.mp4
- Animation for solving a linear system over Zp: sysZp.mp4
- Animation for homomorphic preimages over Z: modZ.mp4
- Animation for homomorphic preimages over Q (rational reconstruction): modQ.mp4
- Demo for ratioal reconstruction: rationalReconstruction.nb
- Computation time depending on bitsize / Chinese remaindering illustration: main.pdf
- Demo for chinese remaindering and newton interpolation: chineseRemainder.nb
- Example linear system over Q(x) with 1D solution space: sys.m
- Implementation of a linear system solver using homomorphic images: LinearSystemSolver.m