You might be an LAPACK geek if...

Here's a quiz modeled after the infamous "purity tests," except that it has nothing to do with goats and everything to do with LAPACK, the most awesome body of Fortran ever created.  Score +1 for a yes answer, 0 for a no answer, and add up the points.

n00bs:


1. Have you ever called an LAPACK routine from one of your codes?

2. Do you know what the abbreviation LAPACK stands for?


3. Do you know how to pronounce LAPACK?  (No, it's not "la" like "lalala"...)

4. Are you aware that using the reference BLAS implementation is generally a bad idea, and do you know how to seek out a better one?

"Smug LAPACK weenies"

5. Have you ever built the reference LAPACK library from the Fortran, not because you didn't know it was installed but because you (a) wanted the latest version, or (b) it wasn't available on the exotic prototype hardware which you have the misfortune of being asked to use?

6. Have you ever found and reported an actual bug in some LAPACK implementation?  (One extra point if you went to the vendor's booth at a conference specifically to report the bug.)

7. Did you learn Fortran specifically to call BLAS or LAPACK routines, because it "seems more natural" than using the CBLAS header files?

8. Do you get the math joke on the cover of the LAPACK Users' Guide?

1337 |-|/\x0rz



9. Can you explain from memory what the first three letters of "DGEQRF" mean?


10. Have you ever contributed to LAPACK code?

11. Are you an author of an LAPACK Working Note?

12. Do you belong to a UC Berkeley or UTK "lapackers" e-mail list?

Beyond the Pale

13. If somebody asks for a banded LU factorization with partial pivoting, can you tell them the LAPACK routine name without looking?

14. Do you own and proudly wear a ScaLAPACK 1.0 T-shirt?  (One extra point if you get the math joke on the front.)

15. Have you found a counterexample for convergence of an eigenvalue routine?

Scoring:
1-5:  Just starting
6-10:  Escape while you can
11-15:  Hopeless
>15:  I know exactly who you are so you'd better not skew the curve!

Modeling reality with code: Nethack

One of my secret vices is Nethack, a classic dungeon-crawl game with an ASCII user interface, in the tradition of Rogue and Angband.  (The name "nethack" refers to the game's development as a hacking project by people distributed over the Internet, and has nothing to do with the game's content.)  Nethack is a great game, despite its ludicrously primitive graphics by modern standards, for the following reasons:

• Game play is rich and complex, but intuitive.  Rules make sense (especially if you catch the allusions to myth and modern storytelling) and actions have consequences.  Almost any object or creature can and will interact with anything else. 
  
• Intelligent humor makes the perverse and random ways to suffer and die (almost) bearable.
  
• The game is so challenging that even if I skim the spoilers and play with infinite lives, I can get myself into apparently inextricable situations.  Yet, it's still enjoyable without cheats and spoilers.
  
• The display is stripped-down but suggestive.  For example, line of sight and memory interact intuitively -- both are combined into one map, which lets you fit more of the map on one screen (unlike, say, a first-person shooter, which keeps the map separate from the view). 
  

Nethack also makes a good motivating example for teaching new programmers how to model reality with code.  The game has some elements which are representative of real-life situations:

1. Agents have limited information, and may even forget things.
   
2. Things happen beyond agents' awareness.
3. Attempted actions may not succeed: luck (which may improve with skill) plays a role.  (Nethack, like most games, models luck probabilistically.)
   
4. Actions usually change the world state irreversibly.
5. Object interactions depend on the properties of all the objects involved.  (In terms of object-oriented programming, your object system needs mixins.)
   
6. Some items and creatures are unique and irreplaceable.

 It also has properties which are not representative of reality:

1. Turn-based: there is no need to manage simultaneous attempts to change the world's state.
2. Rule-based: interactions are modeled simply, with little resort to a priori physical modeling (e.g., Newton's laws).  This means interactions are not usually computationally intensive.
3. Very simple graphics.
   

These three properties make Nethack fit into a natural progression of increasingly complex situations to model.  The game belongs after explaining object-oriented programming (OOP), but before explaining concurrency.  The simple graphics let students concentrate on the algorithmic interactions (and save teaching assistants and graders a lot of trouble writing a GUI framework for them!).  These interactions are rich enough to exercise many OOP lessons, such as member and class methods, inheritance, generic (a.k.a. virtual) methods, and object factories (for uniqueness).  However, they are not generally computationally expensive, so complicated algorithms are not necessary.

The chosen programming model affects the teaching approach.  For example, probabilistic success requires pseudorandom number generation, but if the programming model is functional, the novice's mental model ("rolling a die") differs from the usual stateful implementation.  Also, the lessons learned at this stage may require correction when the model is generalized to handle real-time (instead of turn-based) interactions, since multiple agents will need to draw random numbers simultaneously (parallel pseudorandom number generation). In addition, the programming language's version of OOP may make it more or less difficult to explain how to implement object interactions.  Some (such as Common Lisp) handle mixins trivially, whereas others (Java, C++) do not.  Reliance on "design patterns" to cover the programming language's deficiencies can help students deal with languages used in industry, but may also limit their flexibility with programming languages and models.  This doesn't mean a dogmatic insistence on "the one true programming language."  It's better to understand the deficiencies of one's chosen language, and learn how to work around them, than not to recognize deficiencies at all.

Nethack offers another useful pedagogical feature:  it's well-crafted and balanced.  Playing it teaches students that making an application good comes not so much from learning new programming tricks, as from careful and laborious design and testing.   "Testing" here means both correctness ("It didn't crash"), which students experience by necessity, as well as user experience testing ("It's fun to play"), which few students experience much in an undergraduate computer science curriculum.

Making LaTeX builds faster

I do most of my home computing on a first-generation Asus Eee -- with the seven-inch screen and all (though it's hooked up to a big monitor and ergonomic keyboard -- I'd go nuts otherwise!). The little Eee is terrifically portable (only 2.2 lbs, and fits easily with fully open screen on an airplane tray) but is a bit underpowered -- mine has an Intel Celeron processor overclocked to 900 MHz, and presumably the memory bandwidth is much less than that of my workstation at work. I notice especially how underpowered the Eee is when I typeset documents with LaTeX. Of course, making the most of underpowered hardware is a great nerd exercise ;-) so I'm posting some tips about how to do that here.

The first trick I tried was to precompile the document header. This saved a little bit of time but not much. Plus, the binary format of the precompiled preamble is not portable between different versions of the LaTeX toolchain, even when running under the same OS and brand of CPU. I left it in just to save 0.4 or so seconds per document pass.

Precompiling the preamble didn't save much time, so it seemed then that processing the (100-page) document was taking most of the time. This made me think about the TeX build process. Prof. Knuth considered a build an interactive process: TeX runs, gives some warnings about overly long lines (with locations so you can correct them later), and on an error stops with a prompt for interactive editing. This was probably because at the time Knuth developed TeX, building the document was a long computation. One would want to interact with it in midstream to correct errors, rather than breaking off a build, editing, and starting the build over again. This is partly why it's so much trouble to write a good Makefile for TeX documents -- Knuth set the tools to give you a lot of feedback by default, and you're supposed to read the feedback to tell whether you need to let a tool make another pass over the document. On a fast computer, all the informative messages and warnings produced by the TeX toolchain zip by too fast to see. On my Eee, however, they don't -- which made me wonder about the expense of terminal output itself. TeX has an option ("-interaction batchmode") to turn off all the informative output. Using this brought the time for a complete build (pdflatex once, bibtex once, then pdflatex twice) down from 30 seconds to 6 seconds!

Another optimization is taking advantage of the \include and \includeonly comamnds before the document is finished. The \include command generates a .aux file for each included file. If you add all the included files in the \includeonly list once and do a complete build, then you'll generate .aux files for all the included files. This gives LaTeX references and page locations for all the files. Then, you can remove files from the \includeonly list if you're not working on them, and only build the parts of the document in which you're interested. This technique also preserves page numbers, equation numbers, and other reference-related things. I was able to optimize a single pdflatex step down from 3.5 seconds to 2.5 seconds with this technique.

The \include command has a side effect: it adds a page break after the included file. (Presumably this lets LaTeX compute page numbers without needing to regenerate the .aux file.) For shorter documents, I prefer to use \input to add files, because it doesn't create page breaks. Since I'm writing a longer document with chapters and LaTeX inserts a page break at the end of each chapter anyway, I can use \include for "chapter files" and within each chapter file, use \input to include section files. This website recommends solving the page break problem by using \include when editing, and \input when publishing, but for me, using \include for chapters reflects how I work on the document anyway.

LaTeX is missing some features that could make a build go a lot faster. First, building a document doesn't work like building a C library: compilation of individual files isn't independent of the whole build. I have a long document and I've taken the care to break it up into modular files; this helps with revision control, but LaTeX can't exploit this very effectively (other than with the \includeonly trick). Second, LaTeX must pass several times over the same document in order to get references right; in Knuth's time, this probably was meant to save memory, but now it would be nice to use more memory in order to save some passes.

Copying by hand

A couple weeks ago, I noticed in a BoingBoing post the following quote:

Before literacy, we were mere listeners. We heard stories read to us as a group. After the printing press, we were elevating to individuals, each with our own, acknowledged perspective on what we read.

I made a comment (as "hilbertastronaut"), and I feel like expanding on
it a bit more.

The writer argues that the printing press elevated us (Westerners,
perhaps?) from mere listeners to individuals with opinions. If
anything, the opposite might be true. Back when the only way to
propagate information was to copy it by hand, it was standard practice
to add commentary to the margins of the document. This could include
clarifications or even personal reflections. One sees this in Western
monastic manuscripts as well as Chinese brush paintings (where
standard practice was to indicate receipt of the painting by marking
it with one's personal stamp, and then perhaps write one's thoughts on
the piece in the margin). In contrast, the printing press (and the
Reformation in some sense) gave people the idea of a book as an
official, received text. Written comments have a lesser status than
the printed text. For example, if one buys a used textbook at a
college bookstore, one generally hopes that it hasn't been written on
much. Before the printing press, the commentary could often be equally
or more valuable than the main text itself.

Copying other kinds of information by hand besides text also has
the same effect. For example, when J. S. Bach copied Italian
concerti, he added inner voices and ornamentation, making the concerti
into pieces universally recognized as his own compositions (and
arguably more interesting than the originals!). Bach treated copying
both as an end (to get his hands on other people's music), and as a
means (to improve his compositional skills). Even today, mathematics
teachers consider copying out and working through proofs an important
part of learning mathematics. This is because mathematics, like music
composition, is not about memorization of facts but about developing
one's creative problem-solving ability according to a combination of
rules and aesthetic principles. Copying a proof and understanding
each step is a guided re-creation of the original author's work.
Furthermore, creative mathematical thinkers in this process of
re-creation usually have new things to say, like clarifications or
generalizations, which they "write in the margins" and use in their
research -- just like Bach wrote inner voices and ornamentations "in
the margins" to produce new compositions.

My sophomore high school English teacher handed out red pens on
the first day of class, and exhorted us, even required us to
write in our books with them. At the time, it seemed ridiculous to
ruin books which could be reused for the next class. Pencil
annotations could at least be erased. Now I understand that using a
red pen elevates the status of the handwritten text, to be more
visible and more permanent even than the printed text. It makes the
reader's commentary just as valuable, if not more so, than the
original document. Whether my commentary really was more valuable
than what I read at the time is doubtful, but at least the long-term
lesson of the value of "manual" commentary stuck in my head.

ImageMagick crops your white space!

ImageMagick is a fabulous command-line tool for image processing. I use it a lot for converting between different image formats, which it does with no fuss whatsoever -- as the following PNG to PDF example illustrates:

$ convert in.png out.pdf

ImageMagick can do much, much more than conversions. Today I learned the following trick from an
e-mail list discussion:

$ convert -trim img.pdf

which trims all the white space from around an image. It's a great trick for inserting Matlab plots into papers! I used to do this by hand with an image editing program like the GIMP; it's great to know that I don't have to fire up such a massive tool in order to accomplish this simple task. (The GIMP is a wonderful program, incidentally, but starting it up just to crop some white space is a task beneath its mighty powers.)

New version of ECL is out

A new version of Embeddable Common Lisp (ECL) is out!!! I use ECL in my projects to support Lisp as an embedded scripting language in large C-based projects. ECL's chief developer (Juan Jose Garcia Ripoll) is amazingly responsive, which makes the library a pleasure to use. Yay ECL!!!

(Pseudo)random numbers matter

The newly released LAPACK Working Note #206 gives yet another reason why generating good pseudorandom numbers matters:

In May 2007, a large high performance computer manufacturer ran a twenty-hour long High Performance Linpack benchmark. The run fails with the following output:

|| A x - b ||_oo / ( eps * ||A||_1 * N ) = 9.22e+94 ...... FAILED


What happened was that the benchmark's matrix generator uses a lame linear congruential pseudorandom number generator, which causes generated matrices to have repeated columns for certain unfortunate choices of matrix dimension. This of course makes one wonder why the generator doesn't just make a matrix which is known to be invertible, say, by generating a sufficiently nonzero diagonal matrix and hitting it on both sides with orthogonal transforms until the zeros are filled in. Regardless, the bug meant 20 hours of very expensive, intensely power-consuming supercomputer time were wasted on computing the wrong answer to a problem which at such sizes very few people need to solve. So, random numbers do matter ;-)