Toric ideals--woo hoo!

It looks like Maple has something relevant to this Graver basis problem after all:

http://www.maplesoft.com/support/help/Maple/view.aspx?path=Groebner/ToricIdealBasis

Now to see if we can get it to actually do something useful.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
>
> It looks like Maple has something relevant to this Graver basis problem after all:
>
> http://www.maplesoft.com/support/help/Maple/view.aspx?path=Groebner/ToricIdealBasis
>
> Now to see if we can get it to actually do something useful.
>

I got it to give a subset of the Graver basis. If Mike or anyone else wants to play with it, here it is:

monocoeff := proc(u, m, n)
# monomial coefficient
local i, y;
y := u;
for i from 1 to n do
if not i=m then y := subs(x[i]=1, y) fi od;
coeff(y, x[m], degree(y, x[m])) end:

monocon := proc(u, n)
# monomial conversion
local i, j, z;
z := NULL;
for i from 1 to n do
z := z,signum(0, monocoeff(u, i, n), 0)*degree(u, x[i]) od;
[z] end:

toric := proc(w)
local M, g, i, n, u, y, z;
n := nops(w[1]);
M := Matrix(w);
z := [seq(x[i], i=1..n)];
g := Groebner[ToricIdealBasis](M, z, plex(op(z)), method='du');
z := NULL;
for i to nops(g) do
z := z, monocon(g[i],n) od;
z := monzl2rat([z]);
y := NULL;
for i from 1 to nops(z) do
u := z[i];
if u<1 then u:=1/u fi;
y := y, u od:
tensort([y]) end:

monz2rat := proc(m)
# converts monzo to rational number
local i, t;
t := 1;
for i from 1 to nops(m) do
t := t * ithprime(i)^m[i] od;
t end:

monzl2rat := proc(w)
# list of monzos to list of rationals
local i, u;
u := NULL;
for i from 1 to nops(w) do
u := u,monz2rat(w[i]) od;
[u] end:

tenney := proc(q)
# tenney height of q
numer(q)*denom(q) end:

tensort := proc(l)
# tenney height sorting of list l;
local i, j, n, u, v, w;
u := map(tenney, l);
v := sort(u);
n := nops(u);
w := NULL;
for i from 1 to n do
for j from 1 to n do
if v[i]=u[j] then
w := w,l[j] fi od od;
[w] end:

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
I've got an alternative to "redic" coded up, but I wish it was faster. But at least now I have an alternative when "redic" craps out on me.

I still don't really get it - how does this help us find the point in an
affine subspace with the least L1 norm?

-Mike

On Jun 8, 2012, at 6:06 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...>
wrote:
I've got an alternative to "redic" coded up, but I wish it was faster. But
at least now I have an alternative when "redic" craps out on me.

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> I still don't really get it - how does this help us find the point in an
> affine subspace with the least L1 norm?

Once you find a Graver basis for the commas of a temperament, you can multiply or divide your interval by an element of the Graver basis to see if the Tenney height goes down. Lather, rise, repeat. Of course you can do that anyway, but without the full Graver basis you might get stuck.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
>
>
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@> wrote:
> >
> > I still don't really get it - how does this help us find the point in an
> > affine subspace with the least L1 norm?
>
> Once you find a Graver basis for the commas of a temperament, you can multiply or divide your interval by an element of the Graver basis to see if the Tenney height goes down. Lather, rise, repeat. Of course you can do that anyway, but without the full Graver basis you might get stuck.

In that connection, I'll be experimenting with using what might be called the totic basis--the basis given by Maple's Groebner[ToricIdealBasis](M, z, plex(op(z)), method='du'). That is very fast to compute.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
>
>
>
> --- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@> wrote:
> >
> >
> >
> > --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@> wrote:
> > >
> > > I still don't really get it - how does this help us find the point in an
> > > affine subspace with the least L1 norm?
> >
> > Once you find a Graver basis for the commas of a temperament, you can multiply or divide your interval by an element of the Graver basis to see if the Tenney height goes down. Lather, rise, repeat. Of course you can do that anyway, but without the full Graver basis you might get stuck.
>
> In that connection, I'll be experimenting with using what might be called the totic basis--the basis given by Maple's Groebner[ToricIdealBasis](M, z, plex(op(z)), method='du'). That is very fast to compute.
>

The combination of Mike's algorithm and the toric basis seems to work fine in practice if anyone, such as Mike, wants it.

On Fri, Jun 8, 2012 at 11:51 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...>
> wrote:
> >
> > I still don't really get it - how does this help us find the point in an
> > affine subspace with the least L1 norm?
>
> Once you find a Graver basis for the commas of a temperament, you can
> multiply or divide your interval by an element of the Graver basis to see if
> the Tenney height goes down. Lather, rise, repeat. Of course you can do that
> anyway, but without the full Graver basis you might get stuck.

Do you do it in order or something? As in, first you minimize L1
distance by altering by one member of the basis, then when that's
minimized you move onto the next one, and so on until you're done, and
then you're guaranteed to minimize L1 distance overall?

-Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> Do you do it in order or something? As in, first you minimize L1
> distance by altering by one member of the basis, then when that's
> minimized you move onto the next one, and so on until you're done, and
> then you're guaranteed to minimize L1 distance overall?

I do it in order of increasing complexity but that should not matter.