Hermite reduction vs LLL reduction vs "TM" reduction

I saw Graham put this here:

On Tue, Jan 10, 2012 at 5:56 PM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> That's the one. I didn't understand the definitions of Hermite normal form but it turns out I implemented it anyway.

I've since finally gotten my hands on a bonafide Hermite normal form
algorithm, and the thing given by the "reduced" mapping in the
temperament finder doesn't seem to be it. For example, the Hermite
normal form for meantone is |<1 0 -4| <0 1 4|>, with a generator of
3/1, whereas the one on your site is 4/3. But it's definitely
interesting, whatever it is. What is it?

The form I prefer for mappings is the one that expresses meantone as
|<1 1 0| <0 1 4|>. That is, I like the one in which the vals are as
close to the zero vector as possible. This is another way of saying
that what I really want is a "basis" for the lattice formed by the
vals which is in a sense "minimal." The reason I like this is because
it makes the mental work of interpreting the mapping as little as
possible: there's less mental arithmetic that you need to perform to
figure out what's going on if the numbers involved are as small as
possible. So what sort of form is this?

I thought it might be LLL, but it's not. LLL is |<-1 -1 0| <1 0 -4|>.
I see there's something in the archives called "TM Reduction", which
is apparently really Minkowski reduction, but I can't figure out what
that is. Is this related to that?

-Mike

On Fri, Jan 20, 2012 at 4:34 AM, Mike Battaglia <battaglia01@gmail.com> wrote:
>
> I thought it might be LLL, but it's not. LLL is |<-1 -1 0| <1 0 -4|>.
> I see there's something in the archives called "TM Reduction", which
> is apparently really Minkowski reduction, but I can't figure out what
> that is. Is this related to that?

It looks like what I want is something like Minkowski reduction, with
the basis vectors then stuffed into a matrix and sorted so that it's
upper triangular. But neither MATLAB nor Maple seems to have Minkowski
reduction in it, which I assume is because this is a major pain in the
ass to compute. Is that right?

-Mike

The reduced mapping isn't hermite for rank two. You get the smallest positive generator instead.
TM reduction is the smallest basis according to Tenney weighting.
Cangwu reduction would be interesting. For mapping space, you'd get the best linearly independent equal temperaments. It's a unimodular matrix. The inverse is a set of potential unison vectors.

----------
Sent from my Nokia phone

------Original message------
From: Mike Battaglia <battaglia01@gmail.com>
To: <tuning-math@yahoogroups.com>
Date: Friday, January 20, 2012 4:34:53 AM GMT-0500
Subject: [tuning-math] Hermite reduction vs LLL reduction vs "TM" reduction

I saw Graham put this here:

On Tue, Jan 10, 2012 at 5:56 PM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> That's the one. I didn't understand the definitions of Hermite normal form but it turns out I implemented it anyway.

I've since finally gotten my hands on a bonafide Hermite normal form
algorithm, and the thing given by the "reduced" mapping in the
temperament finder doesn't seem to be it. For example, the Hermite
normal form for meantone is |<1 0 -4| <0 1 4|>, with a generator of
3/1, whereas the one on your site is 4/3. But it's definitely
interesting, whatever it is. What is it?

The form I prefer for mappings is the one that expresses meantone as
|<1 1 0| <0 1 4|>. That is, I like the one in which the vals are as
close to the zero vector as possible. This is another way of saying
that what I really want is a "basis" for the lattice formed by the
vals which is in a sense "minimal." The reason I like this is because
it makes the mental work of interpreting the mapping as little as
possible: there's less mental arithmetic that you need to perform to
figure out what's going on if the numbers involved are as small as
possible. So what sort of form is this?

I thought it might be LLL, but it's not. LLL is |<-1 -1 0| <1 0 -4|>.
I see there's something in the archives called "TM Reduction", which
is apparently really Minkowski reduction, but I can't figure out what
that is. Is this related to that?

-Mike

------------------------------------

Yahoo! Groups Links

On Fri, Jan 20, 2012 at 9:51 AM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> The reduced mapping isn't hermite for rank two. You get the smallest positive generator instead.

Do you figure this out by going to Hermite form first, and then
performing row operations until you're happy?

> TM reduction is the smallest basis according to Tenney weighting.
> Cangwu reduction would be interesting. For mapping space, you'd get the best linearly independent equal temperaments. It's a unimodular matrix. The inverse is a set of potential unison vectors.

I thought that only square matrices can be unimodular?

-Mike

It's fairly easy to get the period/generator mapping for rank two. One method involves the extended euclidean algorithm.
Reduce the identity matrix according to cangwu badness and you'll get a square matrix.

----------
Sent from my Nokia phone

------Original message------
From: Mike Battaglia <battaglia01@gmail.com>
To: <tuning-math@yahoogroups.com>
Date: Friday, January 20, 2012 3:34:10 PM GMT-0500
Subject: Re: [tuning-math] Hermite reduction vs LLL reduction vs "TM" reduction

On Fri, Jan 20, 2012 at 9:51 AM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> The reduced mapping isn't hermite for rank two. You get the smallest positive generator instead.

Do you figure this out by going to Hermite form first, and then
performing row operations until you're happy?

> TM reduction is the smallest basis according to Tenney weighting.
> Cangwu reduction would be interesting. For mapping space, you'd get the best linearly independent equal temperaments. It's a unimodular matrix. The inverse is a set of potential unison vectors.

I thought that only square matrices can be unimodular?

-Mike

------------------------------------

Yahoo! Groups Links

On Fri, Jan 20, 2012 at 4:07 PM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> It's fairly easy to get the period/generator mapping for rank two. One method involves the extended euclidean algorithm.
> Reduce the identity matrix according to cangwu badness and you'll get a square matrix.

Alright, I'll rephrase. The set of all matrices that share the same
Hermite normal form is a group under addition. I want to find the
matrix in this group with the lowest Frobenius distance; that is, the
one in which the sum of the squares of the coefficients in the matrix
is as small as possible, under the constraint that the rows remain
linearly independent (so no zero vals). Is there a name for this type
of lattice reduction?

Also, the way I've phrased the question above has transformed this
into a least squares problem, so it can't be impossibly hard to
compute.

-Mike

Unfortunately no lattice reduction is easy to compute in the general case. LLL is good and tries to do what you say. But it falls short for reasons of practicality. I believe Minkowski is the ideal equivalent. Simple to define but hard to calculate.

----------
Sent from my Nokia phone

------Original message------
From: Mike Battaglia <battaglia01@gmail.com>
To: <tuning-math@yahoogroups.com>
Date: Friday, January 20, 2012 5:23:43 PM GMT-0500
Subject: Re: Re: [tuning-math] Hermite reduction vs LLL reduction vs "TM" reduction

On Fri, Jan 20, 2012 at 4:07 PM, gbreed@gmail.com <gbreed@gmail.com> wrote:
>
> It's fairly easy to get the period/generator mapping for rank two. One method involves the extended euclidean algorithm.
> Reduce the identity matrix according to cangwu badness and you'll get a square matrix.

Alright, I'll rephrase. The set of all matrices that share the same
Hermite normal form is a group under addition. I want to find the
matrix in this group with the lowest Frobenius distance; that is, the
one in which the sum of the squares of the coefficients in the matrix
is as small as possible, under the constraint that the rows remain
linearly independent (so no zero vals). Is there a name for this type
of lattice reduction?

Also, the way I've phrased the question above has transformed this
into a least squares problem, so it can't be impossibly hard to
compute.

-Mike

------------------------------------

Yahoo! Groups Links