Tellegen’s transposition principle and its applications

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.