The computation

So the computation has finished (actually a few days ago) for degree 19. I’ve only yesterday gotten around to finishing a short paper (addendum) to post to arxiv, which I’ve done yesterday, see arXiv:1302.1441. The really funky thing is that there are so many sharp polynomials in degree 19. Up to symmetry there are 16 in odd degrees up to degree 17, yet there are 13 in degree 19. And two of the new ones are symmetric, which is actually surprising, that seems it should be hard to achieve if you think about how they are constructed. There’s probably a bunch of interesting number theory that appears here. It should be fun to figure out what’s going on there.

This was the first time a paper of mine got reclassified to a different archive on arxiv. I put it into algebraic geometry because well, the motivation comes from geometry, but it got stuck into comutative algebra. Which actually makes a lot more sense. Especially since none of the motivation from geometry appears in this writeup.

Degree 21 has been running for about a week. It will probably be running for the next year or so at which point I really expect it to just spit out only one polynomial which is the group invariant one we already know about. Which would be also kind of funky since then there would be two degrees with as few polynomials as possible and in between there would be a degree with the most polynomials we have found so far in any degree.

The correct finite field does wonders

So the computation I was running since thanksgiving was getting nowhere (finding degree 19 polynomials which are equal to 1 on x+y=1, which have fewest possible terms (11) and which have only positive coefficients, we know that there are finitely many, the trick is to find them). My code didn’t really have good status updates. Well it does tell you exactly where it is, but it takes a bit of computation to really see how it’s progressing, so I didn’t do that until a few days ago since I thought it was going way too slow.

And low and behold, it was going way too slow. I computed that it should take another 3-7 years or so (different parts of the search space take different times so it’s a bit hard to estimate). That was a bummer. That was about 10 times longer than I thought it should be. At first I was a bit resigned to this reality, but the next day I started to look into it, and one thing I figured out after running a bunch of tests was that one shortcut I was using was never triggered. The idea is that we need to find when a certain matrix with integer coefficients has 1 dimensional nullspace. Doing the integer row reduction is done with gmp, and is reasonably fast. But since we do this many times over and most of these matrices are simply full rank (no null space), we don’t really need to do the whole computation. So what we can do (and this is a useful trick to know), is to first do all computation in some small finite field, e.g. do everything mod p for some small prime p. If a matrix is full rank mod p, it is full rank. The computation can be done rather quickly this way and you don’t even have to involve modulo computation, since all the possible computations you can just precompute first and just build up a big table, so instead of two multiplications, an addition, and finding the remainder, you just look up in a table. Anyway, that gets us quite a bit of a speed up.

Now the thing is that I was using mod 19, since that worked for lower degrees. One thing I forgot when I started the run (remember this was a few years since I looked at this code and ran it last time), is that the modulus cannot be the same as the degree. The matrices we need to work with have most terms divisible by the degree. So moding out by 19 essentially always made the matrix all 0 (except for a few 1s scattered around). So these matrices were essentially always singular and the shortcut never triggered. So after doing a useless mod 19 calculation we had to do the actual integer arithmetic. That’s why it was slow. Damnit!

Well the calculations were not wrong, I just did a lot more computation than needed. After a small amount of testing it seemed that mod 23 was a good finite field to proceed in, so I restarted the code. Suddenly 3-7 years turned into first estimating 90 days and after running things for a day, that turned into an estimate of 30 days.

Then I noticed one more thing (and Danny pointed this out too), that his code used symmetry and just threw out half of the nonsymmetric polynomials, since the computations are the same. I remembered that my code didn’t do it. It didn’t make much sense if the longest run we did was 5 days on one core (for code that is only ever run once or twice, small speedups are somewhat pointless). I implemented this idea and it seems to achieve 33% reduction in time (there’s still the checking for symmetry, and there are of course symemtric polynomials, so that’s probably close to where we can get). So anyway, I guess within 20 days we should have the answer.

After it finsihes, I still have one more speedup up my sleeve. It could be that I can do the row reduction really fast mod 2 by using binary operations (each row would be an unsigned int). Not sure what speedup I can achieve though, at best 90%, since that’s how many cases mod 2 catches. While mod 23 or so catches essentially everything. So the idea is to do mod 2, then mod 23, and only then if the matrix is still singular do the integer arithmetic. If the speedup is another 50%, and my most optimistic estimates hold, that would put degree 21 within the realm of possibility, though at least half a year on 4 cores. That’s is, within something I’d be willing to run.

So, the mood went from “I’ll probably give up n d=19 soon” to “maybe d=21 is possible”. All this just by using a different prime

New versions of books and new genius

