Thursday, July 18, 2013

The Hauptmann Shuffle (1)

This is one of the most well known diagrams in the history of music in the West, the circle of fifths.[1] This diagram has also been augmented (at least since the mid 17th century) by a second circle of fifths inscribed either within the original circle or, as represented in the next illustration, by adding notes (the red dots with lower case labels) between the originals on the same circle:

This has the advantage of showing all 24 major and minor triads and all 24 major and minor diatonic scales. Any three consecutive nodes represent a triad whose root is the first of the three nodes (when moving clockwise), and any seven consecutive nodes can be rearranged to form a diatonic scale. For example, starting with F and proceeding clockwise to D generates the major triads F-a-C (IV, or subdominant triad in C major), C-e-G (I, or tonic triad in C major), and G-b-D (V, or dominant triad in C major) as well as the minor triads in the C-major scale, a-C-e (vi, submediant) and e-G-b (iii, mediant)

To get to the third remaining minor triad in C major, d-F-a (ii, supertonic) as well as the devilish diminished triad b-d-F (using the same logic), we can employ a more modern trick that amounts to the same thing as the often intricate explanatory strategies of older theorists. Looking at the diagram of the double circle of fifths above, think of snipping the circle just below the d on the left and below the D on the right. Then make a new circle  by joining the d and the D (the numbers indicate half-steps between each node):

We could follow several apparently divergent math paths at this point, not the least of which would begin by noting that this representation of the diatonic set is the maximally even 7-in-24, but right now I'd like to draw these well known concepts into the permutation theme. Remember, this is all about discovering deep connections. Just what does the circle of fifths have to do with spirals, sestinas, coils, perfect shuffles, parallel processing? Take a look at the next diagram from the mid 19th century found in Moritz Hauptman's treatise Die Natur der Harmonie und der Metrik (1853).[2]

What Hauptmann is doing here is tracing a path through his "triad of triads" (a linear representation which is essentially the same as the circular representation of the diatonic set above).[3]  Following this nicely symmetric path reveals the step-wise scale version of the set, for example,
Bending a few of Hauptmann's curving lines upward, we can see it this way:

... the most familiar version of the coil permutation – the perfect shuffle. Here it's shuffling a deck of just seven cards/notes. In cyclic notation, this permutation is (F)(aGC)(ebd)[4], so we know that after three shuffles we will come back to the original arrangement:

The first note, F in this example, is the only fixed point and remains in the first position with each shuffle, while the other six notes permute as a perfect in shuffle.

