On the transposition of computer programs
Luca De Feo (École Polytechnique)
Thursday 10 June 2010, 15.00, b-it 1.25 (cosec meeting room)
Contents
It is a well known result in algebraic complexity theory that a linear circuit computing a matrix-vector product for a fixed matrix M can be transformed in another linear circuit computing the vector-matrix product for the same matrix M. Moreover, the transformation preserves the size and depth of the circuit.
This simple theorem, originally discovered for electric networks, has many generalizations and consequences. In computer algebra it has mainly been used as a theorem to state upper bounds on the complexity of some fundamental algebraic problems such as power projection, middle product, interpolation/evaluation, etc.
Shoup and later Bostan, Lecerf & Schost have gone further by directly applying the transformation to computer programs written in some pseudo-code. Most notably, they have been able to prove that time and space complexity are preserved by transposition.
In this talk we will revise the various proofs of the transposition theorem and discuss its relationship with automatic differentiation and some modern idioms of functional languages. Motivated by the limitations of these approaches, we will then introduce a new algorithm that permits to automatically infer all the possible transpositions of a computer program written in a general purpose language. Finally, if time permits, we will show a python implementation of our ideas.
joint work with E. Schost