A Signature Based Border Basis Algorithm

The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same an...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics in computer science 2020-03, Vol.14 (1), p.177-189
Main Authors: Horáček, Jan, Kreuzer, Martin, Messeng Ekossono, Ange-Salomé
Format: Article
Language:English
Subjects:
Algorithms
Boolean
Boolean algebra
Computer Science
Mathematics
Mathematics and Statistics
Polynomials
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c270t-2814473075288f4c490ab88b8d5c008338d94b88b809f77c293a6cb1e8e546b43
container_end_page 189
container_issue 1
container_start_page 177
container_title Mathematics in computer science
container_volume 14
creator Horáček, Jan
Kreuzer, Martin
Messeng Ekossono, Ange-Salomé
description The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.
doi_str_mv 10.1007/s11786-020-00459-z
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2376270853</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2376270853</sourcerecordid><originalsourceid>FETCH-LOGICAL-c270t-2814473075288f4c490ab88b8d5c008338d94b88b809f77c293a6cb1e8e546b43</originalsourceid><addsrcrecordid>eNp9kLtOwzAUhi0EEqXwAkyRWFgMx5fYJ2NaUUCqxADMVuI4IVWbFDsd6NPjNgg2pnPRf5E-Qq4Z3DEAfR8Y06gocKAAMs3o_oRMmFKMIsfs9HfXcE4uQlgBKM4km5DbPHltm64Ydt4lsyK4Kpn1vnL-cLQhyddN79vhY3NJzupiHdzVz5yS98XD2_yJLl8en-f5ktoYPlCOTEotQKccsZZWZlCUiCVWqQVAIbDK5PEBWa215ZkolC2ZQ5dKVUoxJTdj7tb3nzsXBrPqd76LlYYLrWIJpiKq-Kiyvg_Bu9psfbsp_JdhYA5EzEjERCLmSMTso0mMphDFXeP8X_Q_rm_a-mEH</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2376270853</pqid></control><display><type>article</type><title>A Signature Based Border Basis Algorithm</title><source>Springer Link</source><creator>Horáček, Jan ; Kreuzer, Martin ; Messeng Ekossono, Ange-Salomé</creator><creatorcontrib>Horáček, Jan ; Kreuzer, Martin ; Messeng Ekossono, Ange-Salomé</creatorcontrib><description>The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.</description><identifier>ISSN: 1661-8270</identifier><identifier>EISSN: 1661-8289</identifier><identifier>DOI: 10.1007/s11786-020-00459-z</identifier><language>eng</language><publisher>Cham: Springer International Publishing</publisher><subject>Algorithms ; Boolean ; Boolean algebra ; Computer Science ; Mathematics ; Mathematics and Statistics ; Polynomials</subject><ispartof>Mathematics in computer science, 2020-03, Vol.14 (1), p.177-189</ispartof><rights>Springer Nature Switzerland AG 2020</rights><rights>2020© Springer Nature Switzerland AG 2020</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c270t-2814473075288f4c490ab88b8d5c008338d94b88b809f77c293a6cb1e8e546b43</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Horáček, Jan</creatorcontrib><creatorcontrib>Kreuzer, Martin</creatorcontrib><creatorcontrib>Messeng Ekossono, Ange-Salomé</creatorcontrib><title>A Signature Based Border Basis Algorithm</title><title>Mathematics in computer science</title><addtitle>Math.Comput.Sci</addtitle><description>The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.</description><subject>Algorithms</subject><subject>Boolean</subject><subject>Boolean algebra</subject><subject>Computer Science</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Polynomials</subject><issn>1661-8270</issn><issn>1661-8289</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp9kLtOwzAUhi0EEqXwAkyRWFgMx5fYJ2NaUUCqxADMVuI4IVWbFDsd6NPjNgg2pnPRf5E-Qq4Z3DEAfR8Y06gocKAAMs3o_oRMmFKMIsfs9HfXcE4uQlgBKM4km5DbPHltm64Ydt4lsyK4Kpn1vnL-cLQhyddN79vhY3NJzupiHdzVz5yS98XD2_yJLl8en-f5ktoYPlCOTEotQKccsZZWZlCUiCVWqQVAIbDK5PEBWa215ZkolC2ZQ5dKVUoxJTdj7tb3nzsXBrPqd76LlYYLrWIJpiKq-Kiyvg_Bu9psfbsp_JdhYA5EzEjERCLmSMTso0mMphDFXeP8X_Q_rm_a-mEH</recordid><startdate>20200301</startdate><enddate>20200301</enddate><creator>Horáček, Jan</creator><creator>Kreuzer, Martin</creator><creator>Messeng Ekossono, Ange-Salomé</creator><general>Springer International Publishing</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20200301</creationdate><title>A Signature Based Border Basis Algorithm</title><author>Horáček, Jan ; Kreuzer, Martin ; Messeng Ekossono, Ange-Salomé</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c270t-2814473075288f4c490ab88b8d5c008338d94b88b809f77c293a6cb1e8e546b43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Algorithms</topic><topic>Boolean</topic><topic>Boolean algebra</topic><topic>Computer Science</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Polynomials</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Horáček, Jan</creatorcontrib><creatorcontrib>Kreuzer, Martin</creatorcontrib><creatorcontrib>Messeng Ekossono, Ange-Salomé</creatorcontrib><collection>CrossRef</collection><jtitle>Mathematics in computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Horáček, Jan</au><au>Kreuzer, Martin</au><au>Messeng Ekossono, Ange-Salomé</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Signature Based Border Basis Algorithm</atitle><jtitle>Mathematics in computer science</jtitle><stitle>Math.Comput.Sci</stitle><date>2020-03-01</date><risdate>2020</risdate><volume>14</volume><issue>1</issue><spage>177</spage><epage>189</epage><pages>177-189</pages><issn>1661-8270</issn><eissn>1661-8289</eissn><abstract>The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.</abstract><cop>Cham</cop><pub>Springer International Publishing</pub><doi>10.1007/s11786-020-00459-z</doi><tpages>13</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1661-8270
ispartof Mathematics in computer science, 2020-03, Vol.14 (1), p.177-189
issn 1661-8270
1661-8289
language eng
recordid cdi_proquest_journals_2376270853
source Springer Link
subjects Algorithms
Boolean
Boolean algebra
Computer Science
Mathematics
Mathematics and Statistics
Polynomials
title A Signature Based Border Basis Algorithm
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T21%3A00%3A53IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20Signature%20Based%20Border%20Basis%20Algorithm&rft.jtitle=Mathematics%20in%20computer%20science&rft.au=Hor%C3%A1%C4%8Dek,%20Jan&rft.date=2020-03-01&rft.volume=14&rft.issue=1&rft.spage=177&rft.epage=189&rft.pages=177-189&rft.issn=1661-8270&rft.eissn=1661-8289&rft_id=info:doi/10.1007/s11786-020-00459-z&rft_dat=%3Cproquest_cross%3E2376270853%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c270t-2814473075288f4c490ab88b8d5c008338d94b88b809f77c293a6cb1e8e546b43%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2376270853&rft_id=info:pmid/&rfr_iscdi=true