Solving Thousand Digit Frobenius Problems Using Grobner Bases
Journal of Symbolic Computation (January 2008), volume 43, issue 1
[PDF, PostScript, arXiv, ScienceDirect, BibTeX] download benchmark data
Abstract: A Grobner basis-based algorithm for solving the Frobenius Instance Problem is presented, and this leads to an algorithm for solving the Frobenius Problem that can handle numbers with thousands of digits. Connections to irreducible decompositions and Hilbert functions are also presented.
The Slice Algorithm For Irreducible Decomposition of Monomial Ideals
Journal of Symbolic Computation (April 2009), volume 44, issue 4
[PDF, arXiv, ScienceDirect, BibTeX] download benchmark data
Abstract: Irreducible decomposition of monomial ideals has an increasing number of applications from biology to pure math. This paper presents the Slice Algorithm for computing irreducible decompositions, Alexander duals and socles of monomial ideals. The paper includes experiments showing good performance in practice.
A Slice Algorithm for Corners and Hilbert-Poincaré series of monomial ideals
Proceedings of the 2010 international symposium on Symbolic and algebraic computation
[PDF, ACM Digital Library, BibTeX]
Abstract: We present an algorithm for computing the corners of a monomial ideal. The corners are a set of multidegrees that support the numerical information of a monomial ideal such as Betti numbers and Hilbert-Poincaré series. We show an experiment using corners to compute Hilbert-Poincaré series of monomial ideals with favorable results.
Practical Groebner Basis Computation
Joint work with Michael Stillman.
Abstract: We report on our experiences exploring state of the art Grobner basis computation. We investigate signature based algorithms in detail. We also introduce new practical data structures and computational techniques for use in both signature based Grobner basis algorithms and more traditional variations of the classic Buchberger algorithm. Our conclusions are based on experiments using our new freely available open source standalone C++ library.
Complexity and Algorithms for Euler Characteristic of Simplicial
Joint work with Eduardo Sáenz-de-Cabezón.
Abstract: We consider the problem of computing the Euler characteristic of an abstract simplicial complex given by its vertices and facets. We show that this problem is #P-complete and present two new practical algorithms for computing Euler characteristic. The two new algorithms are derived using combinatorial commutative algebra and we also give a second description of them that requires no algebra. We present experiments showing that the two new algorithms can be implemented to be faster than previous Euler characteristic implementations by a large margin.
Maximal lattice free bodies, test sets and the Frobenius problem
Joint work with Anders Nedergaard Jensen and Niels Lauritzen.
Abstract: Maximal lattice free bodies are maximal polytopes without interior integral points. Scarf initiated the study of maximal lattice free bodies relative to the facet normals in a fixed matrix. In this paper we give an efficient algorithm for computing the maximal lattice free bodies of an integral matrix A. An important ingredient is a test set for a certain integer program associated with A. This test set may be computed using algebraic methods. As an application we generalize the Scarf-Shallcross algorithm for the three-dimensional Frobenius problem to arbitrary dimension. In this context our method is inspired by the novel algorithm by Einstein, Lichtblau, Strzebonski and Wagon and the Groebner basis approach by Roune.
My Danish Bachelor's Thesis on Matroids
An introduction to Matroid theory in danish.