August 2012 - mathfun@mailman.xmission.com

[math-fun] Huge Mandelbrot set
by Adam P. Goucher 19 Aug '12

19 Aug '12

As a computational tour-de-force, I decided to draw a large image of the Mandelbrot set and save it as a macrocell file. The iteration limit was 1000 iterations per pixel, and the bounding box is 258687 by 221688. https://docs.google.com/open?id=0B7zc3Wqisi4jenRfQmlmQTJ4LXM There's some slight mutilation, unfortunately, due to the lazy recursive sampling method I used. I think the worst (only?) case of this is the southernmost minuscule 'copy' of the Mandelbrot set, which does not appear reflected in the real axis. I've used machine-precision complex numbers to accelerate the process; hence, there is some very minute asymmetry. Oh well. The computation took 20427 seconds on my old 1.3 GHz single-core machine from 2001. Individual 32 by 32 squares are computed in efficient C code and assembled by Mathematica 8. I then optimised the quadtree (resulting in a reduction in file size by almost an order of magnitude from 722MB to 85MB) using a C++ program. The GZipped version (25MB) is available for download from the above link. Sincerely, Adam P. Goucher

6 8

[math-fun] Plane Geometry puzzle
by Warren Smith 18 Aug '12

18 Aug '12

>Dan Asimov dasimov at earthlink.net >Just noticed this problem, with one solution given, in an obscure article: >"Find a finite subset of the plane such that for any two of its points the perpendicular >bisector of the segment connecting them passes through exactly two points of the set." --don't know answer, but if we transplant to surface of sphere not plane (use geodesics not lines) then the 4 vertices of a regular tetrahedron work. (Other platonics have other interesting properties of this ilk.)

1 0

Re: [math-fun] Huge Mandelbrot set
by Henry Baker 18 Aug '12

18 Aug '12

You're right -- this paper isn't particularly helpful to anyone who isn't already steeped in GPU technology. Here's most of what you need to know: "SMX: 192 single-precision CUDA cores, 64 double-precision units, 32 special function units (SFU), and 32 load/store units (LD/ST)." If you're doing 32-bit single precision, I think you basically have an SIMD array of 192 processors. "CUDA" is nVidia's C-based language for programming these things. Since Mandelbrot does a reasonable amount of processing per pixel, it shouldn't be memory-bound. Even GPU memory is getting pretty cheap, so you can have a very large image store -- hence the ECC on the image memory. At 03:23 PM 8/18/2012, Fred lunnon wrote: >For all the sense I could make of it, this document might just as well >have been an extract from a storyboard for Star Wars --- and I used to >teach computer architecture a few years ago! > >WFL > >On 8/18/12, Henry Baker <hbaker1(a)pipeline.com> wrote: >> Can't modern GPU's (nVidia Kepler, etc.) compute Mandelbrot in "real time" >> -- i.e., the time >> it takes to display that portion of the screen ? If not, aren't modern >> GPU's getting pretty >> close to this capability ? >> >> www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepap…

1 0

[math-fun] Max |determinant| for Toeplitz*Hankel sign matrix
by Warren Smith 18 Aug '12

18 Aug '12

A Toeplitz matrix is constant along diagonals. A Hankel matrix is an upside-down Toeplitz matrix (hence constant on antidiagonals). What is the greatest |determinant| for the elementwise (aka Hadamard) product of two NxN sign matrices, one Toeplitz and one Hankel? The answer N det example matrix 1 0.00 -- 2 2.00 +---+- 3 4.00 ++----+--- 4 16.00 ++--+---+----- 5 48.00 -+++-+++-++------- 6 160.00 +--+++-++---+--------- 7 576.00 +--+---+-++---+----------- 8 4096.00 ++-+++--+---+---+-+-+--------- (Toeplitz specified by stating leftmost column going up, then continuing along top row going right, i.e. "clockwise"; then Hankel specified by stating top row going right, then continuing along rightmost column going down, i.e. "clockwise.") happens to match the maximum |determinant| for ANY matrix with real entries in [-1,1] given in http://oeis.org/A003433 ...at least it matches up to N=8. When (if ever) does Toeplitz*Hankel fail to reach optimality over all matrices?

1 0

[math-fun] NxN Toeplitz matrices with entries +-1 and maximum|determinant|
by Warren Smith 18 Aug '12

18 Aug '12

>Adam P. Goucher apgoucher at gmx.com Hmm, these look interesting when expressed in binary: 1 10 100 10000 110000 10100000 1001000000 101000000000 11000000000000 10010000000000000 1010000000000000000 1000000000000000000000 111000111101000000000000 100000110101010000000000000 --if you were to use not {+1,-1} matrices, but rather {0,1} then you'd basically get the same determinants but with a lot of factors of 2 removed. Well, not quite... consider row operations... This is a crude/vague/flaky explanation of why the determinant is divisible by a large power of 2.

1 0

