ChapterZero

It seems I’m going to be doing a lot of running around during my first week in California: I have to apply for a California driver’s license, both because the school requires it and because my current one expires this November. I was also supposed to go back to Barbados this winter for the first time in 7 years, for a family reunion, but apparently someone misplaced my certificate of citizenship, so I can’t get a passport, and have to apply for a new one. That’s going to cost me $220! Then I have to wait, probably for a year or more, to get the certificate, before I can apply for the passport. Then that’s another $100. I have to do all of this without a car.

The programming language Aldor, aka A^#, seems to be a well-kept secret. It started off as the compiler for Axiom, Axiom-xl, but has since developed into an interesting standalone language in its own right. It reminds me of Scheme, C/C++, Python, and Perl 6 to varying degrees. In particular (with respect to being similar to Perl), where Perl has Parrot and Java has the JVM, Aldor has FOAM, the First Order Abstract Machine:

A major part of the tex2html_wrap_inline302 compiler is concerned with producing optimized intermediate code, or Foam code. “Foam” is an acronym for “First Order Abstract Machine.” The abstract machine is first order in the sense that it does not treat its types as values.

Foam is designed to contain only those concepts which can have an efficient realization in both Lisp and C. For example it is not possible to take an address of a variable because that would be inefficient in Lisp (a closure would be created). Nor are dynamic type tests allowed, as that would be inefficient in C. We have been asked how the lack of address arithmetic limits the potential performance of compiled tex2html_wrap_inline302 vs hand-coded C which uses pointers to traverse arrays in inner loops. It is our experience that this is a minor concern on current architectures with optimizing compilers.

Foam is not restricted to the precise intersection of C and Lisp. Some aspects are handled by support libraries. Big integer arithmetic is assumed as part of Foam, and this is provided as a library for C. Also the memory model differs from both C and Lisp in some details: garbage collection is assumed (this is a run time support library in C) and it is possible to make an explicit request to free storage (in Lisp this is ignored).

A Foam program is comprised of a flat sequence of commands. Foam types have various sizes and uses. or example, “Char” is a text character whereas “Byte” is a character sized integer, “DFlo” is a double precision floating point, “Ptr” can point to an array, record, arbitrary sized integer, etc. Reference instructions contain the kind of reference and the position, e.g., “Loc 3” refers to the third local variable of the current function and “RElt 7 x 2” indicates the 2nd field of the record x, using the 7th layout format. Foam operations consist of instructions, such as “If b n,” which indicates that if b is true then proceed to label n, and builtin operations, e.g., “HIntLT a b” is a half-word-integer less-than comparison. The builtin operations are type specific and conversion operations are generally provided. A detailed description of Foam is given elsewhere [26].

The abstract machine does not support asharp types directly and relies on the code generator to produce appropriate calls to create and maintain types. This has the advantage that one can use these calls to add new representations of types to the system. These representations may be written in tex2html_wrap_inline302 itself, or some other language. This is used in order to interface with the Axiom system, and may be extended to other object/type systems, such as CLOS [21] and C++.

Also, since Aldor evolved out of Axiom, where one might want to coerce types like Polynomial Integers to Polynomial Reals on the fly, or reorder the types in a hierarchy, it supports functions and types as first class objects. This makes for the most interesting features of the language.

Then there are several libraries which make Aldor look like a particularly good system for implementing computer algebra algorithms on: Algebra and Sumit, by Manuel Bronstein, support basic CAS facilities and the solution of first order linear differential/difference equations, respectively. There’s also an older BasicMath library from NAG which seems to support a rather respectible subset of CAS facilities, e.g. subresultants. Of course, considering its origins, it’s also probably trivial to use Axiom from Aldor.

Maybe the biggest reason that Aldor isn’t as well known as it could be is that it is not free– binaries are available for non-commercial use, but the source is not, even though Aldor is not being commercially distributed. Anyhow, in this day and age, what profit is there in commercial general purpose languages? Although it would be more convenient to use Aldor, I suspect most researchers/implementors of CASes (the two classes of people I see most likely to be attracted by Aldor’s particular strengths) will be more willing to reinvent several wheels than depend on a potentially capricious licensor. Too bad, but some Axiom developers are gathering a petition together– go sign it!

I’ve entered a crucial time in my transition from Houston to California: from now until I reach there, I shouldn’t order any books online. If I got them shipped to Houston, it’s too likely I wouldn’t be around to pick them up, so someone would have to squander money to get them shipped to me; knowing my family, I’d probably also get them months after they arrived (no kidding). I don’t have an address in California to ship them to.

Knowing that I’m in this position makes me more anxious to go online and buy a book, any book. Lately I’ve been adding books to my Amazon.com booklist with an unholy fervor; I even started a new book list to handle fiction (usually I only keep technical books on my wishlist). There are several books that I’d really like to own yesterday: Analytical Mechanics by Fasano and Marmi, and The Geometry of Spacetime by James Callahan come to mind, but I’m stuck deciding which to plunk down the cash for. My next couple of purchases will definitely be physics books– I already have many math books that I’m not going to get around to reading anytime in the next 5 years– but deciding which constitute good starting points is a difficult task. I’m looking for something that starts off with foundational material and slowly builds a respectable edifice; preferably something that develops one or more foundational mathematical tool (e.g. Hamiltonians, Lagrangians, differential geometry, etc.) along the way. The two aforementioned books seem to do a good job covering the classical mechanics and spacetime aspects of physics, but I’d like to have candidates of a similar caliber for quantum mechanics and cosmology.

I spent most of my time today trying to answer the following question. Let be radial filters in the sense that when (and likewise for the ’s). Then is the filter also radial?

