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!
Description
Summary: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.
ISSN:1661-8270
1661-8289
DOI:10.1007/s11786-020-00459-z