COMP443 2010 Arithmetic and Algebraic Algorithms

Lecturer: Dr S. McCallum

In this unit we shall study efficient algorithms for computations with
(potentially big) integers and polynomials.
Topics include data structures for the representation of
(big) integers and polynomials, fast multiplication, Chinese
remainder algorithms, and algorithms for polynomial factorization.

Such algorithms have numerous applications. One interesting application
area we shall glimpse in this unit concerns the development of decision methods
for elementary real algebra and geometry.
For this purpose we shall also need to consider algorithms
for polynomial real root isolation and algorithms for handling real
algebraic numbers.

While primarily a theoretical unit, students will have some
opportunity to work with a powerful computer arithmetic/algebra package
called SACLIB.

This unit will be offered as a full semester unit. It is envisaged that
two hours of lectures will be offered each week for the whole semester.

Timetabling for the lectures will be arranged to suit
the (expected small number of) participants. Lectures will commence
in week 1 (beginning 2 August) and continue right through
the semester (excluding the recess).

Assessment will probably be based upon three written assignments
(each worth at least 10%), one project (worth at least 20%) and an exam
(worth up to 50%). The exact structure of the assessment 
(including the exact weightings of the assessment components) could be
worked out by discussion in the first class meeting.

While there will be no textbook for this unit, the following
reference books will be useful:

Lipson, J. D. (1981). Elements of Algebra and Algebraic Computing.
Benjamin/Cummings.

Geddes, K. et al. (1992). Algorithms for Computer Algebra.
Kluwer, Norwell.

Knuth, D. E. (1997). The Art of Computer Programming,
Volume 2, Seminumerical algorithms - Third Edition. Addison-Wesley,
Reading.

von zur Gathen, J. and Gerhad, J. (2003). Modern Computer Algebra - Second Edition.
Cambridge University Press.

Winkler, F. (1996). Polynomial Algorithms in Computer Algebra.
Springer-Verlag, Wien.