[math-fun] NxN Circ*Backcirc matrices with entries +-1 and maximum |determinant|
by Warren Smith 18 Aug '12

18 Aug '12

Among the NxN matrices that are the elementwise product (also called Hadamard product) of a circulant sign matrix with a backcirculant sign matrix, examples with maximum |determinant| are as follows. Matrices are specified by the first row of the circulant then the first row of the backcirculant. N det example matrix 1 1.00 -- 2 0.00 +--+ 3 4.00 +++-+- 4 16.00 ++---+-- 5 48.00 ------+--- 6 128.00 +++----+---- 7 512.00 +++++++++-+--- 8 4096.00 ++---+---+------ 9 6912.00 +++++++++++-+++-+- 10 36864.00 +-+++++-+-+++++-++-- 11 273408.00 +++++++++++-+--+++---- 12 -2097152.00 +-+-+--+--+-++-+-++----- 13 14929920.00 +++++++++++++++++-+++--+-+ 14 -50331648.00 ++--+-+--------+-+-+-+-+-+-+

1 0

[math-fun] NxN Toeplitz matrices with entries +-1 and maximum |determinant|
by Warren Smith 18 Aug '12

18 Aug '12

(This is a related, but different, problem from the previous one for circulants.) A Toeplitz matrix is constant along diagonals. An NxN Toeplitz matrix with entries +-1 and maximum |determinant| is as follows, where I regard the Toeplitz as specified by its entries going up the first column, then rightward along the top row (i.e. "clockwise"). N det example matrix 1 1.00 + 2 2.00 +-- 3 4.00 --+++ 4 16.00 +---+-- 5 48.00 -++++-+++ 6 160.00 +-+++--+--- 7 576.00 -++++-+--++++ 8 2560.00 +-+++---+--+--- 9 12288.00 --+---+++-++-+++- 10 73728.00 ++-++-+++---+--+--- 11 327680.00 +-++++--+++-+-----+-- 12 2097152.00 +-++----+---+-++----+-- 13 14929920.00 -+-+++++-+++--+-+++++-+++ 14 68853760.00 +--+-+-----+++-++-+-+++++--

2 1

[math-fun] Maximum |determinant| for NxN circulant sign matrix?
by Warren Smith 18 Aug '12

18 Aug '12

What is the maximum |determinant| of an NxN circulant matrix whose defining first row consists entirely of +1's and -1's? (Related question: each entry lies between -1 and +1 inclusive?) -------- The answer is <=N^(N/2), but this upper bound is achieved only when N=1 and N=4 (by -1,1,1,1). When N=5 the best matrix is (-1,1,1,1,1). Thus the sequence begins 1,0,4,16,48 and the next entry perhaps is 128 from (-1,1,1,1,1,1). The NxN circulant matrix (-1,1,1,...,1) has det = N * (-2)^(N+1) = -1,0,+4,-16,+48,-128... but this formula definitely stops yielding maximum |det| at N=7 because formula would yield 320 whereas the matrix (-1,1,-1,-1,1,1,1) has det=512. [Possible calculational tricks: The first entry is +1 wlog saving you a factor of 2. The second entry is >= the last entry, saving further factor. The determinant of an NxN circulant can be calculated by taking the FFT of the first row, scaling, then product of FFT entries, see http://en.wikipedia.org/wiki/Circulant_matrix which runs in O(NlogN) operations. Using however the slow discrete FT instead of fast FT we can improve to time O(N) per matrix by examining matrices in gray-code order.] -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 4

[math-fun] A remarkable probability distribution on the (perimeter of the) unit circle
by Warren Smith 15 Aug '12

15 Aug '12

> This density on the circle shares the property with the plain uniform > distribution on the circle that the expected value of z^k > is ZERO for each integer k with |k|>1. > However, when |k|=1 we (unlike plain uniform) do NOT get zero, --actually... duh... it occurs to me we can also get all well-behaved densities on the circle |z|=1 which have this "remarkable property" by simply making the density be proportional to A + z + 1/z for any constant A>=2. (Proof: fourier series.) So, my particular density which I constructed in a much more complicated way must be expressible as such a formula (that equality is a remarkable identity, I guess).

1 0

[math-fun] A remarkable probability distribution on the (perimeter of the) unit circle
by Warren Smith 15 Aug '12

15 Aug '12

> However, when |k|=1 we (unlike plain uniform) do NOT get zero, > we get 0.8281 approximately (and of course when k=0 we get 1). --correction of bug: 0.4529 approximately. (Perhaps somebody can compute this to much greater precision... incidentally it turns out the sum of 1/p^2 for p prime has allegedly been computed to very high precision by Pascal Sebah & Xavier Gourdon: 0.452247420041065498506543364832247934173231343239892421736418... http://numbers.computation.free.fr/Constants/Miscellaneous/constantsNumTheo… http://numbers.computation.free.fr/Constants/Miscellaneous/constantsNumTheo… )

1 0