So in the last two days I’ve put up new versions of both the differential equations textbook (3 new sections, and of course some fixes) and the real analysis textbook (fixes, plus 4 new exercises). And also I’ve made a new release of genius. Actually two of those I just did today when my students were taking their final. The nice things about proctoring tests with small upper division classes is that you can get stuff done. There is no cheating going on. There’s only a few questions, so I had over two hours to burn. Next semester will be quite different. I’ll have two calculus lectures with 250+ students each. Proctoring an exam for that many students is not at all a relaxing exercise (and then there’s the grading … ugh!)

Yet another new section in DE book

In trying to avoid bad mood and keep stress level down, people turn to hobbies. One of my hobbies is working on my textbooks, so I have written a new section on the Dirichlet problem for the Laplace equation in the circle for the differential equations book. See the draft section. The previous section 4.9 is OK, but the solution is far more natural in the circle in polar coordinates than in a square, that is we obtain

And then we can derive the Poisson formula which is just cool. Also it’s a good example showing more complicated change of variables since we do it in polar, and also it shows a somewhat more complicated and different separation variables.

Part of the motivation was that I did this topic in my PDE class so I had lecture notes and it really felt right for that point in the book, even to leave it as reading to interested students. The other part is that I have been improving the graphing ability of genius so I can do polar coordinates for example:

That’s the graph of the solution , showing that high frequency on the boundary means fast decay as you go closer to the center of your domain.

Though there is no UI for polar coordinates, there is just a function that allows you to plot arbitrary surface data now. Notice how it’s not graphed on a square grid, but above the disc. Also notice that internal rings have fewer points on them, that’s because I just compute fewer values at smaller radii, remember I am passing in arbitrary data, a list of tripples (x,y,z). This will be in version 1.0.16, which should come out end of next week sometime (have to let translators have a go at it). Actually the reason for doing this work on genius was not polar coordinates but showing numerical solutions in my PDE class. It’s just that one of my test cases was polar coordinates and so it just clicked and I thought: I have to write up this section, it’s just too cool to pass up and I can make the graphs now.

This brings the number of pages in the DE book to 315, and the number of exercises to 533. Yaikes! It’s become a beast. I’ll make the new version in a week or two so that it’s usuable for next semester (so if you have comments on the new section do let me know quickly).

I think now a two semester course could possibly be run out of the book. What’s going to be added in the new version is essentially about 5-6 lectures. At my speed the whole thing is now approximately 65 lectures, so a bit less than two semesters worth, but if you go just a tad slower (as many people do), do more examples, and if you factor in exams, reviews, quizzes, etc… it’s just right I think. You’ve got lots of room to spare if you want a two quarter course.

Bad memory

So I just remembered, it wasn’t that we thought the computation (see a previous post) would take half a year, it would take 450 days on 3ghz CPU. I guess my memory was being optimistic. I remembered “half a year” when it was really “one and a half a year”. OK, so the computation has now been running for a bit over 2 weeks now on 4 cores. I guess I’m at least 10% there (I hope). It looks a bit worse from the output. It doesn’t seem computers have gotten all that much faster (not at all it seems at least on the load I am trying to do) in the past few years. The only thing better is more cores.

Frobenius method and Bessel functions

I had occasion to talk about Bessel functions and mention the Frobenius method in my PDE class and I realized that I do not have any mention of this in the book. This was the section I did not quite get to when teaching at UCSD, so it never got written. Well, worry no more. I’ve written up a draft version of the section. This will appear in the next version of the book whenever I make it, though if you do have comments, do let me know. It’s good to catch typos or make changes now.

This brings the number of pages to 307 together with new delta function section and the number of exercises to 521. Yay!

This also made me realize that Genius did not have Bessel functions implemented. They were actually easy to implement as MPFR has them done. At least for integer orders and real values anyway. Then as my current working directory of genius was such a mess with trying to include LAPACK, I decided to remove LAPACK for now from the genius git. I think what I will do is link to the fortran version at some later point. It seems like the fortran LAPACK is available almost everywhere, so it should not be a bad new dependency. Much easier than trying to make the beast compile cleanly inside genius. Anyway, so Bessel functions will be in Genius, which I think I ought to make a release of soon as there are a bunch of other small changes to set upon the world.

“Maxima is calculating”

