NDLI: Sub-cubic change of ordering for Gröbner basis: a probabilistic approach

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

Mathematics by machine

Effective quantifier elimination for industrial applications

Sparse interpolation over finite fields via low-order roots of unity

Fuzzy simplification of non-numeric expressions containing some intervals and/or floating point numbers

How to develop a mobile computer algebra system

Multivariate sparse interpolation using randomized Kronecker substitutions

Maximum likelihood for matrices with rank constraints

Introduction to max-plus algebra

Computing the differential Galois group of a parameterized second-order linear differential equation

Algebraic complexity theory and matrix multiplication

A new deterministic algorithm for sparse multivariate polynomial interpolation

Gröbner bases of toric ideals and their application

A fast algorithm for computing the characteristic polynomial of the p-curvature

Symbolic-numeric algorithms for computing validated results

Computing necessary integrability conditions for planar parametrized homogeneous potentials

Improved algorithm for computing separating linear forms for bivariate systems

Solving higher order linear differential equations having elliptic function coefficients

Quantifier elimination by cylindrical algebraic decomposition based on regular chains

Parallel telescoping and parameterized Picard-Vessiot theory

A generalized Apagodu-Zeilberger algorithm

The asymptotic analysis of some interpolated nonlinear recurrence relations

Fast arithmetic for the algebraic closure of finite fields

On the computation of the topology of plane curves

Logspace computations in graph products

Essentially optimal interactive certificates in linear algebra

Root counts of semi-mixed systems, and an application to counting nash equilibria

Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation)

Sub-cubic change of ordering for Gröbner basis: a probabilistic approach

Sparse Gröbner bases: the unmixed case

The MMO problem

Factoring linear differential operators in n variables

Online order basis algorithm and its impact on the block Wiedemann algorithm

On isomorphisms of modules over non-commutative PID

Radical solutions of first order autonomous algebraic ordinary differential equations

Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach

Maximum likelihood geometry in the presence of data zeros

Constructing fewer open cells by GCD computation in CAD projection

An a posteriori certification algorithm for Newton homotopies

Evaluating parametric holonomic sequences using rectangular splitting

Equivariant lattice generators and Markov bases

Sparse polynomial interpolation codes and their decoding beyond half the minimum distance

Sparse multivariate function recovery with a high error rate in the evaluations

Bounds for D-finite closure properties

Powers of tensors and fast matrix multiplication

Reduction among bracket polynomials

Formal solutions of a class of Pfaffian systems in two variables

On the reduction of singularly-perturbed linear differential systems

High performance implementation of the TFT

Randomized detection of extraneous factors

Toric border basis

On efficient algorithms for computing parametric local cohomology classes associated with semi-quasihomogeneous singularities and standard bases

A near-optimal algorithm for computing real roots of sparse polynomials

LLL reducing with the most significant bits

Covering of surfaces parametrized without projective base points

Linear independence oracles and applications to rectangular and low rank linear systems

Cylindrical algebraic decomposition using local projections

Matrix-F5 algorithms over finite-precision complete discrete valuation fields

Faster relaxed multiplication

Unimodular completion of polynomial matrices

Tame decompositions and collisions

Sub-cubic change of ordering for Gröbner basis: a probabilistic approach

Content Provider	ACM Digital Library
Author	Gaudry, Pierrick Renault, Guénaël Faugère, Jean-Charles Huot, Louise
Abstract	The usual algorithm to solve polynomial systems using Gröbner bases consists of two steps: first computing the DRL Gröbner basis using the $F_{5}$ algorithm then computing the LEX Gröbner basis using a change of ordering algorithm. When the Bézout bound is reached, the bottleneck of the total solving process is the change of ordering step. For 20 years, thanks to the FGLM algorithm the complexity of change of ordering is known to be cubic in the number of solutions of the system to solve. We show that, in the generic case or up to a generic linear change of variables, the multiplicative structure of the quotient ring can be computed with no arithmetic operation. Moreover, given this multiplicative structure we propose a change of ordering algorithm for Shape Position ideals whose complexity is polynomial in the number of solutions with exponent ω where 2 ≤ ω < 2.3727 is the exponent in the complexity of multiplying two dense matrices. As a consequence, we propose a new Las Vegas algorithm for solving polynomial systems with a finite number of solutions by using Gröbner basis for which the change of ordering step has a sub-cubic (i.e. with exponent ω) complexity and whose total complexity is dominated by the complexity of the $F_{5}$ algorithm. In practice we obtain significant speedups for various polynomial systems by a factor up to 1500 for specific cases and we are now able to tackle some instances that were intractable.
Starting Page	170
Ending Page	177
Page Count	8
File Format	PDF
ISBN	9781450325011
DOI	10.1145/2608628.2608669
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Change of ordering Gröbner basis Polynomial systems
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

A new algorithm for computing comprehensive Gröbner systems

Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm

Synthesis of multidimensional control systems by Gröbner basis approach

Incomplete Gröbner basis as a preconditioner for polynomial systems

Degree bounds for Gröbner bases of low-dimensional polynomial ideals

Criteria for Finite Difference Gröbner Bases of Normal Binomial Difference Ideals

An Algorithm to Check Whether a Basis of a Parametric Polynomial System is a Comprehensive Gröbner Basis and the Associated Completion Algorithm

A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras

Changing the ordering of Gröbner bases with LLL: case of two variables

Sub-cubic change of ordering for Gröbner basis: a probabilistic approach

Similar Documents

A new algorithm for computing comprehensive Gröbner systems

Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm

Synthesis of multidimensional control systems by Gröbner basis approach

Incomplete Gröbner basis as a preconditioner for polynomial systems

Degree bounds for Gröbner bases of low-dimensional polynomial ideals

Criteria for Finite Difference Gröbner Bases of Normal Binomial Difference Ideals

An Algorithm to Check Whether a Basis of a Parametric Polynomial System is a Comprehensive Gröbner Basis and the Associated Completion Algorithm

A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras

Changing the ordering of Gröbner bases with LLL: case of two variables

Sub-cubic change of ordering for Gröbner basis: a probabilistic approach