{
  "id": "1512.02671",
  "version": "v1",
  "published": "2015-12-08T21:51:53.000Z",
  "updated": "2015-12-08T21:51:53.000Z",
  "title": "Householder QR Factorization: Adding Randomization for Column Pivoting. FLAME Working Note #78",
  "authors": [
    "Per-Gunnar Martinsson",
    "Gregorio Quintana-Orti",
    "Nathan Heavner",
    "Robert van de Geijn"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "A fundamental problem when adding column pivoting to the Householder QR factorization is that only about half of the computation can be cast in terms of high performing matrix-matrix multiplication, which greatly limits the benefits of so-called blocked algorithms. This paper describes a technique for selecting groups of pivot vectors by means of randomized projections. It is demonstrated that the asymptotic flop count for the proposed method is $2mn^2 - (2/3)n^3$ for an $m\\times n$ matrix with $m \\geq n$, identical to that of the best classical Householder QR factorization (with or without pivoting). Experiments demonstrate improvements in speed of substantial integer factors (between a factor of 3 and 5) relative to LAPACK's geqp3 implementation on a modern CPU.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-08T21:51:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "flame working note",
      "column pivoting",
      "adding randomization",
      "best classical householder qr factorization",
      "lapacks geqp3 implementation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}