Segre-driven radicality testing

DOI10.1016/J.JSC.2023.102262MaRDI QIDQ6184180zbMATH OpenOpenAlexFDO

Authors Martin Helmer, Elias P. Tsigaridas

Publication date 5 January 2024

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.01913

zbMATH Keywords

equidimensional decompositionintersection theoryradical idealsrational univariate representationSegre classtesting if a polynomial ideal is radical

Mathematics Subject Classification ID

Computational aspects and applications of commutative rings (13Pxx) Computational aspects in algebraic geometry (14Qxx) Algorithms in computer science (68Wxx)

Abstract: We present a probabilistic algorithm to test if a homogeneous polynomial ideal $I$ defining a scheme $X$ in $mathbb{P}^n$ is radical using Segre classes and other geometric notions from intersection theory. Its worst case complexity depends on the geometry of $X$. If the scheme $X$ has reduced isolated primary components and no embedded components supported the singular locus of $X_{mred}=V(sqrtI)$, then the worst case complexity is doubly exponential in $n$; in all the other cases the complexity is singly exponential. The realm of the ideals for which our radical testing procedure requires only single exponential time includes examples which are often considered pathological, such as the ones drawn from the famous Mayr-Meyer set of ideals which exhibit doubly exponential complexity for the ideal membership problem.

Cites work

• A concise proof of the Kronecker polynomial system solver from scratch
• A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties
• Algorithm 795
• An algorithm for the computation of the radical of an ideal
• Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Direct methods for primary decomposition
• Effective equidimensional decomposition of affine varieties
• Evaluation techniques for zero-dimensional primary decomposition
• Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
• Generalised characteristic polynomials
• Gröbner bases and primary decomposition of polynomial ideals
• scientific article; zbMATH DE number 3114810 (Why is no real title available?)
• scientific article; zbMATH DE number 4214184 (Why is no real title available?)
• scientific article; zbMATH DE number 16651 (Why is no real title available?)
• scientific article; zbMATH DE number 16653 (Why is no real title available?)
• scientific article; zbMATH DE number 177873 (Why is no real title available?)
• scientific article; zbMATH DE number 1302473 (Why is no real title available?)
• scientific article; zbMATH DE number 1057741 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• scientific article; zbMATH DE number 6154261 (Why is no real title available?)
• Localization and primary decomposition of polynomial ideals
• Modern computer algebra
• On the complexity exponent of polynomial system solving
• On the complexity of computing syzygies
• Probabilistic saturations and Alt's problem
• Software for numerical algebraic geometry: a paradigm and progress towards its implementation
• Solving degenerate sparse polynomial systems faster
• Solving zero-dimensional systems through the rational univariate representation
• Sparse Rational Univariate Representation
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The computational complexity of the Chow form
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science

This page was built for publication: Segre-driven radicality testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184180)