But the most interesting thing to me is that you can get from any one of these three well-known orderings of the 7-note diatonic set to the others by applying just one permutation, the perfect out shuffle or its inverse, the outL pretzel – e.g., (F)(aGC)(ebd) or its inverse (F)(CGa)(dbe). A bonus here is that all three are maximally even sets (4343433 (7-in-24); (2221221 (7-in-12); (7777776 (7-in-48)), but after examining what happens when other maximally even sets are shuffled, it becomes obvious that a perfect shuffle of a maximally even set will not necessarily result in another max even set (try shuffling the octatonic as one counter example).

[1] I am fully aware of the centuries-old controversies concerning tuning problems, but here I will be assuming equal temperament and ignoring just intonation. I am doing this by fiat, not because of any personal preference or because I think ET is "right" and JI is "wrong," but simply to stay on topic to make a point that really has nothing to do with tuning. Tuning theory to one side, even the notes on a badly out-of-tune piano would still have the same underlying abstract relationships being described here, however awful they may sound to the sensitive ear.
[2] This is actually from the 1888 English edition, The Nature of Harmony and Metre, tr. & ed. W.E. Heathcote.
[3] Hauptmann's Roman numerals are not the same as the more familiar chord functions still in use, but explaining them here would take us too far off topic.
[4] If we rotate the circle to start with the scale (deck) arranged CeGbdFa, the result woud be the familiar major scale form CdeFGab and the permutation would be (C)(edG)(bFa), and so on for the other modes (arrangements of the deck).

Wednesday, July 3, 2013

Don't Panic: Parallel processing for intelligent dummies.

Multitasking is a family of four living in a house with one television set.
Parallel processing is a family of four living in a house with four television sets.[1]

The distinction between multitasking and parallel processing is important. But the distinction in humans (if it applies at all) is much more complex than it is in computers. It's imbedded within the knotty questions surrounding "attention."[2] As far as I know, these questions regarding attention for the human mind/brain are far from being settled, and they're a significant part of the subtext in this thread. Fortunately, the case is not (yet) as difficult to understand for the computer as it is for the human.[3]

In contrast to parallel (simultaneity) processing, multitasking is a kind of serial (single time line) processing. But things happen so fast inside a computer that the two are indistinguishable to the user – and are meant to be. So it helps (especially for my purpose here) to slow things down to a sub-computer (human?) speed to watch what's going on. This slowing down, in the example I'm about to give, will reveal the action of the well-known permutation algorithm, the perfect shuffle, presented in the Kevin Houston video I used at the beginning of the "Jeu de Cartes" post.

The following example is a variation on an example taken from a 1971 paper by Harold S. Stone, "Parallel Processing with the Perfect Shuffle." This paper was written at a time when parallel processing was in a relatively early stage of development. It gives four interesting processing applications for the perfect shuffle: the fast Fourier transform[4], polynomial evaluation, sorting, and matrix transposition. The example here will be polynomial evaluation, because the only math needed to understand the action of the perfect shuffle in parallel processing here is multiplication.

In a deck of eight cards labeled 1, 2, 3, 4, 5, 6, 7, 8, the perfect out shuffle looks like this:

The "one-line" notation for this ("coil") permutation is (15263748), and the cyclic notation is
(1)(8)(253)(467). The 1 and 8 are "fixed points" – they don't change in the permutation and so stay on the "outside" after the shuffle, hence the "out" in the designation. 2-5-3 and 4-6-7 cycle through together during consecutive shuffles, indicating that after only three shuffles, an eight-card deck will return to its original order:

Remembering that the objects being permuted need not be the usual consecutive integers, but can be any "objects," we make a substitution mapping all the odd integers 1,3,5,7 to "0" and the even integers 2,4,6,8 to "1".  Leaving off the return permutation, we then have the map:

Now, an "object" in the context here need not be a "noun thing" like a number or an apple or a pitch or a word. It can also be an instruction such as "Do X" or the response to a question such as "Should I do X?" This will be important in a future post.

So we can then treat the perfect shuffle of 0's and 1's as a "mask" or "sieve" so that a "1" tells the computer to do something to a piece of data before letting it pass through to the next step, while a "0" tells the computer to let the datum pass through without doing anything to it.

In the example taken in Stone's paper we want to evaluate a 6th-degree polynomial, which has a formidable look to it

If we were to try this using only our human serial/multi-tasking abilities, or work it on a computer that could only perform SISD (single instruction, single data), we would have to go one step at a time from left to right. The parallel processing suggested by Stone in 1971 feeds all the data in through eight processors simultaneously. At the first stage, each processor asks the mask, "Should I multiply the datum I was given by x?" If the answer is "1" then it multiplies by x and passes the answer on to the next stage. If it's "0" it simply passes on what it was given without doing anything to it. Then the computer shuffles that mask to produce the next mask which answers the question, "Should I multiply by x-squared or not?" Then a final shuffle to answer "Should I multiply by x-to-the-4th or not?"[5]

So if we wanted to evaluate this polynomial for x=2

it would go through in three steps:

Finally, as any Hitchhiker can predict, when you sum all the terms in the end (remember to leave out the 256), the answer will be 42.

Still, there's more to life than 42. The idea to take away from all this is not a more efficient and faster way for a computer to evaluate polynomials, but the idea of permutations of instructions. And that will now lead to some music-world observations about voice leading, neo-Riemannian transformations, and cycles of sonorities in atonal settings – and then moving on to a fantasy on the question, "What did you do in the war, Uncle Miltie?" 


[1] I guess I should add this more technical distinction taken from ComputerUser Dictionary:

In computing, multitasking is a technique used in an operating system for sharing a single processor between several independent jobs. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for that task. Multitasking solves the problem by scheduling which task may be the one running at any given time, and when another waiting task gets a turn. The act of reassigning a CPU from one task to another one is called a context switchWhen context switches occur frequently enough the illusion of parallelism is achieved. Even on computers with more than one CPU, multitasking allows many more tasks to be run than there are CPUs.
Parallel processing:
Parallel processing is a computing architecture within a single computer that performs more than one operation at the same time. Parallel processing can also be achieved by using multiple computers clustered together to process one part of a large function simultaneously to obtain results faster.
[2] Recommended reading: a summary of philosophies of attention can be found in the online Stanford Encyclopedia of Philosophy.
[3] A helpful tutorial on parallel processing is on the Lawrence Livermore National Laboratory web site.
[4] There is a humorous tale of one man's encounter with fast Fourier transforms at John the Math Guy, a blog devoted to a light hearted but informative approach to many topics in math – highly recommended blog.
[5] Why do these particular multipliers in this particular order make this work?
Hint 1: remember from elementary algebra that
Hint 2: read the mask from top to bottom: 000, 100, ..., 111

Monday, July 1, 2013

A Few Notes about Notations

Several days ago I attached a page to this blog tentatively titled "Spiral Set." I say "tentatively" because it's simply a working title referring to the post "The Form" that began this thread on deep connections. The title will likely change to something more accurately descriptive when I consider this set of eight slides is correct and complete (or when someone tells me that this "super-group"/"hyper-group"/? has been named and studied elsewhere, which would save me a lot of work). I decided to publish this nearly complete set now since nomenclature starts to get cumbersome in describing and applying these inter-related permutations in traditionally marginally- or un-related fields. So a word or two here about the eight slides.

Each slide contains four related permutations. Talking through just one of the slides will explain the other seven. I'm using permutations of order 6 (remember the sestina) to illustrate, but the basic set can be of just about any size. I've chosen the "COIL" slide as an example because I'll be moving soon from the "perfect (Faro) shuffle" in cards to its application in computers.

Some readers will already have noticed that at this point I have introduced four parallel notations, i.e., four different ways of describing (or, better, seeing) the same result.

(1) Open continuous paths. At the top of the slide is a diagram [appearing only in the first four slides as of now – I haven't included the other four yet] showing a 2-dimensional continuous path that crosses once through each of the six points on the line (imagine each point labelled consecutively 1 through 6). Begin at one of the "loose ends" of the path, two of which are "outside" ends and two of which are "inside." Thus outL means start following the path at the outside end on the left resulting in the path on the line [142536] ; outR means start at the outside end on the right, [635241]; inR starts the path at the inside right loose end, [415263]; inL begins at the inside left end, [362514].

(2) Comb combinations. All of these permutations (on all eight slides) are based on dividing the basic set in half in one of two ways: Left and Right halves, L={123} R={456}, and Odd and Even halves, O={135} E={246}.[1]  Each of these subsets is then expressed as an ordered set according to whether the integers increase (→: 123, 456, 135, 246) or decrease (←: 321, 654, 531, 642). Finally, the oriented subsets are either INTERLeaved as in this example or CONCATenated (see slide 1, for example) beginning with whichever subset is written first. Thus, INTERL(L→R→) means write 1 2 3 and then, starting after the 1, interleave 4 5 6 yielding the permutation [142536].[2]  CONCAT(L→R→) = [123456] (see slide 6). INTERL(L←R←) = [362514] (slide 2 above). CONCAT(L←R←) = [321654] (slide 6). INTERL(E←O→) = [614325] (slide 7). Etc. for a total of 32 comb combinations. Also note that the four comb combinations on each of the eight slides are related by both a FLIP operation (O↔E or L↔R, the red lines) and a REVerse orientation operation (← ↔ →, the green lines).

The comb notation and all of the operations it suggests might seem at first to be a highly convoluted way of distinguishing this bunch of 32 permutations (technically only 30 because two of them [123456] and [654321] are repeated) out of all possible permutations. But it's helpful to remember that the comb idea generating all these permutations originated with the medieval definition of the sestina form as retrogradatio cruciata. Once you have the acorn, sooner or later the entire oak will appear for you. But there are two more notations left – the more traditional ones from mathematics.

(3) 1-to-1 map (Cauchy two-line notation). This is the simplest way of representing any permutation and is generally used when introducing the concept in elementary math courses.

It means no more than the top row "goes to" the bottom row: 1→1, 2→4, 3→2, etc. This is often abbreviated in "one-line notation" where the consecutive integers in the top row are assumed; all that's needed is to state the outcome, the bottom row (see the double-line enclosed boxes in slide 2 above).

(4) Closed continuous paths (cyclic notation). This is analogous to the open continuous path in that it cycles through the elements in the string being permuted. Whereas the "open path"notation described in (1) leads through the initial string from one end to another (e.g., 1→4→2→5→3→6), occasionally revealing some nice symmetries, cyclic notation creates one or more closed loops. Referring to the previous example in two-line notation, first note that 1 and 6 are "fixed points" in the example – they don't change in the permutation. Next, go to 2 in the top row and follow the path through: 2→4,4→5,5→3,3→2. tracing the closed path 2→4→5→3→(2). In the traditional notation for cyclic notation this would be written: (1)(6)(2453) as it is on slide 2 above. While I have never seen it presented this way, we could present cyclic notation visually in much the same way the open path notation was presented:

Using cyclic notation it becomes easy to determine any permutation's inverse, e.g., having gone from [123456] to [142536], what permutation will immediately take me back to [123456]? The answer is to simply read each cycle backward. So (1) and (6) are unchanged, but (2453) becomes (3542) which, remembering this is cyclic, is the same as (2354) or (4235) or (5423).  But notice that the inverse we are looking for, (1)(6)(3542) is not available on slide 2. It can be found on slide 1. On inspection we find that slides 1 and 2 are inverse-related, as well as the pair of slides 3 and 4. For the rest, however, the inverse of any permutation is found on the same slide.

A summary of the relationships between the eight slides can be found on the page "Spiral Set Stack."


[1] If the order of the basic set is odd, say 7, all of these relationships will still work and create analogous structures. To work with an odd order, begin by extending the open path diagrams in order to get around the difficulty of dividing the basic set exactly in half. It's an interesting exercise which I'll leave to the reader.
[2] Sorry. Typography problem here. Think of the arrows to the right of a letter within the text as being above the letter as in the slide.