Berkowitz's Algorithm and Clow Sequences

Simple item page
dc.creatorSoltys, Michael
dc.date2002-01-31
dc.date.accessioned2026-07-07T04:46:13Z
dc.date.available2026-07-07T04:46:13Z
dc.descriptionWe 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.
dc.descriptionSubmitted to ELA (Electronic Journal of Linear Algebra)
dc.identifierhttps://arxiv.org/abs/math/0201315
dc.identifierhttp://arxiv.org/abs/math/0201315
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/63245
dc.subjectRings and Algebras
dc.subject65F30; 11Y16
dc.titleBerkowitz's Algorithm and Clow Sequences
dc.typetext

Files

Collections

arXiv