Berkowitz's Algorithm and Clow Sequences

2002/01/31 by Michael Soltys, Soltys, Michael · 1 citation
Computer Science · Engineering · Mathematics · #11Y16 #65F30 #Computability, Logic, AI Algorithms #FOS: Mathematics #Rings and Algebras (math.RA) #graph theory and CDMA systems #math.RA #msc:11Y16 #msc:65F30 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0201315

Submitted to ELA (Electronic Journal of Linear Algebra)

arxiv created 2002/01/31 · openalex publication_date 2002/01/31 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• On the gradient of the coefficient of the characteristic polynomial

Related

• Deterministic computation of the characteristic polynomial in the time\n of matrix multiplication
• Computing the Characteristic Polynomial of Generic Toeplitz-like and\n Hankel-like Matrices
• The Berlekamp-Massey Algorithm via Minimal Polynomials
• On a fast and nearly division-free algorithm for the characteristic polynomial
• Efficient Computation of the Characteristic Polynomial