Berkowitz's Algorithm and Clow Sequences

Details Berkowitz's Algorithm and Clow Sequences Berkowitz's Algorithm and Clow Sequences

2002-01-31

arxiv.org/abs/math/0201315v1

Mathematics

Rings and Algebras

Submitted to ELA (Electronic Journal of Linear Algebra)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Berkowitz's Algorithm and Clow Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Berkowitz's Algorithm and Clow Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Berkowitz's Algorithm and Clow Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163850