Improved sparse multivariate polynomial interpolation algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1989

AUTHORS

Erich Kaltofen , Lakshman Yagati

ABSTRACT

We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the other due to Zippel (1988). We present efficient algorithms for finding the rank of certain special Toeplitz systems arising in the Ben-Or and Tiwari algorithm and for solving transposed Vandermonde systems of equations, the use of which greatly improves the time complexities of the two interpolation algorithms. More... »

PAGES

467-474

References to SciGraph publications

  • 1979. Probabilistic algorithms for sparse polynomials in SYMBOLIC AND ALGEBRAIC COMPUTATION
  • Book

    TITLE

    Symbolic and Algebraic Computation

    ISBN

    978-3-540-51084-0
    978-3-540-46153-1

    Author Affiliations

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-51084-2_44

    DOI

    http://dx.doi.org/10.1007/3-540-51084-2_44

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Rensselaer Polytechnic Institute", 
              "id": "https://www.grid.ac/institutes/grid.33647.35", 
              "name": [
                "Department of Computer Science, Rensselaer Polytechnic Institute, 12180-3590\u00a0Troy, New York"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kaltofen", 
            "givenName": "Erich", 
            "id": "sg:person.013117774373.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013117774373.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Rensselaer Polytechnic Institute", 
              "id": "https://www.grid.ac/institutes/grid.33647.35", 
              "name": [
                "Department of Computer Science, Rensselaer Polytechnic Institute, 12180-3590\u00a0Troy, New York"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yagati", 
            "givenName": "Lakshman", 
            "id": "sg:person.01007667674.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01007667674.71"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0747-7171(08)80018-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024811749"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-09519-5_73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030416919", 
              "https://doi.org/10.1007/3-540-09519-5_73"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/74540.74556", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034342820"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321662.321665", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034811621"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/62212.62241", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037365455"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(80)90013-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049330426"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0212017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841697"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989", 
        "datePublishedReg": "1989-01-01", 
        "description": "We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the other due to Zippel (1988). We present efficient algorithms for finding the rank of certain special Toeplitz systems arising in the Ben-Or and Tiwari algorithm and for solving transposed Vandermonde systems of equations, the use of which greatly improves the time complexities of the two interpolation algorithms.", 
        "editor": [
          {
            "familyName": "Gianni", 
            "givenName": "P.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-51084-2_44", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3002150", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-540-51084-0", 
            "978-3-540-46153-1"
          ], 
          "name": "Symbolic and Algebraic Computation", 
          "type": "Book"
        }, 
        "name": "Improved sparse multivariate polynomial interpolation algorithms", 
        "pagination": "467-474", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-51084-2_44"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5e6443e536c14199bf895f396330d9add97e22042773be17564958e9b0b3b45b"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019811312"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-51084-2_44", 
          "https://app.dimensions.ai/details/publication/pub.1019811312"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T11:17", 
        "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_8660_00000034.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-51084-2_44"
      }
    ]
     

    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/3-540-51084-2_44'

    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/3-540-51084-2_44'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-51084-2_44'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-51084-2_44'


     

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

    96 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-51084-2_44 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N140cc332de00499b996c32b8fe6f6959
    4 schema:citation sg:pub.10.1007/3-540-09519-5_73
    5 https://doi.org/10.1016/0196-6774(80)90013-9
    6 https://doi.org/10.1016/s0747-7171(08)80018-1
    7 https://doi.org/10.1137/0212017
    8 https://doi.org/10.1145/321662.321665
    9 https://doi.org/10.1145/62212.62241
    10 https://doi.org/10.1145/74540.74556
    11 schema:datePublished 1989
    12 schema:datePublishedReg 1989-01-01
    13 schema:description We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the other due to Zippel (1988). We present efficient algorithms for finding the rank of certain special Toeplitz systems arising in the Ben-Or and Tiwari algorithm and for solving transposed Vandermonde systems of equations, the use of which greatly improves the time complexities of the two interpolation algorithms.
    14 schema:editor N1126b86ff90c45c3b2d793385953b9ab
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf Nf47c73808c55433f97648dea8cd70fd1
    19 schema:name Improved sparse multivariate polynomial interpolation algorithms
    20 schema:pagination 467-474
    21 schema:productId N292993a0f29a48aebc8bb31e877d8958
    22 Ncc7a6169651d4cf89539a97ce1cc6f72
    23 Nd4207961fe3b49eb933bc749809e2224
    24 schema:publisher Nea8b0cc2e22744d69d1551c682417ae3
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019811312
    26 https://doi.org/10.1007/3-540-51084-2_44
    27 schema:sdDatePublished 2019-04-15T11:17
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N6c841a2d581b4eb9a197fa7d5c556778
    30 schema:url http://link.springer.com/10.1007/3-540-51084-2_44
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N0816614f59c6400e9f6ac76cd242ea01 schema:familyName Gianni
    35 schema:givenName P.
    36 rdf:type schema:Person
    37 N1126b86ff90c45c3b2d793385953b9ab rdf:first N0816614f59c6400e9f6ac76cd242ea01
    38 rdf:rest rdf:nil
    39 N140cc332de00499b996c32b8fe6f6959 rdf:first sg:person.013117774373.47
    40 rdf:rest N6c6c9aca1e17469ab06041e3b40e5815
    41 N292993a0f29a48aebc8bb31e877d8958 schema:name doi
    42 schema:value 10.1007/3-540-51084-2_44
    43 rdf:type schema:PropertyValue
    44 N6c6c9aca1e17469ab06041e3b40e5815 rdf:first sg:person.01007667674.71
    45 rdf:rest rdf:nil
    46 N6c841a2d581b4eb9a197fa7d5c556778 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 Ncc7a6169651d4cf89539a97ce1cc6f72 schema:name dimensions_id
    49 schema:value pub.1019811312
    50 rdf:type schema:PropertyValue
    51 Nd4207961fe3b49eb933bc749809e2224 schema:name readcube_id
    52 schema:value 5e6443e536c14199bf895f396330d9add97e22042773be17564958e9b0b3b45b
    53 rdf:type schema:PropertyValue
    54 Nea8b0cc2e22744d69d1551c682417ae3 schema:location Berlin, Heidelberg
    55 schema:name Springer Berlin Heidelberg
    56 rdf:type schema:Organisation
    57 Nf47c73808c55433f97648dea8cd70fd1 schema:isbn 978-3-540-46153-1
    58 978-3-540-51084-0
    59 schema:name Symbolic and Algebraic Computation
    60 rdf:type schema:Book
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Computation Theory and Mathematics
    66 rdf:type schema:DefinedTerm
    67 sg:grant.3002150 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-51084-2_44
    68 rdf:type schema:MonetaryGrant
    69 sg:person.01007667674.71 schema:affiliation https://www.grid.ac/institutes/grid.33647.35
    70 schema:familyName Yagati
    71 schema:givenName Lakshman
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01007667674.71
    73 rdf:type schema:Person
    74 sg:person.013117774373.47 schema:affiliation https://www.grid.ac/institutes/grid.33647.35
    75 schema:familyName Kaltofen
    76 schema:givenName Erich
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013117774373.47
    78 rdf:type schema:Person
    79 sg:pub.10.1007/3-540-09519-5_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030416919
    80 https://doi.org/10.1007/3-540-09519-5_73
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0196-6774(80)90013-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049330426
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/s0747-7171(08)80018-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024811749
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1137/0212017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841697
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1145/321662.321665 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034811621
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1145/62212.62241 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037365455
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1145/74540.74556 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034342820
    93 rdf:type schema:CreativeWork
    94 https://www.grid.ac/institutes/grid.33647.35 schema:alternateName Rensselaer Polytechnic Institute
    95 schema:name Department of Computer Science, Rensselaer Polytechnic Institute, 12180-3590 Troy, New York
    96 rdf:type schema:Organization
     




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


    ...