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
[Paper website]
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
Complexes
[arXiv,
BibTeX]
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
[arXiv,
BibTeX]
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.
The F4 algorithm
[PDF,
Postscript]
An accessible three-page account of Faugere's F4 algorithm, which
speeds up Groebner basis computation using linear algebra.
My Danish Bachelor's Thesis on Matroids
[Postscript]
An introduction to Matroid theory in danish.