Journal
JOURNAL OF SYMBOLIC COMPUTATION
Volume 68, Issue -, Pages 87-108Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.jsc.2014.09.005
Keywords
Involutive bases; Quasi-stable ideals
Funding
- PRIN
- MIUR [201047ARA_009]
Ask authors/readers for more resources
In this paper, we consider a monomial ideal J (sic) P := A[chi(1), . . . , chi(n)], over a commutative ring A, and we face the problem of the characterization for the family Mf (J) of all homogeneous ideals I (sic) P such that the A-module P/I is free with basis given by the set of terms in the Grinner escalier N(J) of J. This family is in general wider than that of the ideals having J as initial ideal w.r.t. any term-ordering, hence more suited to a computational approach to the study of Hilbert schemes. For this purpose, we exploit and enhance the concepts of multiplicative variables, complete sets and involutive bases introduced by Riquier (1893, 1899, 1910) and in Janet (1920, 1924, 1927) and we generalize the construction of J-marked bases and term-ordering free reduction process introduced and deeply studied in Bertone et al. (2013a), Cioffi and Roggero (2011) for the special case of a strongly stable monomial ideal J. Here, we introduce and characterize for every monomial ideal J a particular complete set of generators.F(J), called stably complete, that allows an explicit description of the family Mf (J). We obtain stronger results if J is quasi-stable, proving that F(J) is a Pommaret basis and Mf (J) has a natural structure of affine scheme. The final section presents a detailed analysis of the origin and the historical evolution of the main notions we refer to. (C) 2014 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
Article
Computer Science, Theory & Methods
Sum-of-squares certificates for Vizing's conjecture via determining Grobner bases
Elisabeth Gaar, Melanie Siebenhofer
Summary: The open Vizing conjecture states that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recent research reformulated this conjecture using the graph class g and introduced the concept of SOS-certificates. By solving semidefinite programs (SDPs) and applying clever guessing, they obtained SOS-certificates for specific cases. In this paper, we consider their approach for a specific case and derive the unique reduced Grobner basis of the Vizing ideal, which leads to the minimum degree of an SOS-certificate. We also propose a method to find certificates for general cases, which relies on solving smaller SDPs and does not require guessing. We provide new SOS-certificates for various graph classes using our implemented method in SageMath.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
A pseudo-polynomial algorithm for the Frobenius number and Grobner basis
Marcel Morales, Nguyen Thi Dung
Summary: The aim of this paper is to provide an effective pseudopolynomial algorithm on a1, which computes the Apery set and the Frobenius number of S. We also find the Grobner basis of the toric ideal defined by S without using Buchberger's algorithm. As an application, special classes of semigroups generated by generalized arithmetic progressions and generalized almost arithmetic progressions are introduced and studied.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
SAGBI combinatorics of maximal minors and a SAGBI algorithm
Winfried Bruns, Aldo Conca
Summary: The maximal minors of a matrix of indeterminates are a universal Grobner basis according to a theorem by Bernstein, Sturmfels, and Zelevinsky. However, they are not always a universal SAGBI basis. Experimental findings on their behavior under varying monomial orders and their extension to SAGBI bases have motivated the development of a new implementation of the SAGBI algorithm using a Singular script and Normaliz for combinatorial computations. Compared to other packages, it significantly expands the range of computability.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Computing roadmaps in unbounded smooth real algebraic sets I: Connectivity results
Remi Prebet, Mohab Safey El Din, Eric Schost
Summary: This paper presents a fundamental problem in effective real algebraic geometry, which is answering connectivity queries in real algebraic sets. This problem has many applications in robotics, particularly in motion planning. The problem is solved by computing roadmaps, which are real algebraic subsets of the set under study, with dimension at most one and a connected intersection with all semi-algebraically connected components. The algorithms for computing roadmaps rely on connectivity properties of selected subsets, assuming boundedness of the set. The paper extends these connectivity statements by removing the boundedness assumption and utilizing generalized polar varieties.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Hirota varieties and rational nodal curves
Claudia Fevola, Yelena Mandelshtam
Summary: In this work, the Hirota variety arising from a rational nodal curve is studied, with a specific focus on its irreducible subvariety called the main component. Proving this to be an irreducible component corresponds to solving a weak Schottky problem for rational nodal curves. Computational tools are used to solve this problem up to genus nine.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
The Smith normal form and reduction of weakly linear matrices
Jinwang Liu, Dongmei Li, Tao Wu
Summary: This paper investigates the reduction of weakly linear multivariate polynomial matrices to their Smith normal forms, using hierarchical-recursive method and Quillen-Suslin Theorem. The necessary and sufficient conditions for such matrices to be reduced to their Smith normal forms are derived, which can be easily checked by computing the reduced Grobner bases of the relevant polynomial ideals. Based on the new results, an algorithm for reducing weakly linear multivariate polynomial matrices to their Smith normal forms is proposed.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
The span of singular tuples of a tensor beyond the boundary format
Luca Sodomaco, Ettore Teixeira Turatti
Summary: This paper studies the linear span of singular k-tuples of a specific format tensor and proves that the dimension of this linear span is stable in certain formats.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Voronoi diagrams of algebraic varieties under polyhedral norms
Adrian Becedas, Kathlen Kohn, Lorenzo Venturello
Summary: We study Voronoi diagrams with respect to polyhedral norms for manifolds and varieties. Upper and lower bounds on the dimensions of Voronoi cells are provided. We also examine the full-dimensional Voronoi cells for algebraic varieties. As an application, the polyhedral Wasserstein distance between discrete probability distributions is considered.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
Ilias Kotsireas, Toufik Mansour, Gokhan Yildirim
Summary: We introduce an algorithmic approach based on a generating tree method for enumerating the inversion sequences with various pattern-avoidance restrictions. The algorithm outputs either an accurate description of the succession rules of the generating tree or an ansatz for a given set of patterns. We determine the generating trees for several pattern classes and obtain generating functions and enumerating formulas using the kernel method.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
On cyclic codes over Zq[u]/(u2) and their enumeration
Fatih Temiz, Irfan Siap
Summary: In this study, the structure of cyclic codes over the ring Zq[u]/(u2) which is isomorphic to R = Zq + uZq is determined. The algebraic structure of ideals of the polynomial quotient ring R[x]/(xn - 1) is completely addressed, and an exact formula that enumerates the number of ideals of this ring is presented. Furthermore, the size of some special families of cyclic codes for specific q is determined.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Critical configurations for two projective views, a new approach
Martin Bratelund
Summary: This article develops new techniques to classify critical configurations for 3D scene reconstruction from images taken by unknown cameras. The paper uses an algebraic approach to study the critical configurations for two projective cameras and shows that all critical configurations lie on quadric surfaces. It also describes the relationship between different reconstructions when unique reconstruction is impossible.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Toric geometry of entropic regularization
Bernd Sturmfels, Simon Telen, Francois-Xavier Vialard, Max von Renesse
Summary: Entropic regularization is a method used for large-scale linear programming. It involves tracing the intersections of the feasible polytope with scaled toric varieties, starting from the Birch point. This method is compared to log-barrier methods that use reciprocal linear spaces starting from the analytic center. The paper also explores the use of optimal conic couplings and algorithms like iterative scaling in this context.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Computing tropical bitangents to smooth quartic curves in polymake
Alheydis Geiger, Marta Panizzut
Summary: In this article, the recently developed Polymake extension TropicalQuarticCurves and its associated database entry in polyDB dealing with smooth tropical quartic curves are introduced. The algorithms implemented to analyze tropical bitangents and their lifting conditions over real closed valued fields are reported. The authors used the new functions and data to provide a tropical proof of Plucker and Zeuthen's count of real bitangents to smooth quartic curves.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
A counterexample to a conjecture on simultaneous Waring identifiability
Elena Angelini
Summary: Based on the research of Angelini et al. (2018) and the recent analysis on simultaneous identifiability of pairs of ternary forms by Beorchia and Galuppi (2022), a conjecture was proposed towards a complete classification of all simultaneous Waring identifiable cases: for any d >= 2, the general polynomial vectors consisting of d -1 ternary forms of degree d and a ternary form of degree d + 1, with rank d2+d+2 2 , are identifiable over C. This paper obtains, through a computer-aided procedure inspired by Angelini et al. (2018), that the case d = 4 contradicts the previous conjecture, admitting at least 36 complex simultaneous Waring decompositions (of length 11) instead of 1.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Article
Computer Science, Theory & Methods
Syzygies, constant rank, and beyond
Marc Haerkoenen, Lisa Nicklasson, Bogdan Raita
Summary: We study linear PDE with constant coefficients and investigate the connection between the constant rank condition and primary decomposition. We also make progress in the study of weak lower semicontinuity of integral functionals defined on sequences of PDE constrained fields when the PDEs do not have constant rank.
JOURNAL OF SYMBOLIC COMPUTATION (2024)
Share Paper
