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.