On Thu, Jul 16, 2009 at 9:20 AM, Bjarke Hammersholt Roune<bjarke.ro...@gmail.com> wrote: > > Frobby is currently an optional component of Sage, which performs > computations related to monomial ideals. In particular, it can compute > > * Multigraded Hilbert series > * Alexander dual of monomial ideals > * Maximal standard monomials of monomial ideals > * Irreducible decomposition of monomial ideals > * Optimization of any linear function over the maximal standard > monomials of a monomial ideal using branch-and-bound. > > Sage currently is not able to do any of this. Sage does have the less > general (1,..., 1)-graded Hilbert series using Singular, but it > doesn't support arbitrarily large exponents as Frobby does. > > Applications of the last item above include Frobenius numbers for > instances with very large numbers (with 4ti2), as demonstrated at Sage > Days 16, and described in (1) below. Another application is the > integer programming gap (also with 4ti2) of a matrix where the right- > hand-side is allowed to vary as described in (2). > > This is put up for a vote now since I wrote a cython interface to > Frobby at Sage Day 16, and I'm told this requires Frobby to be a > standard component of Sage.
+1 > > Frobby is fastest at items 2-4 listed above as documented in (3) > below, by factors of up to 1000x, with the exception of specially- > constructed inputs (in particular taking the dual of a dual to recover > the original ideal). Item 1 is Hilbert series, where CoCoALib might be > faster right now, since the algorithm I use is for now unpublished, > and I haven't compared it to CoCoALib yet. In any case I will also > implement the Bigatt et.al. algorithm that CoCoALib uses, though this > is not done yet. > > Frobby has an extensive test-suite, which includes running Frobby > under valgrind to detect memory leaks, and is supported for Mac OS > 10.5, Linux and Cygwin. It compiles using MS Visual Studio Express, > though I haven't tested it on that platform since I couldn't get GMP > to build on Windows. GMP is the only dependency Frobby has other than > a C++ compiler. The build system is make-based. I am the upstream > contact, and Frobby is licensed as GPL version 2.0 or later. > > Cheers > Bjarke Hammersholt Roune > www.broune.com > > (1) Bjarke H. Roune, Solving Thousand Digit Frobenius Problems Using > Grobner Bases > Journal of Symbolic Computation (January 2008), volume 43, issue 1 > See http://www.broune.com/papers/index.html > > (2) Hocsten, S., Sturmfels, B., 2007. Computing the integer > programming gap. > Combinatorica 27 (3). > See http://arxiv.org/abs/arXiv:math/0301266 > > (3) Bjarke H. Roune, The Slice Algorithm For Irreducible Decomposition > of Monomial Ideals > Journal of Symbolic Computation (April 2009), volume 44, issue 4 > See http://www.broune.com/papers/index.html > > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
