Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.
Résumé du séminaire du Mardi 7 Février 2006
Tellegen's transposition principle and its applications
par Alin Bostan (INRIA Rocquencourt, Projet Algorithmes)
Tellegen's transposition principle is a set of program transformation techniques, associating to any linear algorithm a "dual algorithm" of (essentially) equal complexity. It originates from electronic circuit design and it was introduced in computer algebra quite recently. In the first part of this talk, we present different formulations of Tellegen's principle in terms of computation graphs, matrices and straight-line programs. Then, we describe some of its recent applications to the design of fast algorithms for basic problems in computer algebra, such as the multipoint evaluation and interpolation of univariate polynomials.