The F5 algorithm for computing Gröbner bases achieves a high level of efficiency through the careful analysis of signatures assigned to each computed polynomial. However, it computes and uses many polynomials that turn out to be redundant. Eliminating these redundant polynomials is a non-trivial task, because they correspond to signatures required for reduction. This paper revisits the theory underlying F5 and describes F5C, a new variant that prunes redundant polynomials, then re-computes signatures to preserve correctness. This strategy successfully reduces both overhead and execution time.

References in zbMATH (referenced in 30 articles )

Showing results 1 to 20 of 30.
Sorted by year (citations)

1 2 next

  1. Maletzky, Alexander: A generic and executable formalization of signature-based Gröbner basis algorithms (2021)
  2. Francis, Maria; Verron, Thibaut: A signature-based algorithm for computing Gröbner bases over principal ideal domains (2020)
  3. Hashemi, Amir; Kreuzer, Martin; Pourkhajouei, Samira: Computing coupled border bases (2020)
  4. Laird, Lucas; Tillquist, Richard C.; Becker, Stephen; Lladser, Manuel E.: Resolvability of Hamming graphs (2020)
  5. Li, Ting; Sun, Yao; Huang, Zhenyu; Wang, Dingkang; Lin, Dongdai: Speeding up the GVW algorithm via a substituting method (2019)
  6. Lu, Dong; Wang, Dingkang; Xiao, Fanghui; Zhou, Jie: Extending the GVW algorithm to local ring (2018)
  7. Eder, Christian; Faugère, Jean-Charles: A survey on signature-based algorithms for computing Gröbner bases (2017)
  8. Chen, Gang; Liu, Junyu; Xie, Ruofei; Zhang, Hao; Zhou, Yehao: Syzygies probing scattering amplitudes (2016)
  9. Gao, Shuhong; Volny, Frank IV; Wang, Mingsheng: A new framework for computing Gröbner bases (2016)
  10. Sun, Yao; Huang, Zhenyu; Wang, Dingkang; Lin, Dongdai: An improvement over the GVW algorithm for inhomogeneous polynomial systems (2016)
  11. Tang, Min; Yang, Zhengfeng; Zeng, Zhenbing: Resultant elimination via implicit equation interpolation (2016)
  12. Diem, Claus: Bounded regularity (2015)
  13. Zheng, Licui; Liu, Jinwang; Liu, Weijun; Li, Dongmei: A new signature-based algorithms for computing Gröbner bases (2015)
  14. Eder, Christian: Predicting zero reductions in Gröbner basis computations (2014)
  15. Galkin, V. V.: Termination of the F5 algorithm (2014)
  16. Eder, Christian: An analysis of inhomogeneous signature-based Gröbner basis computations (2013)
  17. Galkin, V. V.: Simple signature based iterative algorithm for calculation of Gröbner bases (2013)
  18. Gerdt, Vladimir P.; Hashemi, Amir; M.-Alizadeh, Benyamin: Involutive bases algorithm incorporating F(_5) criterion (2013)
  19. Hashemi, Amir; M.-Alizadeh, Benyamin; Riahi, Monireh: Invariant (\mathrmG^2\mathrmV) algorithm for computing SAGBI-Gröbner bases (2013)
  20. Joux, Antoine; Vitse, Vanessa: Elliptic curve discrete logarithm problem over small degree extension fields (2013)

1 2 next