June 16, 2008
10h30: Deformation techniques for triangular arithmetic. Éric Schost, University of Western Ontario, Canada.
Triangular representations are a versatile data structure; however,
even basic arithmetic operations raise difficult questions with such
objects. I will present an algorithm for multiplication modulo a
triangular set that relies on deformation techniques and ultimately
evaluation and interpolation. It features a quasi-linear running time
(without hidden exponential factor), at least in some nice
cases. Applications include polynomial multiplication, operations on
algebraic numbers and arithmetic in Artin-Schreier extensions.
Contact Information Virginie Collette