NDLI: Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

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

A-hypergeometric functions: computational aspects

Complexity of deciding connectivity in real algebraic sets: recent results and future research directions

Asymptotic spectrum and matrix multiplication

Upper bounds on real roots and lower bounds for the permanent

Elements of computer-algebraic analysis

Algebraic statistics

On valuations of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients

Computing Puiseux series for algebraic surfaces

The M4RIE library for dense linear algebra over small fields with even characteristic

A root isolation algorithm for sparse univariate polynomials

Computing closed form solutions of integrable connections

Solving linear ordinary differential systems in hyperexponential extensions

Relaxed p-adic Hensel lifting for algebraic systems

Solving polynomial systems over finite fields: improved analysis of the hybrid approach

A polynomial time algorithm for computing the HNF of a module over the integers of a number field

Parallel sparse polynomial multiplication on modern hardware architectures

Compositions and collisions at degree $p^{2}$

Fast computation of common left multiples of linear ordinary differential operators

Power series solutions of singular (q)-differential equations

On the complexity of solving initial value problems

Order-degree curves for hypergeometric creative telescoping

Telescopers for rational and algebraic functions via residues

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

Fast computation of Smith forms of sparse matrices over local rings

On the complexity of solving a bivariate polynomial system

Critical points and Gröbner bases: the unmixed case

Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

Twisting q-holonomic sequences by complex roots of unity

Improving the accuracy of linear programming solvers with iterative refinement

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Practical Gröbner basis computation

On the complexity of multivariate blockwise polynomial multiplication

Rational invariants of scalings from Hermite normal forms

Zeilberger's holonomic ansatz for Pfaffians

Algorithms for the universal decomposition algebra

An efficient implementation of the algorithm computing the Borel-fixed points of a Hilbert scheme

Computing real solutions of polynomial systems via low-rank moment matrix completion

Small homogeneous quandles

Border basis representation of a general quotient algebra

An algorithm to compute the differential equations for the logarithm of a polynomial

Deterministic unimodularity certification

Programming before theorizing, a case study

When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

Effective de Rham cohomology: the hypersurface case

Construction of 2-closed M-representations

Near optimal tree size bounds on a simple real root isolation algorithm

An efficient programming model for memory-intensive recursive algorithms using parallel disks

Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas

Univariate real root isolation in multiple extension fields

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

Factorization of differential operators with ordinary differential polynomial coefficients

Computing minimal nullspace bases

Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

Content Provider	ACM Digital Library
Author	Svartz, Jules Faugère, Jean-Charles
Abstract	We propose an efficient algorithm to solve polynomial systems of which equations are globally invariant under an action of the symmetric group $G_{N}$ acting on the variable $x_{i}$ with $σ(x_{i})$ = $x_{σ(i)}$ and the number of variables is a multiple of N. For instance, we can assume that swapping two variables (or two pairs of variables) in one equation gives rise to another equation of the system (perhaps changing the sign). The idea is to apply many times divided difference operators to the original system in order to obtain a new system of equations involving only the symmetric functions of a subset of the variables. The next step is to solve the system using Gröbner techniques; this is usually several order faster than computing the Gröbner basis of the original system since the number of solutions of the corresponding ideal, which is always finite has been divided by at least N!. To illustrate the algorithm and to demonstrate its efficiency, we apply the method to a well known physical problem called equilibria positions of vortices. This problem has been studied for almost 150 years and goes back to works by von Helmholtz and Lord Kelvin. Assuming that all vortices have same vorticity, the problem can be reformulated as a system of polynomial equations invariant under an action of $G_{N}.$ Using numerical methods, physicists have been able to compute solutions up to N ≤ 7 but it was an open challenge to check whether the set of solution is complete. Direct naive approach of Gröbner bases techniques give rise to hard-to-solve polynomial system: for instance, when N = 5, it takes several days to compute the Gröbner basis and the number of solutions is 2060. By contrast, applying the new algorithm to the same problem gives rise to a system of 17 solutions that can be solved in less than 0.1 sec. Moreover, we are able to compute all equilibria when N ≤ 7.
Starting Page	170
Ending Page	178
Page Count	9
File Format	PDF
ISBN	9781450312691
DOI	10.1145/2442829.2442856
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-22
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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