NDLI: Parallel Gaussian elimination for Gröbner bases computations in finite fields

Please wait, while we are loading the content...

Techniques and tools for implementing IEEE 754 floating-point arithmetic on VLIW integer processors

Generic design of Chinese remaindering schemes

Spiral-generated modular FFT algorithms

Fifteen years after DSC and WLSS2 what parallel computations I do today: invited lecture at PASCO 2010

A complete modular resultant algorithm targeted for realization on graphics hardware

High performance linear algebra using interval arithmetic

Exploiting multicore systems with Cilk

Parallel operations of sparse polynomials on multicores: I. multiplication and Poisson bracket

Parallel computation of determinants of matrices with polynomial entries for robust control design

Automated performance tuning

Parallel computation of the minimal elements of a poset

Cache friendly sparse matrix-vector multiplication

Roomy: a system for space limited computations

Parallel disk-based computation for large, monolithic binary decision diagrams

Parallelising the computational algebra system GAP

Parallel arithmetic encryption for high-bandwidth communications on multicore/GPGPU platforms

Exact sparse matrix-vector multiplication on GPU's and multicore architectures

Parallel Gaussian elimination for Gröbner bases computations in finite fields

A quantitative study of reductions in algebraic libraries

Parallel sparse polynomial division using heaps

A high-performance algorithm for calculating cyclotomic polynomials

Accuracy versus time: a case study with summation algorithms

Polynomial homotopies on multicore workstations

Parallel computations in modular group algebras

Cache-oblivious polygon indecomposability testing

Parallel sparse polynomial interpolation over finite fields

Parallel Gaussian elimination for Gröbner bases computations in finite fields

Content Provider	ACM Digital Library
Author	Lachartre, Sylvain Faugère, Jean-Charles
Abstract	Polynomial system solving is one of the important area of Computer Algebra with many applications in Robotics, Cryptology, Computational Geometry, etc. To this end computing a Gröbner basis is often a crucial step. The most efficient algorithms [6, 7] for computing Gröbner bases [2] rely heavily on linear algebra techniques. In this paper, we present a new linear algebra package for computing Gaussian elimination of Gröbner bases matrices. The library is written in C and contains specific algorithms [11] to compute Gaussian elimination as well as specific internal representation of matrices (sparse triangular blocks, sparse rectangular blocks and hybrid rectangular blocks). The efficiency of the new software is demonstrated by showing computational results fr well known benchmarks as well as some crypto-challenges. For instance, for a medium size problem such as Katsura 15, it takes 849.7 sec on a PC with 8 cores to compute a DRL Gröbner basis modulo p < $2^{16};$ this is 88 faster than Magma (V2-16-1).
Starting Page	89
Ending Page	97
Page Count	9
File Format	PDF
ISBN	9781450300674
DOI	10.1145/1837210.1837225
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Gröbner bases Polynomial systems solving Gaussian elimination Multi-core programming High performance linear algebra Cryptography
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

GBLA: Gröbner Basis Linear Algebra Package

Performance study of matrix computations using multi-core programming tools

Computational Comparison of Some Multi-core Programming Tools for Basic Matrix Computations

Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology

Solving multivariate polynomial systems and an invariant from commutative algebra

A Gr\"obner bases methodology for solving multiobjective polynomial integer programs

Hybrid approach for solving multivariate systems over finite fields

On the complexity of computing gröbner bases for quasi-homogeneous systems

Solving polynomial equations for chemical problems using Gröbner bases

Parallel Gaussian elimination for Gröbner bases computations in finite fields

Similar Documents

GBLA: Gröbner Basis Linear Algebra Package

Performance study of matrix computations using multi-core programming tools

Computational Comparison of Some Multi-core Programming Tools for Basic Matrix Computations

Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology

Solving multivariate polynomial systems and an invariant from commutative algebra

A Gr\"obner bases methodology for solving multiobjective polynomial integer programs

Hybrid approach for solving multivariate systems over finite fields

On the complexity of computing gröbner bases for quasi-homogeneous systems

Solving polynomial equations for chemical problems using Gröbner bases

Parallel Gaussian elimination for Gröbner bases computations in finite fields