Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr