{
  "id": "1405.0223",
  "version": "v2",
  "published": "2014-05-01T17:18:17.000Z",
  "updated": "2016-12-30T08:11:13.000Z",
  "title": "Fast symmetric factorization of hierarchical matrices with applications",
  "authors": [
    "Sivaram Ambikasaran",
    "Michael O'Neil",
    "Karan Raj Singh"
  ],
  "comment": "18 pages, 8 figures, 1 table",
  "categories": [
    "math.NA",
    "cs.NA",
    "physics.flu-dyn",
    "stat.CO"
  ],
  "abstract": "We present a fast direct algorithm for computing symmetric factorizations, i.e. $A = WW^T$, of symmetric positive-definite hierarchical matrices with weak-admissibility conditions. The computational cost for the symmetric factorization scales as $\\mathcal{O}(n \\log^2 n)$ for hierarchically off-diagonal low-rank matrices. Once this factorization is obtained, the cost for inversion, application, and determinant computation scales as $\\mathcal{O}(n \\log n)$. In particular, this allows for the near optimal generation of correlated random variates in the case where $A$ is a covariance matrix. This symmetric factorization algorithm depends on two key ingredients. First, we present a novel symmetric factorization formula for low-rank updates to the identity of the form $I+UKU^T$. This factorization can be computed in $\\mathcal{O}(n)$ time if the rank of the perturbation is sufficiently small. Second, combining this formula with a recursive divide-and-conquer strategy, near linear complexity symmetric factorizations for hierarchically structured matrices can be obtained. We present numerical results for matrices relevant to problems in probability \\& statistics (Gaussian processes), interpolation (Radial basis functions), and Brownian dynamics calculations in fluid mechanics (the Rotne-Prager-Yamakawa tensor).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-01T17:18:17.000Z",
      "abstract": "We present a fast direct algorithm for computing symmetric factorizations, i.e. $A = WW^T$, of symmetric positive-definite hierarchical matrices with weak-admissibility conditions. The computational cost for the symmetric factorization scales as $\\mathcal{O}(n \\log^2 n)$ for hierarchically off-diagonal low-rank matrices. Once this factorization is obtained, the cost for inversion, application, and determinant computation scales as $\\mathcal{O}(n \\log n)$. In particular, this allows for the near optimal generation of correlated random variates in the case where $A$ is a covariance matrix. This symmetric factorization algorithm depends on two key ingredients. First, we present a novel symmetric factorization formula for low-rank updates to the identity of the form $I+UKU^T$. This factorization can be computed in $\\mathcal{O}(n)$ time, if the rank of the perturbation is sufficiently small. Second, combining this formula with a recursive divide-and-conquer strategy, near linear complexity symmetric factorizations for hierarchically structured matrices can be obtained. We present numerical results for matrices relevant to problems in probability \\& statistics (Gaussian processes), interpolation (Radial basis functions), and Brownian dynamics calculations in fluid mechanics (the Rotne-Prager-Yamakawa tensor).",
      "comment": "15 pages, 5 figures, 3 tables",
      "journal": null,
      "doi": null,
      "authors": [
        "Sivaram Ambikasaran",
        "Michael O'Neil"
      ]
    },
    {
      "version": "v2",
      "updated": "2016-12-30T08:11:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "fast symmetric factorization",
      "application",
      "symmetric factorization algorithm depends",
      "novel symmetric factorization formula",
      "linear complexity symmetric factorizations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.0223A"
    }
  }
}