ELA, Volume 9, pp. 42-54, April 2002, abstract.  

Berkowitz's algorithm and clow sequences

Michael Soltys

A combinatorial interpretation of Berkowitz's algorithm 
is presented. Berkowitz's algorithm is the fastest known 
parallel algorithm for computing the characteristic 
polynomial of a matrix. The combinatorial interpretation 
is based on ``loop covers'' introduced by Valiant, and 
``clow sequences'', defined by Mahajan and Vinay. 
Clow sequences turn out to capture very succinctly the 
computations performed by Berkowitz's algorithm, which 
otherwise are quite difficult to analyze. The main 
contribution of this paper is a proof of correctness of 
Berkowitz's algorithm in terms of clow sequences.