Berkowitz's algorithm and clow sequences Academic Article uri icon

  •  
  • Overview
  •  
  • Research
  •  
  • Identity
  •  
  • Additional Document Info
  •  
  • View All
  •  

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.

publication date

  • January 1, 2002