Tuesday, November 15, 2005


I'm moving to a new bat place and new bat format: Numerical Notes. This move is spurred by a combination of technical and personal considerations.

On the technical side: I mostly spend my evenings away from computer networks, which means that the times I'm most likely to take a break and blog are also the times that I'm least likely to have the connectivity to post anything. Also, I've decided that I'd really like to be able to write mathematical ideas, and it's very difficult to do that with plain HTML. The new tools give me more control.

On the personal side: I would rather correspond with my friends and family (by letters or e-mail) than broadcast news through this blog. On the other hand, essay writing to an audience -- even an unknown audience -- has proven to be a valuable way for me to clarify my thoughts. Expect further essays and computations at the new site, but not so much personal news. I hope I will be better about sending letters with that!

Thanks for reading.

Tuesday, October 04, 2005

Understanding and reviewing

In How to Solve It, Polya lists four steps for mathematical problem-solving: understand the problem, devise a plan, carry out the plan, and then look back. It seems like I spend most of my time -- or at least most of my interesting time -- in the understand the problem or the look back phases.

In some sense, I spend way more time in the phases of initial understanding and later reflection than in any of the other phases. I spend years on them! The thing is, devise a plan and carry out the plan are crucial components in solving individual problems. But figuring out a problem that's simultaneously interesting and tractable -- ah, this is not so much a matter of planning as a matter of observation.

I've already mentioned my experience with geometry: took a graduate Riemannian geometry course, felt completely bewildered, came out... and got it over the next several years in a series of ah! moments (where moments should be very loosely interpreted as time periods ranging between a second and twelve hours). I'm less sure if I've mentioned other such experiences. The time between initial exposure and any personal feeling of competence is often a couple years, at least: for linear algebra, for numerical analysis, for functional analysis, for ODEs, for PDEs... the list goes on. But what really constitutes a satisfying feeling of basic competence? I don't think it's the ability to ace an exam, or even to do difficult problems; those are side-effects at best. I've received good grades in all my mathematical courses, really; I saw stuff, I did the problems, I put together the pieces in my head, and at the end of those courses, I knew the material as well as anyone could expect. But there's a difference between knowing something at the end of a semester and knowing something so well that you can use it intuitively in a complicated argument, so well that it's not just something that you remember, but something you couldn't possibly forget.

Of course, effortless recall of mathematical concepts is no more sufficient to do interesting mathematics than effortless use of English vocabulary is sufficient to craft good prose. It's a starting point. It is, to me, the real meat of the understanding the problem phase. And to do it right either takes someone much smarter than me, or someone willing to devote years of thought -- though not continuous thought -- to really grok the concepts. Sometimes I run into people who claim expertise before they've spent the time to get to what I would consider a starting point (for whatever reason this happens more in CS than in math), and who are undone by a few simple questions. I've been in that position, too! But I feel a little bad when I see it happen to someone else, and then I see that person walk away still feeling like an expert. It's not so much that fake experts hurt others, or that they hurt the reputation of their field of expertise, though unfortunately such things do happen; but when I've met such folks, they seem to have a certain smugness which inures them to the feeling of accomplishment which only comes (for me) after years of feeling like the brain knows what's going on, but the guts haven't quite caught up.

For the record: I consider myself expert in certain aspects of numerical software development. I would grudgingly grant that I might become an expert in certain aspects of numerical linear algebra. There's no way that I'd let you call me an expert in Riemannian geometry; it's just that I've spent enough years with certain ideas floating around in my mind -- things like manifolds and atlases, differential forms and vector bundles and tensor bundles -- that I feel a certain comfort with the material. And the same is true of other things.

Looking back is just as important, and just as time consuming, as the initial effort of understanding mathematical ideas. The initial understanding and the looking back blur together. Let me give an example, one that partly inspired this whole line of thought. One of the first topics covered in a compilers class is lexical analysis: how does one break up a string like 1 + a12(b*c) into meaningful tokens, things like the number 1 or the identifier a12? The usual way of approaching this is through finite automata: one starts with regular expressions, which are translated into nondeterministic finite automata, which are then converted into deterministic automata, which are then compacted. Then you generate some executable representation of the automata -- a state table and an interpreter, perhaps -- and away you go, tokenizing files with gleeful abandon. Or maybe you just say to heck with this, and do it in an ad-hoc way, in which case you'll probably re-invent either state machines or recursive-descent parsing. For the lexer the students were required to write, we gave them a code base which was written in a recursive-descent style; but it turns out that a DFA can be converted directly into an LL(1) grammar, so... six of one, half a dozen of the other.