So friday afternoon I wanted to test for existence of a certain mapping that takes one surface to another surface. Everything is algebraic so one might assume if a mapping exist it might actually be polynomial and since everything is of low degree, the mapping might be as well. So I just set up brute force equations and tried an arbitrary degree 2 mapping. After a second or two, maxima returned no solutions to the resulting system. OK, so how about plugging in degree 3. It turns out I don’t need to test the linear terms, and there are 3 variables so 16 variables per component so I get an algebraic system in 48 variables. Sounds bad, but lot of the equations become something of the form “x=0″. So I looked at a subset of the system. Already the generating of the equations took a few seconds. So I thought, this will take a few minutes. So I started “algsys” on the equations. Well, that was wednesday afternoon. It is Sunday and the thing is still running. Unfortunately it just says “Maxima is calculating” in the wxMaxima window, so one has no clue if it will take another day or so, another year or so, or if the sun will implode first. I sort of have the feeling it is doing something stupid. Once I get more time for math on monday, I’ll probably try to simplify the equations by hand first. I could also try for the solution (or lack thereof) numerically. In the meantime I’ll let it run. This is on my laptop which is surely not meant as a computation machine. It’s only running on one core so it’s not heating up too badly. When I was running some computations for days in the summer on all four cores you could almost cook eggs on the keyboard.

On a related front, I decided that my work computer is sitting too idly so I started the degree 19 calculation that we never did with Danny on our paper [1]. In 2008 we thought it would take at least half a year. Presumably the computers have gotten a tad quicker in the meantime (and since I’m running it on 4 cores), so perhaps the result will come in sooner. Still the progress seems slow from the output so far. It is a bit difficult to judge, I’ll try to estimate time left more precisely later on, but just as first guess from looking at the output I don’t think this will be done before christmas.

There is something magical about pressing ENTER to start the computation you know will take months to complete. It is one of the few places where you really use the fact that you have a fast computer. Most computer power is totally wasted. So for example in somewhat similar time frame Firefox managed to get 70 minutes of CPU time (maxima is up to 5208 now). Now that’s with only very occasional short browsing over the last few days. It seems mostly it’s the tabs being open that eat up time, run the CPU and heat our house. Come to think of that my office will be quite warm I bet once I get there on monday, I don’t think the heating runs on the room termostat, as the swich on that thing is in “off” position and it still heats the room. So with the added heating from 4 cores running at top speed and it being a small room, it should get toasty.

Update (monday morning): Actually my office was not much warmer. The computer case is actually quite cold and I don’t feel a huge difference in temperature of the air output. I don’t know why I never ran anything on this computer and always used my laptop so far for longer computations. I think I’ll abuse it more from now on.

[1] Jiří Lebl and Daniel Lichtblau, Uniqueness of certain polynomials constant on a line, Linear Algebra and its Applications, 433 (2010), no. 4, 824-837, arXiv:0808.0284.

Numerical range

I was fiddling with numerical range of two by two matrices so I modified my root testing python program to do this. The numerical range of is the set of all values

for all nonzero vectors . This set is a compact set (it can be seen as the image via the mapping of vectors on the unit sphere which is a compact set). It’s convex which is harder to show. For two by two it is an elliptic disc (could be degenerate).

See the result here, it plugs in random vectors and shows the result. Here’s an example plot for the matrix .

The code is really inefficient and eats up all your cpu. There’s no effort to optimize this.

Visualizing complex singularities

I needed a way to visualize which t get hit for a polynomial such as when z ranges in a simple set such as a square or a circle. That is, really this is a generically two-valued function above the z plane. Of course we can’t just graph it since we don’t have 4 real dimensions (I want t and z to of course be complex). For each complex z, there are generically two complex t above it.

So instead of looking for existing solutions (boring, surely there is a much more refined tool out there) I decided it is the perfect time to learn a bit of Python and checkout how it does math. Surprisingly well it turns out. Look at the code yourself. You will need numpy, cairo, and pygobject. I think except for numpy everything was installed on fedora. To change the polynomial or drawing parameters you need to change the code. It’s not really documented, but it should not be too hard to find where to change things. It’s less than 150 lines long, and you should take into considerations that I’ve never before written a line of python code, so there might be some things which are ugly. I did have the advantage of knowing GTK, though I never used Cairo before and I only vaguely knew how it works. It’s probably an hour or two’s worth coding, the rest of yesterday afternoon was spent on playing around with different polynomials.

What it does is randomly pick z points in a rectangle, by default real and imagnary parts going from -1 to 1. Each z point has a certain color assigned. On the left hand side of the plot you can see the points picked along with their colors. Then it solves the polynomial and plots the two (or more if the polynomial of higher degree) solutions on the right with those colors. It uses the alpha channel on the right so that you get an idea of how often a certain point is picked. Anyway, here is the resulting plot for the polynomial given above:

