{
  "id": "math/0212179",
  "version": "v1",
  "published": "2002-12-12T20:25:48.000Z",
  "updated": "2002-12-12T20:25:48.000Z",
  "title": "High Probability Analysis of the Condition Number of Sparse Polynomial Systems",
  "authors": [
    "Gregorio Malajovich",
    "J. Maurice Rojas"
  ],
  "comment": "29 pages, no figures. Extensive revision and streamlining of math.NA/0012104. In particular, new theorem with explicit high probability estimate of the condition number of a random sparse polynomial system (Theorem 1) has been added",
  "journal": "Theoretical Computer Science, Volume 315, Issues 2-3, 6 May 2004, Pages 525-555.",
  "doi": "10.1016/j.tcs.2004.01.006",
  "categories": [
    "math.NA",
    "math.AG"
  ],
  "abstract": "Let F:=(f_1,...,f_n) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than 1/epsilon. The bound depends on an integral of a differential form on a toric manifold and admits a simple explicit upper bound when the Newton polytopes (and underlying covariances) are all identical. We also consider polynomials with real coefficients and give bounds for the expected number of real roots and (restricted) condition number. Using a Kahler geometric framework throughout, we also express the expected number of roots of f inside a region U as the integral over U of a certain {\\bf mixed volume} form, thus recovering the classical mixed volume when U = (C^*)^n.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2002-12-12T20:25:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "condition number",
      "high probability analysis",
      "sparse polynomial systems",
      "simple explicit upper bound",
      "kahler geometric framework throughout"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math.....12179M"
    }
  }
}