So all these ideas come into a seemingly simple task of chopping up a file into individual tokens. And it's all very beautiful, but it can be sort of confusing, particularly since the students were really writing an LL(1) parser (a recursive-descent type parser) before they were ever formally introduced to the ideas of LL(1) parsing. So one day, as we were walking out of section, one of my students asked why should we learn the NFA -> DFA algorithm, if we're not coding it directly, and if we there are well-established tools that will do such conversions for us? It was a fair question, but while my brain was sorting among the reasons I could give, my gut interjected. If you can understand NFA -> DFA conversion, I said, then you'll be able to understand the construction of state machines for LR(k) parsing. And you want to understand the construction of those state machines, even if you're using an automated tool; otherwise, you'll have no understanding of how to avoid conflicts when they occur. My brain agreed that this was a pretty good reason, and started to expand; but by that time the student had thanked me and we'd parted ways.

Guess what? Before he asked, I'd never really thought about it before. But it really is true. The technical point: the NFA -> DFA algorithm and the LR(1) parser construction algorithm are similar in flavor, in that both involve manipulating states that represent sets of things (sets of NFA states in one case, and sets of productions in the other). Further, you can mimic the effects of the NFA -> DFA algorithm by converting an NFA into a certain type of grammar and then generating an LR(k) parse table.

And stuff like this keeps happening! But sometimes it goes off in odd directions. I write an LL(1) parser generator, I learn something interesting about Lisp. I try to come up with a non-trivial regular expression for a class exercise, I end up reminding myself of some interesting number theory... and then wishing that I had time to go learn a bit more about analytic number theory, since I've been thinking about analytic function theory in a different context. I think about code optimization shortly after thinking about a problem in floating point error analysis, and I find myself thinking gee, I could probably write an optimizer that new my favorite floating point error analysis tricks, and was able to generate code for maximal accuracy rather than for maximal performance. Oh, so many wonderful connections there are! The best thing is that I've learned that I can mention some of these things in class, and at this point most of the students seem to understand what I've said -- and a few of them get curious enough that they start playing with the ideas and making connections and asking questions. O, brave new world, that has such people in it!

But what is this activity, really? It's not problem-solving, really, though sometimes it results in good problems. It's something of a hybrid: exploration to discover new problems, or to discover how to understand problems, followed by reflection to steer further exploration. Were I a poet, I might mention the phoenix here, with new attacks and approaches rising from the ashes of old problems. But I am not a poet, so I shan't mention the phoenix. Except I've mentioned the phoenix just in order to bring attention to what I'm not mentioning. So am I waxing poetic?

Ah, the joy of it all!

Monday, October 03, 2005

