|
people
|
 publications
|
research
|
education
|
 industry
|
 conferences
|
media
|
 projects
internal

 search: sitemap

# Computer Algebra II: Fast arithmetic and Factorization (Lecture)

Summer 2010

## Description

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.

## Course Details

• Lecturer: Manuel Kauers
• If you are regular JKU student, please register to this course via KUSSS
• Exam/credits mode: will be discussed in the first meeting
• Time/Place:
• 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, Cambridge 1999; Algorithms for Computer Algebra by Geddes, Czapor, and Labahn, Kluwer 1992.

## Material

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