Evaluating Straight-Line Programs over Balls

Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is bes...

Full description

Saved in:
Bibliographic Details
Main Authors: Van Der Hoeven, Joris, Lecerf, Gregoire
Format: Conference Proceeding
Language:English
Subjects:
ball arithmetic
C++ languages
Context
Hardware
Libraries
polynomial evaluation
Program processors
Reliability
software implementation
Switches
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 149
container_issue
container_start_page 142
container_title
container_volume
creator Van Der Hoeven, Joris
Lecerf, Gregoire
description Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.
doi_str_mv 10.1109/ARITH.2016.12
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_7563283</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>7563283</ieee_id><sourcerecordid>7563283</sourcerecordid><originalsourceid>FETCH-LOGICAL-i214t-ac2660314e23e48311d19c0d5bc43d9d2472cadb8aa7afdebd3bec54a0be7cf93</originalsourceid><addsrcrecordid>eNotzE9LwzAYgPEICs65oycv_QCm5k3S_DnOsblBQdF5Hm-TtzXSbZLWgd9eQU8Pv8vD2A2IEkD4-_nLZrsupQBTgjxjM28dVML_Gow9ZxMQRnHjnL9kV8PwIQR4b-yE3S1P2H_hmA5d8TpmTN37yOt0oOI5H7uM-6E4nigXD9j3wzW7aLEfaPbfKXtbLbeLNa-fHjeLec2TBD1yDNIYoUCTVKSdAojgg4hVE7SKPkptZcDYOESLbaQmqoZCpVE0ZEPr1ZTd_n0TEe0-c9pj_t7ZyijplPoBwRFCYw</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Evaluating Straight-Line Programs over Balls</title><source>IEEE Xplore All Conference Series</source><creator>Van Der Hoeven, Joris ; Lecerf, Gregoire</creator><creatorcontrib>Van Der Hoeven, Joris ; Lecerf, Gregoire</creatorcontrib><description>Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.</description><identifier>ISSN: 1063-6889</identifier><identifier>EISBN: 9781509016167</identifier><identifier>EISBN: 1509016163</identifier><identifier>DOI: 10.1109/ARITH.2016.12</identifier><identifier>CODEN: IEEPAD</identifier><language>eng</language><publisher>IEEE</publisher><subject>ball arithmetic ; C++ languages ; Context ; Hardware ; Libraries ; polynomial evaluation ; Program processors ; Reliability ; software implementation ; Switches</subject><ispartof>2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), 2016, p.142-149</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/7563283$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,27925,54555,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/7563283$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Van Der Hoeven, Joris</creatorcontrib><creatorcontrib>Lecerf, Gregoire</creatorcontrib><title>Evaluating Straight-Line Programs over Balls</title><title>2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH)</title><addtitle>ARITH</addtitle><description>Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.</description><subject>ball arithmetic</subject><subject>C++ languages</subject><subject>Context</subject><subject>Hardware</subject><subject>Libraries</subject><subject>polynomial evaluation</subject><subject>Program processors</subject><subject>Reliability</subject><subject>software implementation</subject><subject>Switches</subject><issn>1063-6889</issn><isbn>9781509016167</isbn><isbn>1509016163</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2016</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotzE9LwzAYgPEICs65oycv_QCm5k3S_DnOsblBQdF5Hm-TtzXSbZLWgd9eQU8Pv8vD2A2IEkD4-_nLZrsupQBTgjxjM28dVML_Gow9ZxMQRnHjnL9kV8PwIQR4b-yE3S1P2H_hmA5d8TpmTN37yOt0oOI5H7uM-6E4nigXD9j3wzW7aLEfaPbfKXtbLbeLNa-fHjeLec2TBD1yDNIYoUCTVKSdAojgg4hVE7SKPkptZcDYOESLbaQmqoZCpVE0ZEPr1ZTd_n0TEe0-c9pj_t7ZyijplPoBwRFCYw</recordid><startdate>201607</startdate><enddate>201607</enddate><creator>Van Der Hoeven, Joris</creator><creator>Lecerf, Gregoire</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>201607</creationdate><title>Evaluating Straight-Line Programs over Balls</title><author>Van Der Hoeven, Joris ; Lecerf, Gregoire</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i214t-ac2660314e23e48311d19c0d5bc43d9d2472cadb8aa7afdebd3bec54a0be7cf93</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2016</creationdate><topic>ball arithmetic</topic><topic>C++ languages</topic><topic>Context</topic><topic>Hardware</topic><topic>Libraries</topic><topic>polynomial evaluation</topic><topic>Program processors</topic><topic>Reliability</topic><topic>software implementation</topic><topic>Switches</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Van Der Hoeven, Joris</creatorcontrib><creatorcontrib>Lecerf, Gregoire</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Van Der Hoeven, Joris</au><au>Lecerf, Gregoire</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Evaluating Straight-Line Programs over Balls</atitle><btitle>2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH)</btitle><stitle>ARITH</stitle><date>2016-07</date><risdate>2016</risdate><spage>142</spage><epage>149</epage><pages>142-149</pages><issn>1063-6889</issn><eisbn>9781509016167</eisbn><eisbn>1509016163</eisbn><coden>IEEPAD</coden><abstract>Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.</abstract><pub>IEEE</pub><doi>10.1109/ARITH.2016.12</doi><tpages>8</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1063-6889
ispartof 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), 2016, p.142-149
issn 1063-6889
language eng
recordid cdi_ieee_primary_7563283
source IEEE Xplore All Conference Series
subjects ball arithmetic
C++ languages
Context
Hardware
Libraries
polynomial evaluation
Program processors
Reliability
software implementation
Switches
title Evaluating Straight-Line Programs over Balls
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T13%3A53%3A14IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Evaluating%20Straight-Line%20Programs%20over%20Balls&rft.btitle=2016%20IEEE%2023nd%20Symposium%20on%20Computer%20Arithmetic%20(ARITH)&rft.au=Van%20Der%20Hoeven,%20Joris&rft.date=2016-07&rft.spage=142&rft.epage=149&rft.pages=142-149&rft.issn=1063-6889&rft.coden=IEEPAD&rft_id=info:doi/10.1109/ARITH.2016.12&rft.eisbn=9781509016167&rft.eisbn_list=1509016163&rft_dat=%3Cieee_CHZPO%3E7563283%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i214t-ac2660314e23e48311d19c0d5bc43d9d2472cadb8aa7afdebd3bec54a0be7cf93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=7563283&rfr_iscdi=true