About the Cover of AMS Notices Dec 2005
The December issue of Notices of the AMS contains an image of the component-by-component matrix on the cover by me as well as a one page explanation of these matrices as accompaniment to an article by Ian Sloan and Frances Kuo. On this page you can find some more images.
Note that the images on this page are also provided as eps and pdf. When viewing these files you can zoom in and out as you like without loosing quality, they are pure vector images unlike the rasterized versions in the online version of AMS.
What is this matrix all about?
For a full explanation you might want to read the preprint of “Fast Component-by-Component Construction of Rank-1 Lattice Rules With a Non-Prime Number of Points” to appear in the Dagstuhl 2004 issue of Journal of Complexity. A less demanding option is of course to read the one page explanation in Notices of the AMS (free, but requires registration). Or you can keep on reading this page where I will just try to give an explanation of what is on the pictures, not where they come from.
Consider a multiplication table where horizontally we have the numbers from 0 to n-1 and vertically the numbers relatively prime to n and were the multiplication is taken modulo n.
If n would be a prime number p, this would be a real multiplication table of the cyclic group Zp×. Since this group is cyclic you could find a generator g for which the powers generate all elements in the table, i.e.
Giving every element a unique color we can picture this multiplication table as the images in Figure 1.
Note that the only extra ordinary column of this (p-1) × p matrix is the column where we have the zero element on top. In the left image this is the first column, in the right image this is the last column (and here only the first entry is drawn in full color since the others are redundant, this will become clear further on). Now let's forget about the zero element for a while and only look at the cyclic group of multiplication modulo a prime.
You can compare the right of Figure 1 on this page with those on the Cyclic Group page from Mathworld, and you will notice that there they have constant anti-diagonals. That is: there the tables are pictured by having positive powers of g in both the horizontal and vertical direction, whilst in my figure on the right, one of the two directions has negative powers.
This is of no importance when we would just be looking at the multiplication table, but in the application of component-by-component lattice rule construction, it happens that we have to multiply a vector with a matrix with this structure a hell of a lot. Putting this table in a formula we would have
And luckily for us, multiplying a vector x with such a matrix C is just cyclic convolution of a vector c with x where c is just the first column of C:
where F and F-1 are Fast Fourier transforms (every discrete Fourier transform can be done in time O(n log(n)), also when n is not highly composite or even prime). Doing this Fast Fourier thing transforms our general matrix-vector product of time O(n2) into a diagonal matrix-vector product of only O(n) at a cost of O(n log(n)) and uses only O(n) memory to store the matrix. Ok, that's fine for n prime and not so difficult, but what about general n?
Taking prime powers n = pα
Since multiplication modulo n is also a cyclic group for prime powers, it is natural to first look at this special case. While in the prime case the only missing element in the horizontal direction was zero, here there are much more missing elements. The cyclic multiplication group modulo a prime power only contains the elements relatively prime to n. And in fact, this is exactly the definition of the group Zn×
This at least means we can form a block of size φ(pα) × φ(pα) in the form which allows us to use the cyclic convolution trick. If we can do a similar trick with the other columns of our matrix then we are done. And yes, we can, the result can be seen in Figure 2.
The image shows that for a prime power we actually have many interleaved structures of the form as for a single prime number. In fact, we get a circulant block for every divisor of n, i.e., for n = pα, these are pl with l = 0 to α. For larger divisors, we have smaller blocks left, since more and more numbers are “divided out”. The rest of the matrix is then simply filled up with copies of the same block. In the pictures this is denoted by displaying the copies of the blocks in faded colors.
We can now work our way back to the original structure seen for the prime case: the simple flower-like pattern. In this way we obtain an intermediate matrix, which is kind of half way to the circulant form, in which for every final circulant block we get a basic flower-like pattern in which the prime basis can be easily recognized. This is visible in Figure 3.
General n
The basic matrix is obtained by