Another week in books

  • Adventures of a Mathematician (S. Ulam)

    Did I finish this two weeks ago? In any case, it was interesting to read. In addition to the autobiographical and historical comments, Ulam says a great deal about mathematics and mathematical ways of thinking. Though he sometimes mentions specific technical areas, almost all of the book is accessible to a general audience.

  • Fool's Errand (R. Hobb)

    The books in the Farseer trilogy kept me up past when I should have gone to sleep. This one did, too. But I think I will postpone picking up Golden Fool, the second book in this new trilogy. I think the bleakness of the characters is a bit overdone.

  • Forty Signs of Rain (K. S. Robinson)

    I can't think of any books by KSR that I haven't enjoyed (although Icehenge wasn't as much fun as Years of Rice and Salt, for instance). I have a few quibbles, mostly involving his description of the idea of an algorithm, but I like his cast of characters and of ideas, and I really like the writing style. There wasn't much plot, yet, but it didn't feel like a deficiency; and anyhow, I expect the plot will develop further in the other books.

    I do not think the similarity of the events in the book to current political and meteorological events is particularly coincidental.

  • The Education of Henry Adams (H. Adams)

    I haven't gotten more than thirty pages into it, but so far I've enjoyed it. There's a dry humor there that appeals to me.

  • Best American Science Writing 2005 (Edited by A. Lightman)

    Haven't started it yet, but I'm looking forward to it. I usually enjoy anthologies of popular science writing.

  • Fundamentals of Electroacoustics (Fischer)

    A short, plainly written description of different types of electromechanical interactions, and of circuit-style models of coupled electrical and mechanical systems (speakers and microphones, mostly). Translated from the German original. Why couldn't I have found this book a couple years ago? But it's on my shelf now.

  • Mathematics of Classical and Quantum Physics (F.W. Byron and R.W. Fuller)

    A Dover reprint with two volumes bound as one. Includes sections on variational calculus, Hilbert spaces and spectral theory, analytic function theory, Green's functions and integral equations, and symmetry groups. I have other books that treat most of these topics in greater detail, but many of those books make little or no useful mention of physical applications or motivations. At the same time, Byron and Fuller have written an essentially mathematical book: there are no rabbit-from-a-hat tricks (or when there are, they are preceded by an apology and a reference), and certain details which seem subject to frequent abuse in physics and engineering texts -- like the treatment of the Dirac delta -- are handled with appropriate rigor.

    An aside: I'm much better as a mathematician than as a physicist. When I think about physical effects, I tend to think of them as concrete approximations of certain mathematical abstractions; and for the most part, my intuition for the mathematical things is better than my intuition for the physical things. This is a constant source of frustration for me when I'm learning about physics, since hand-waving appeals to physical intuition generally confuse me more than they help, at least initially. Nonetheless, I like learning about physics, and about connections between mathematics and physics. Furthermore, I like to learn about mathematical and scientific history, and a great deal of mathematics has historically been inspired by descriptions of physics: the calculus of variations coming from classical mechanics, many ideas in functional analysis coming from quantum mechanics, many ideas in group theory coming from mechanical symmetries, many ideas in graph theory connecting to circuit analysis, and so on.

  • Modulated Waves (Ostrovsky and Potapov)

    I've mentioned this book before. I read the first several chapters over the course of a couple weeks a while back (early summer), and since then I've been re-reading chapters or reading new chapters as the whim or the need takes me. This, too, is a mathematical book; but like Byron and Fuller's book, it contains a nice infusion of physical ideas and applications. I picked up my copy of Ostrovsky and Potapov this weekend to compare their presentation of dispersion relations to the corresponding presentation in Byron and Fuller.

Sunday, October 02, 2005

Windows woes

I wish I had a better idea how to effectively use a Windows box at a distance. Now that my old laptop is retired, I no longer have such easy access to a Windows machine. The department has a server that I can use with rdesktop, but it's of limited usefulness: I can't run MATLAB on it to compile my codes; I can't print from it; and for security reasons, I can't access it from the wireless network.

Even were I able to get remote access to a Windows machine which was not so restricted, I know that I'd still find it an irksome thing to use. No, I don't think Windows is counter-intuitive, nor that it's immensely buggy. Since the introduction of Windows 2000, I think the operating system has become immensely more stable; and Microsoft does well enough at making most of its software usable. I just wish the system was a little less interactive!

Effective computing is largely about constructive laziness. For the compilers class for which I'm an instructor this semester, we have a lot of code that's distributed to students in compiled form. The compiled files vary from vendor to vendor, platform to platform, and version to version. So, in the spirit of constructive laziness, I wrote a build script that shuttles files back and forth between three different computers, then runs Lisp programs to generate compiled files for seven different platforms, then moves all those files to the appropriate places on the class web page.

Seven different platforms, just by typing make all! But then there's an eighth platform, which is Allegro CL 7.0 under Windows; and to produce those compiled files, I defer to the professor. It would be much more convenient for both of us if I could just add another line or two to my build file; but I don't know how to do that, and while I could probably write more code to get around the issue, it's not worth the bother.

(Incidentally, this is also a good reason for distributing programs as source code -- then you can defer to someone else the work of building the program on whatever platform is of interest! Clearly, though, this is not such a good option when you're trying to provide a student with a model solution without actually giving away all the details.)

I think it may be possible for me to run a PC emulator on my Mac laptop, and on that Windows emulator to install enough UNIX-like utilities that I can autobuild there. Also, in the unlikely event that someone reading this has experience running gcc as a cross-compiler with a Windows target, I'd like to hear about it.

Wednesday, September 28, 2005

Frequently searched questions

  1. The word you're thinking of is teetotal. It's an adjective that describes one who does not drink. It is a pun, since I prefer tea to alcohol (though I've decided a cup of cider from time to time is okay, too).
  2. There are two aspects of MATLAB EXternal interface (MEX) programming that cause most of your headaches. First: when you use the mex script, the compiler flags are set in such a way that most of the warnings are turned off. This is bad mojo. Where possible, put most of the functionality for your program into a separate file, so that you can compile it to object files (and perhaps even link it to a testing stub) without testing mex. Then use mex to link everything together. Second: mex creates dynamically loadable modules, and some of the dependency checks for those modules are not performed until load time or (if you're on OS X) possibly even until the unlinked routines are hit at run time. That's why you get errors about unresolved symbols and invalid mex files. Check the order of the libraries on your link line, and check to make sure you have all the libraries you need.
  3. You don't want to write your own eigensolver, LU factorization routine, etc. Not in C++, not in C, not in Fortran. For dense numerical linear algebra, go look at LAPACK and a good BLAS implementation (BLAS = Basic Linear Algebra Subroutines). If you're writing in C++, and you have trouble linking to a Fortran code like LAPACK, make sure you use the extern C directive in order to turn of the C++ compiler's name-mangling. If you're writing in C on most Unix-y platforms, you can call Fortran code by simply appending an underscore; e.g. call dgemm_ from C instead of dgemm. Of course, this is somewhat platform dependent. There is a C translation of LAPACK, which I was responsible for a while back, but I think it's worth the effort of learning to link to Fortran. Still, you might also check out the other packages on Netlib, to see if any of them fit your needs.
  4. For large, sparse systems, you'll want something different from what you use for dense stuff. I use Tim Davis's UMFPACK system for sparse linear solves, and ARPACK for computing eigenvalues of sparse matrices.
  5. When I wrote before about tensors and duality, the code was there purely for illustration. It is not how I would typically structure a computation, or at least it's not how I'd structure it if I wanted to run something big in a reasonable amount of time. You might check out the Matlisp bindings if you're interested in something serious.
  6. Am I really so pessimistic about my code? For those searching on crash, check out Valgrind. This tool will help you. It surely helps me.
  7. If you really are interested in code to do number-theoretic computations, check out Magma, Maxima, or perhaps Mathematica or Maple. If you want to crunch numbers, consider MATLAB, Octave, or perhaps R. There exist C++ number theory libraries, but I'm not sure how much use they'll be (unless you're trying to write a distributed code-cracking system or something -- in which case it's already been done, and you should probably use existing sources).
  8. For information on the Euler totient function, the lengths of repeating fractions, or a variety of other such things, I refer you to Eric Weisstein's Mathworld.
  9. If you want a Lisp lexer generator or LL(1) parser generator, you can grab one from my software page. But for the parser generator, you may prefer something that handles LALR grammars, and for the lexer -- why bother?

Monday, September 19, 2005

Time out for reading

Time out for reading

There is a new Half Price books in Berkeley, along Shattuck Avenue a couple blocks west of campus. Curiously, they're in the same space as the dollar store where I got some pans and utensils just after I moved to Berkeley. As part of their opening celebration, they have an additional 20% off. So I wandered in, saw some familiar faces, and picked up a few books:

  • Adventures of a Mathematician (S. Ulam) --

    This autobiographical book is the only one that I've started. There's a preface that describes Ulam's work, which covers a broader range of pure and applied mathematics than I'd realized. And I thought, excellent, this will be very interesting.

    Then I went to the Au Coquelet cafe to read the prologue and sip something warm, and I realized that this will be very interesting. This book didn't start life as an autobiography; initially, Ulam thought to write a biography of von Neumann. But (on page 5):

    When I started to organize my thoughts, I realized that up to that time -- it was about 1966, I think -- there existed few descriptions of the unusual climate in which the birth of the atomic age took place. Official histories do not give the real motivations or go into the inner feelings, doubts, convictions, determinations, and hopes of the individuals who for over two years lived under unusual conditions. A set of flat pictures, they give at best only the essential facts.

    Thinking of all this in the little plane from Albuquerque to Los Alamos, I remembered how Jules Verne and H. G. Wells had influenced me in my childhood in books I read in Polish translation. Even in my boyish dreams, I did not imagine that some day I would take part in equally fantastic undertakings.

    The result of all these reflections was that instead of writing a life of von Neumann, I have undertaken to describe my personal history, as well as what I know of a number of other scientists who also became involved in the great technological achievements of this age.

    What follows is a remarkable book, part autobiography, part biography, and part introspection on the workings of memory and of the mathematical mind.

  • The Education of Henry Adams (H. Adams) --

    I'm not sure where I first heard about this book. I think it was from reading Jacques Barzun, either Teacher in America or A Stroll with William James; that it would be from Barzun is a pretty good guess, though, since Barzun's books are usually crammed with references to books that I decide I want to read (and then quickly lose in my list). Either way, I know in advance to expect more than basic autobiography from this one.

  • Fool's Errand (R. Hobb) --

    A little lighter reading. I enjoyed the first trilogy, but every time I looked for the start to the second trilogy on the local bookshelves, I could only find the second book and on. So now I have something for the next time I feel like a novel.

Right now I'm switching back and forth between Ulam's book and the most recent SIAM Review for my evening reading. This issue of SIAM Review is a really good one, both for technical content and for style. J.P. Boyd, who has written a book on spectral methods which I've mentioned before, has an article on Hyperasymptotics and the Linear Boundary Layer Problem which is both informative and highly entertaining. To quote again:

Unfortunately, asymptotics is usually taught very badly when taught at all. When a student asks, What does one do when x is larger than the radius of convergence of the power series?, the response is a scowl and a muttered asymptotic series!, followed by a hasty scribbling of the inverse power series for a Bessel function. But of course, that's all built-in to MATLAB, so one never has to use it any more.

Humbug! ... Arithmurgy [number-crunching] hasn't replaced asymptotics; rather, number-crunching and asymptotic series are complementary and mutually enriching.

The article refers several times to a longer article (98 pages) entitled The Devil's invention: Asymptotics, superasymptotics, and hyperasymptotics, which I think I would have to put on my reading list just for the title, even if I didn't know that I found the author so entertaining. But given the state of my reading list right now, perhaps it will have to go onto the longer list rather than the shorter one.

Most of my reading time recently has gone to technical material (excepting Tools for Teaching by B. Davis, which is the textbook for the teaching course). This is unfortunate, because what I read tends to strongly influence what things I think about for casual conversation. So if I'm only reading about number theory, Gershgorin disks, and the error analysis of non-self-adjoint PDE eigenvalue problems, I tend to end up talking about those things to anyone who will listen. Those topics are really cool, and I do have buddies who are willing to go have a coffee, or a cider and some pizza, and have a conversation that wanders in and out of technical realms. Nevertheless: a little light reading in the evenings seems to make conversations in the day go more smoothly.

Multiples of q

You probably learned this trick in grade school: to see whether a number is divisible by three, add all the digits and check if the sum is divisible by three. The same thing works for nine. Ever wonder why?

Actually, three and nine are just special cases of something very general. What does it mean if q divides n evenly? It means that there is ultimately no remainder in the division. So if r represents the remainder at each step of long division, then I should be able to write

  r = 0
  for d = digits
    r = mod(r * 10 + d, q)

If r = 0 at the end of the loop, then the number represented by the given string of digits is evenly divisible by q. Now, it's not too difficult to show that I could rewrite the update of r as

  r = mod(r * (10 + k * q) + d, q)

for any integer k. In particular, this means that I could let p = mod(10,q), and write the update formula as

  r = mod(r * p + d, q)

The trick with division by three and division by nine works because mod(10,3) = mod(10,9) = 1.

Once you realize how this works, you can think of quick checks for all sorts of divisibility properties. For example, take the number 86834; is it evenly divisible by 11? Yes! I can tell because 10 and -1 are equivalent modulo 11, so that my remainder update looks like

  r = mod(-r + d, 11)

I can thus check divisibility by 11 by looking at alternating sums of the digits. So since 8 - 6 + 8 - 3 + 4 = 11 is divisible by 11, so also is 86834. Or if I wanted to know whether a number written in octal (base 8) was divisible by 7, I could add the octal digits and see whether seven divided the sum.

Or I could play around for five minutes to find that the binary representation of any multiple of three matches the regular expression

  (0 | 1 (00)* (1|01))*

Hooray! A meaningful regular expression which isn't absolutely trivial to parse! So such toy problems in number theory not only amuse me, but they also actually serve some use as a source of exercises for my students. We'll see whether any of them appreciate the entertainment value as I do.

  • Currently drinking: Mint tea

Friday, September 16, 2005


A friend pointed out this, which I think is one of the most entertaining uses of GIF animation that I've seen in a long time.