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

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

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

Content Provider	ACM Digital Library
Author	Guo, Feng Zhi, Lihong Kaltofen, Erich L.
Abstract	We deploy numerical semidefinite programming and conversion to exact rational inequalities to certify that for a positive semidefinite input polynomial or rational function, any representation as a fraction of sums-of-squares of polynomials with real coefficients must contain polynomials in the denominator of degree no less than a given input lower bound. By Artin's solution to Hilbert's 17th problems, such representations always exist for some denominator degree. Our certificates of infeasibility are based on the generalization of Farkas's Lemma to semidefinite programming. The literature has many famous examples of impossibility of SOS representability including Motzkin's, Robinson's, Choi's and Lam's polynomials, and Reznick's lower degree bounds on uniform denominators, e.g., powers of the sum-of-squares of each variable. Our work on exact certificates for positive semidefiniteness allows for non-uniform denominators, which can have lower degree and are often easier to convert to exact identities. Here we demonstrate our algorithm by computing certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively. We can also certify impossibility of base polynomials in the denominator of restricted term structure, for instance as in Landau's reduction by one less variable.
Starting Page	195
Ending Page	202
Page Count	8
File Format	PDF
ISBN	9781450312691
DOI	10.1145/2442829.2442859
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Certificates of infeasibility of semidefinite programs Exact solution to semidefinite programs Sum-of-squares denominators in artin's theorem for definite polynomials Farkas lemma in semidefinite programming
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