Berkowitz's algorithm and clow sequences

DOI10.13001/1081-3810.1072MaRDI QIDQ2783464zbMATH OpenOpenAlexFDO

Authors Michael Soltys

Publication date 23 April 2002

Published in ELA. The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0201315, https://eudml.org/doc/122179, http://www.emis.de/journals/ELA/ela-articles/9.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Berkowitz's algorithmBoolean circuitscharacteristic polynomialclosed walk sequencesclow sequencecomputational and proof complexityparallel algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Canonical forms, reductions, classification (15A21) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Determinant: Old algorithms, new insights
• Determinant: Old Algorithms, New Insights
• scientific article; zbMATH DE number 1332669
• Faster algorithms for the characteristic polynomial
• scientific article; zbMATH DE number 2235064

Cited in

(2)

• Monge sequences and a simple assignment algorithm
• Clarkson's algorithm for violator spaces

This page was built for publication: Berkowitz's algorithm and clow sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2783464)