Geodesic
Berkowitz's algorithm and clow sequences
The electronic journal of linear algebra, Tome 9 (2002), pp. 42-54.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: A combinatorial interpretation of Berkowitz's algorithm is presented. Berkowitz's algorithm is the fastest known parallel algorithm for computing the characteristic polynomial of a matrix. The combinatorial interpretation is based on "loop covers" introduced by Valiant, and "clow sequences", defined by Mahajan and Vinay. Clow sequences turn out to capture very succinctly the computations performed by Berkowitz's algorithm, which otherwise are quite difficult to analyze. The main contribution of this paper is a proof of correctness of Berkowitz's algorithm in terms of clow sequences.
Classification : 65F30, 11Y16
Keywords: berkowitz's algorithm, clow sequences, computational and proof complexity, parallel algorithms, characteristic polynomial 
@article{ELA_2002__9__a19,
     author = {Soltys, Michael},
     title = {Berkowitz's algorithm and clow sequences},
     journal = {The electronic journal of linear algebra},
     pages = {42--54},
     publisher = {mathdoc},
     volume = {9},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2002__9__a19/}
}
TY  - JOUR
AU  - Soltys, Michael
TI  - Berkowitz's algorithm and clow sequences
JO  - The electronic journal of linear algebra
PY  - 2002
SP  - 42
EP  - 54
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2002__9__a19/
LA  - en
ID  - ELA_2002__9__a19
ER  - 
%0 Journal Article
%A Soltys, Michael
%T Berkowitz's algorithm and clow sequences
%J The electronic journal of linear algebra
%D 2002
%P 42-54
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2002__9__a19/
%G en
%F ELA_2002__9__a19
Soltys, Michael. Berkowitz's algorithm and clow sequences. The electronic journal of linear algebra, Tome 9 (2002), pp. 42-54. http://geodesic.mathdoc.fr/item/ELA_2002__9__a19/