{
  "id": "math/0201315",
  "version": "v1",
  "published": "2002-01-31T15:05:05.000Z",
  "updated": "2002-01-31T15:05:05.000Z",
  "title": "Berkowitz's Algorithm and Clow Sequences",
  "authors": [
    "Michael Soltys"
  ],
  "comment": "Submitted to ELA (Electronic Journal of Linear Algebra)",
  "categories": [
    "math.RA"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2002-01-31T15:05:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65F30",
      "11Y16"
    ],
    "keywords": [
      "berkowitzs algorithm",
      "combinatorial interpretation",
      "clow sequences turn",
      "main contribution",
      "parallel algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math......1315S"
    }
  }
}