Linear Programming for Bernstein Based Solvers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Dominique Michelucci , Christoph Fünfzig

ABSTRACT

Some interval Newton solvers rely on tensorial Bernstein bases to compute sharp enclosures of multivariate polynomials on the unit hypercube. These solvers compute all coefficients with respect to tensorial Bernstein bases. Unfortunately, polynomials become exponential size in tensorial Bernstein bases. This article gives the first polynomial time method to solve this issue. A polynomial number of relevant Bernstein polynomials is selected. The non-negativity of each of these Bernstein polynomials gives a linear inequality in a space connected to the monomials of the canonical tensorial basis. We resort to linear programming on the resulting Bernstein polytope to compute range bounds of a polynomial or bounds of the zero set. More... »

PAGES

163-178

Book

TITLE

Automated Deduction in Geometry

ISBN

978-3-642-21045-7
978-3-642-21046-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-21046-4_8

DOI

http://dx.doi.org/10.1007/978-3-642-21046-4_8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1048452092


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "LE2I, UMR CNRS 5158, 9 av Alain Savary, BP 47870, 21078\u00a0Dijon cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Michelucci", 
        "givenName": "Dominique", 
        "id": "sg:person.011153340565.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011153340565.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "LE2I, UMR CNRS 5158, 9 av Alain Savary, BP 47870, 21078\u00a0Dijon cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "F\u00fcnfzig", 
        "givenName": "Christoph", 
        "id": "sg:person.07520622331.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07520622331.35"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s11155-007-9043-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000150256", 
          "https://doi.org/10.1007/s11155-007-9043-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2008.04.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008501672"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1629255.1629271", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012719725"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0362-546x(01)00166-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012789389"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2005.09.055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013339434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-8396(02)00146-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017995799"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-8396(02)00146-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017995799"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2495-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026875258", 
          "https://doi.org/10.1007/978-1-4757-2495-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2495-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026875258", 
          "https://doi.org/10.1007/978-1-4757-2495-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/376957.376958", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027860207"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00371-007-0184-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033048183", 
          "https://doi.org/10.1007/s00371-007-0184-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00371-007-0184-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033048183", 
          "https://doi.org/10.1007/s00371-007-0184-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-8396(93)90019-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048239852"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/5763", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098937331"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Some interval Newton solvers rely on tensorial Bernstein bases to compute sharp enclosures of multivariate polynomials on the unit hypercube. These solvers compute all coefficients with respect to tensorial Bernstein bases. Unfortunately, polynomials become exponential size in tensorial Bernstein bases. This article gives the first polynomial time method to solve this issue. A polynomial number of relevant Bernstein polynomials is selected. The non-negativity of each of these Bernstein polynomials gives a linear inequality in a space connected to the monomials of the canonical tensorial basis. We resort to linear programming on the resulting Bernstein polytope to compute range bounds of a polynomial or bounds of the zero set.", 
    "editor": [
      {
        "familyName": "Sturm", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Zengler", 
        "givenName": "Christoph", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-21046-4_8", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21045-7", 
        "978-3-642-21046-4"
      ], 
      "name": "Automated Deduction in Geometry", 
      "type": "Book"
    }, 
    "name": "Linear Programming for Bernstein Based Solvers", 
    "pagination": "163-178", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-21046-4_8"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e6d135abfba010d271ccc0d6855581b5d2f522f4964005a4d3dc9840b74f6fef"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048452092"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-21046-4_8", 
      "https://app.dimensions.ai/details/publication/pub.1048452092"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T13:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000594.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-21046-4_8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21046-4_8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21046-4_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21046-4_8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21046-4_8'


 

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-21046-4_8 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ne47f9bb579d24e1c80f8bab2ba12ef98
4 schema:citation sg:pub.10.1007/978-1-4757-2495-0
5 sg:pub.10.1007/s00371-007-0184-x
6 sg:pub.10.1007/s11155-007-9043-8
7 https://doi.org/10.1016/0167-8396(93)90019-y
8 https://doi.org/10.1016/j.jsc.2008.04.016
9 https://doi.org/10.1016/j.tcs.2005.09.055
10 https://doi.org/10.1016/s0167-8396(02)00146-2
11 https://doi.org/10.1016/s0362-546x(01)00166-3
12 https://doi.org/10.1142/5763
13 https://doi.org/10.1145/1629255.1629271
14 https://doi.org/10.1145/376957.376958
15 schema:datePublished 2011
16 schema:datePublishedReg 2011-01-01
17 schema:description Some interval Newton solvers rely on tensorial Bernstein bases to compute sharp enclosures of multivariate polynomials on the unit hypercube. These solvers compute all coefficients with respect to tensorial Bernstein bases. Unfortunately, polynomials become exponential size in tensorial Bernstein bases. This article gives the first polynomial time method to solve this issue. A polynomial number of relevant Bernstein polynomials is selected. The non-negativity of each of these Bernstein polynomials gives a linear inequality in a space connected to the monomials of the canonical tensorial basis. We resort to linear programming on the resulting Bernstein polytope to compute range bounds of a polynomial or bounds of the zero set.
18 schema:editor N2cb8a586045948d1a0e540e378da214f
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N12a9b8d874df42bfa5f051e1c2ad72b2
23 schema:name Linear Programming for Bernstein Based Solvers
24 schema:pagination 163-178
25 schema:productId N6c00f2189f924685adca68525253815e
26 Nd144e3c4924e4ec48e97f6d1cd55e800
27 Nf824d8ed21104965a01a103065a17501
28 schema:publisher Nef5e844e01bf48aa995c4a6ab0577b31
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048452092
30 https://doi.org/10.1007/978-3-642-21046-4_8
31 schema:sdDatePublished 2019-04-15T13:09
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N38d9d4aaa34c47e492f433342773ec9e
34 schema:url http://link.springer.com/10.1007/978-3-642-21046-4_8
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N01f5518840f047e5b349363227d7cd2f schema:familyName Zengler
39 schema:givenName Christoph
40 rdf:type schema:Person
41 N0fe71d5ba320447a9135bd413fc92349 rdf:first N01f5518840f047e5b349363227d7cd2f
42 rdf:rest rdf:nil
43 N12a9b8d874df42bfa5f051e1c2ad72b2 schema:isbn 978-3-642-21045-7
44 978-3-642-21046-4
45 schema:name Automated Deduction in Geometry
46 rdf:type schema:Book
47 N286e8f1d4be941f7973fedf4b81197a8 schema:familyName Sturm
48 schema:givenName Thomas
49 rdf:type schema:Person
50 N2cb8a586045948d1a0e540e378da214f rdf:first N286e8f1d4be941f7973fedf4b81197a8
51 rdf:rest N0fe71d5ba320447a9135bd413fc92349
52 N38d9d4aaa34c47e492f433342773ec9e schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N497dbf70f47f453799ec8a33e35321bc schema:name LE2I, UMR CNRS 5158, 9 av Alain Savary, BP 47870, 21078 Dijon cedex, France
55 rdf:type schema:Organization
56 N6c00f2189f924685adca68525253815e schema:name doi
57 schema:value 10.1007/978-3-642-21046-4_8
58 rdf:type schema:PropertyValue
59 Nc33c9548172b4a509242c1037a13cb5c schema:name LE2I, UMR CNRS 5158, 9 av Alain Savary, BP 47870, 21078 Dijon cedex, France
60 rdf:type schema:Organization
61 Nd05c9a6d3a704cdba313fa0ec198465a rdf:first sg:person.07520622331.35
62 rdf:rest rdf:nil
63 Nd144e3c4924e4ec48e97f6d1cd55e800 schema:name readcube_id
64 schema:value e6d135abfba010d271ccc0d6855581b5d2f522f4964005a4d3dc9840b74f6fef
65 rdf:type schema:PropertyValue
66 Ne47f9bb579d24e1c80f8bab2ba12ef98 rdf:first sg:person.011153340565.56
67 rdf:rest Nd05c9a6d3a704cdba313fa0ec198465a
68 Nef5e844e01bf48aa995c4a6ab0577b31 schema:location Berlin, Heidelberg
69 schema:name Springer Berlin Heidelberg
70 rdf:type schema:Organisation
71 Nf824d8ed21104965a01a103065a17501 schema:name dimensions_id
72 schema:value pub.1048452092
73 rdf:type schema:PropertyValue
74 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
75 schema:name Mathematical Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
78 schema:name Pure Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.011153340565.56 schema:affiliation N497dbf70f47f453799ec8a33e35321bc
81 schema:familyName Michelucci
82 schema:givenName Dominique
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011153340565.56
84 rdf:type schema:Person
85 sg:person.07520622331.35 schema:affiliation Nc33c9548172b4a509242c1037a13cb5c
86 schema:familyName Fünfzig
87 schema:givenName Christoph
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07520622331.35
89 rdf:type schema:Person
90 sg:pub.10.1007/978-1-4757-2495-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026875258
91 https://doi.org/10.1007/978-1-4757-2495-0
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/s00371-007-0184-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1033048183
94 https://doi.org/10.1007/s00371-007-0184-x
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/s11155-007-9043-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000150256
97 https://doi.org/10.1007/s11155-007-9043-8
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0167-8396(93)90019-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1048239852
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/j.jsc.2008.04.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008501672
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/j.tcs.2005.09.055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013339434
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/s0167-8396(02)00146-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017995799
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/s0362-546x(01)00166-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012789389
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1142/5763 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098937331
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1145/1629255.1629271 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012719725
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/376957.376958 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027860207
114 rdf:type schema:CreativeWork
 




Preview window. Press ESC to close (or click here)


...