The answer, it turns out, is no in general (but of course it is true in , because then the filters are just even). In the 2-d case, the filters

serve as a counterexample: , but .

I haven’t yet found a satisfactory reason for this failure — my vague idea is that rotations do not preserve the lattice, but that doesn’t do more than imply the result. To construct this counterexample, I followed Papadakis’ advice of looking at the simplest radial filters of all: filters which are unity on the intersections of the lattice and a sphere and zero elsewhere, as in the examples given above. In the Fourier domain, the convolution product would look like

and if the resulting filter was also radial, it would look like a sum

in the frequency domain. I wrote a Mathematica program that takes and , calculates the coefficients of the resulting filter, and says if it breaks into such a sum. Now that I think about it, that would have been much easier to do in the spatial domain.

As a corollary of this result, you can see that the following proposition is not true in general: if with , there is an so that and .

‘Effort is more important than innate ability’– seems like a confidence boosting feel-good saying, but this study of chess masters and other experts compiled results that, at least in that arena, make this an aphorism:

• Some chess masters have the ability to play chess (well) when blindfolded; the mechanism involved is nothing so prosaic as a representative mental image of the current layout of the pieces: instead a quick and unconscious reasoning process involving recall of what moves were possible or impossible previously in the game and a more general store of knowledge of previous games played seem to be what allows this feat.
• When asked to recall the layout of a chess board at a position reached through authentic game play, after viewing it for only a few seconds, chess masters were invariably able to reconstruct it perfectly. On the other hand, novice or weak chess players performed much worse even when given 30 seconds to view the board. Interestingly, experts and weaker players performed equally poorly at recalling the layout of random board layouts.

There are more points to support the thesis, and the conclusion they all seem to point to is that being an expert has more to do with a field specific store of knowledge that is constructed through experience and repetition than with ‘genius’. It’s always good to have science back up what common-sense tells you.

I reencountered the Riemann rearrangement theorem this weekend. It states that a conditionally convergent series can be rearranged so that it adds up to any given number. Mysterious-seeming, yes, but not at all hard to justify: it almost follows directly from the definition of conditional convergence. If a series converges conditionally, then and , so you can approximate any positive number by adding an appropriate number of terms from the positive followed by an appropriate number of terms from the negative ; since , this approximation can be made arbitrarily precise. Ditto for negative numbers.

Seems this is yet another one of those simple theorems that just didn’t click with me the first time around– I suspect because I was introduced to it via a formal proof, where we had to keep track of multiple quantities, instead of the simpler hand waving argument I just gave. As I recall it, the formal proof in baby Rudin uses an atrocious number of auxiliary quantities.

An interesting corollary (at least to me, since I came up with it :)) of the Riemann rearrangement theorem is an easy proof that the set of permutations on is uncountable: the rearrangements of any conditionally convergent sequence correspond to permutations of the natural numbers, and a rearrangement of the harmonic series can be found that sums to any real number, so there is an onto mapping from the set of permutations of the natural numbers to the real numbers. Beats diagonalization arguments any day.

I’ve been doing a lot less reading than I intended to, but lately I’ve been focusing what willpower I have at looking at Ward Cheney’s book “Analysis for Applied Mathematics”. I’ve been skipping about, skimming whatever catches my attention; fortunately, he writes in neat packets which can be digested in such a manner. The first thing I read (well, skimmed) was his discussion of a homotopic method used to solve linear programming problems with equality constraints– this all boils down to some clever matrix manipulations that really don’t have much to do with homotopy, but it’s still nice to see that such a practical algorithm can be derived from such a seemingly abstract concept.

Today, I read and reconstructed his proof of the Hahn-Banach theorem with great pleasure: his is a much clearer exposition than the one provided by Folland, which introduced me to the theorem. Whereas, if I recall correctly, Folland starts off by proving a mysterious inequality and then shows that it implies the extension theorem, Cheney does an excellent job of motivating the inequality, and the proof naturally falls out along the way. Also, Folland uses sups and such as an integral part of his argument, while Cheney avoids limit arguments except for at one crucial point, where the limiting argument is so obvious that it wasn’t until I was reconstructing his argument that I noticed the omission.

My latest task has been to look at a formula Bernard derived which measures the error in using a given FIR filter to predict the values of a certain type of random field. In the code, we’ve been using least squares prediction– just calculating the relevant quantities for a given type of tissue, and solving the normal equations to get the filter taps– but this was without justification. Or at least Papadakis seems to think it is (at least, that is the only reason I see for asking me to look at the formula). I think it is perfectly justified: after all, the first step in getting the normal equations is to write an error expression, and then find the coefficients which minimize them; this assumes only that the field is wide sense stationary (which we do).

To set the stage, let be the power spectral density (fourier transform of the autocorrelation sequence) of the random field, and let be a trigonometric polynomial of ‘length’ with all real coefficients . Since this trig poly is really just the fourier transform of the filter tap sequence, we are assuming implicitly that our filter is symmetric () and real. The error expression he derived is

But, if you consider as a function of the filter taps and minimize it accordingly, you get equations

which look suspiciously like Parseval’s equality applied to the usual normal equations. They aren’t quite the normal equations, (there’s a term mysteriously missing from under the right hand integral), but they are pretty close.

I came across these two problems this week; they’re both pretty neat. The first is to show that any positive matrix can be represented as a polynomial in terms of . The second is to show that if is a sequence of unitary matrices, then there is a subsequence satisfying for each , and is unitary. Contrary to first appearances, I think the first one is conceptually trickier than the second; but they’re both essentially one-liners.