TypiCal

Matrices represented by computer programs, also called black-box matrices, are a popular topic in Computer Algebra. Since the seminal paper (Wiedemann 86), algorithms to do arithmetic operations on them, as multiplication, determinant, minimal polynomial, etc., have been intensely studied and are now well understood.

The status of transposition of black box matrices is much less clear. It is a (not so well known) theorem in Algebraic Complexity that black-box matrices given by (non-uniform) arithmetic circuits can be transposed without changing the complexity of the circuit. In the more familiar Turing model, this translates to a principle, often known as "transposition principle" or "Tellegen's principle" in the Computer Algebra community, that gives a "recipe" to "transpose" an algorithm "without changing its complexity".

In this talk I will give a formal proof of the transposition principle in the touring model and sketch the implementation of a compiler that transposes algorithms written in our ad-hoc algebraic language Transalpyne. (Maybe not so) Surprisingly, we discovered some connections with Type Systems and Categoty Theory while attacking this problem: I will try to explain these connections and point out some possible research directions.