I am glad to report (or not glad, depending on your point of view) to report that using the code I did find a counterexample to a Lemma I was trying to prove. In fact the counterexample is essentially the polynomial above. That is, I was thinking you’d probably have to have hit every t inside the “outline” of the image if all the roots were 0 at zero. It turns this is not true. In fact there exist polynomials where t points arbitrarily close to zero are not hit even if the outline is pretty big (actually the hypothesis in the lemma were more complicated, but no point in stating them since it’s not true). For example, doesn’t hit a whole neighbourhood of the point . Below is the plot for . Note that as n goes to infinity the singularity gets close to which is the union of two complex lines.

By the way, be prepared the program eats up quite a bit of ram, it’s very inefficient in what it does, so don’t run it on a very old machine. It will stop plotting points after a while so that it doesn’t bring your machine to its knees if you happen to forget to hit “Stop”. Also it does points in large “bursts” instead of one by one.

Update: I realized after I wrote above that I never wrote a line of python code that I did write a line of python code before. In my evince/vim/synctex setup I did fiddle with some python code that I stole from gedit, but I didn’t really write any new code there rather than just whacking some old code I did not totally understand with a hammer till it fit in the hole that I needed (a round peg will go into a square hole if hit hard enough).

Return to linear search

So … apparently searching an unordered list without any structure whatsoever is supposed to be better than having structure. At least that’s the new GNOME shell design that removes categories, removes any ordering and places icons in pages. The arguments are that it’s hard to categorize things and people use spatial memory to find where things are.

The spatial memory was here before with nautilus. It didn’t work out so great. No people don’t have spatial memory. For example for me, I use a small number of applications often, I put their launchers somewhere easy to reach. The rest of the applications I use rarely if never. No I do not remember where they are, I do not even remember what they are named. E.g. I don’t remember what the ftp client list, but I am not a total moron and I correctly guess to look for it in the “Internet” menu which is managable. Given I’ve used ftp probably once in a year, I do not remember where it is. Another example is when Maia (6 year old) needs a game to play. I never play games, but I have a few installed for these occasions. Do I want to look through an unordered list of 50-100 icons? Hell no. I want to click on “Games” and pick one. 95% or so of applications i have installed I use rarely. I will not “remember” where they are. I don’t want to spend hours trying to sort or organize the list of icons. Isn’t that what the computer can do for me? Vast majority of people (non-geeks) never change their default config, they use it as it came. So they will not organize it unless the computer organizes it for them. I have an android tablet, and this paged interface with icons you have to somehow organize yourself is totally annoying. One of the reasons why I find the tablet unusable (I don’t think I’ve turned it on for a few months now). That interface might work well when you have 10 apps, but it fails miserably when you have 100.

If I could remember that games are on page 4 (after presumably I’ve made a lot of unneeded effort to put them there) I can remember they are in the “Games” category. Actually there I don’t have to memorize it. Why don’t we just number all the buttons in an application since the user could remember what button number 4 that’s right next to button number 3 on window number 5 does. I mean, the user can use spatial memory right?

Now as for “that’s why there is search” … yeah but that only works when you know what you are searching for. I usually know what I am searching for once I found it. It’s this idea that google is the best interface for everything. Google is useful for the web because there are waaaaay too many pages to categorize. That’s not a problem for applications. Search is a compromise. It is a way to find things when there are too many to organize.

The argument “some apps don’t fit into one category neatly” also fails. The whole idea of the vfolder menus was that you could have arbitrary queries for submenus. You can have an app appear in every category where it makes sense. Now just because people making up the menus didn’t get it just right doesn’t make it a bad idea. Also now this leads to a lot of apps without any categories. The problem I think is with the original terminology. When I was designing this system I used “Keywords” instead of “Categories”. But KDE already had Keywords, so we used Categories, but you should think of them as Keywords on which to query where the icon appears. It describes the application, it doesn’t hardcode where it appears. Unfortunately, there seems to be a lack of understanding of this concept which always led to miscategorization. For example someone changed the original design to say some things were some sort of “core categories” or whatnot and that only one should appear on an icon and that there will be a menu with that name. That defeats the purpose. It’s like beating out the front glass of your car and then complaining about the wind.

Finally, what if I lend my computer to someone to do something quickly. No I am a normal person, so I don’t create a new account. And even if I do create a new account, the default sorting of apps is unlikely to be helpful. If someone just wants to quickly do something that doesn’t involve the icons on the dash, they’re out of luck if I have lots of apps installed. Plus at work I will have a different UI, on my laptop I have a different UI, and any other computer I use will have a different UI. I can’t customize everyone of them just to use them.

As it is, if I had a friend use my computer with gnome-shell they were lost. If it’s made even less usable … thank god for XFCE, though I worry that these moves towards iphonization of the UI will lead to even worse categorization. There are already many .desktop’s with badly filled out Categories field, so there will be less incentive to do it correctly.