arXiv:math/0201315 Abstract

arXiv:math/0201315 [math.RA]Abstract References Reviews Resources

Berkowitz's Algorithm and Clow Sequences

Published 2002-01-31Version 1

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.

Comments: Submitted to ELA (Electronic Journal of Linear Algebra)

Categories: math.RA

Subjects: 65F30, 11Y16

Keywords: berkowitzs algorithm, combinatorial interpretation, clow sequences turn, main contribution, parallel algorithm

Related articles: Most relevant | Search more

arXiv:1806.04211 [math.RA] (Published 2018-06-08)

A parallel algorithm for Gaussian elimination over finite fields

Stephen Linton, Gabriele Nebe, Alice Niemeyer, Richard Parker, Jon Thackray

arXiv:0809.1773 [math.RA] (Published 2008-09-10, updated 2008-12-09)

Compatible associative products and trees

Vladimir Dotsenko

arXiv:math/0606775 [math.RA] (Published 2006-06-30)