Berkowitz's algorithm and clow sequences
- Additional Document Info
- View All
We present a combinatorial interpretation of Berkowitz's algorithm.
Berkowitz's algorithm is the fastest known parallel algorithm for computing the
characteristic polynomial of a matrix. Our combinatorial interpretation is
based on ``loop covers'' introduced by Valiant, and ``clow sequences.'' Clow
sequences turn out to capture very succinctly the computations performed by
Berkowitz's algorithm, which otherwise is quite difficult to analyze. The main
contribution of this paper is a proof of correctness of Berkowitz's algorithm
in terms of clow sequences.
has subject area