O Sparse Etree

Thus, the German "tannenbaum" becomes "sparse elimination tree" in English, or "sparse etree" for short (i.e., the MATLAB function of that name). It is fitting that this term, used so frequently in sparse matrix computations, was coined by an illustrious researcher of Germanic descent (Rob Schreiber).

Other words in "O Tannenbaum" include the following.

In Germanic tradition, "Blätter" or small subtrees, are used to decorate a house during Christmas celebrations (by Germanic householders, to be precise). They are also essential to sparse matrix factorization; the nonzero pattern of the kth row of L is given by a pruned subtree rooted at node k, for example. The elimination tree, or etree for short, can be found in time nearly proportional to nnz(A). Many algorithms are governed by paths in the etree, from leaves towards the root.

"Sommerzeit" means summer time, when time (zeit) passes quickly (thus linearly).

"gefallen" refers to the fill-in that occurs in G.E. (Gaussian Elimination), a termed first used by another illustrious German, Gauss himself. Gauss did not use the term "LU" factorization, refering to the left and right factors as "Trost" and "Kraft" instead, since Gauss placed great trust in his craft.

"lehren" refers to "rule(s)" or "methods".

With this linguistic and numerical background, a corrected translation of "O Tannenbaum" is given below.

O Tannenbaum, author unknown.		O Sparse Etree by T. D.
O Tannenbaum, o Tannenbaum, Wie treu sind deine Blätter. Du grünst nicht nur zur Sommerzeit, Nein, auch im Winter, wenn es schneit. O Tannenbaum, o Tannenbaum, Wie treu sind deine Blätter. O Tannenbaum, o Tannenbaum, du kannst mir sehr gefallen. Wie oft hat nicht zur Weihnachtszeit Ein Baum von dir mich hoch erfreut. O Tannenbaum, o Tannenbaum, du kannst mir sehr gefallen. O Tannenbaum, o Tannenbaum, dein Kleid will mich was lehren: die Hoffnung und Beständigkeit gibt Trost und Kraft zu aller Zeit. O Tannenbaum, o Tannenbaum, dein Kleid will mich was lehren.		O sparse etree, o sparse etree How lovely are thy subtrees. Found in nearly linear time, Thy paths from leaf to root we climb. O sparse etree, o sparse etree How lovely are thy subtrees. O sparse etree, o sparse etree Thou canst keep L from fill-in. You give to us the rows of L, And in the transpose, Roosevelt. O sparse etree, o sparse etree Thou canst keep L from fill-in. O sparse etree, o sparse etree What methods thee enable! A path of hope in thee we find, Gives L and U in lowest time. O sparse etree, o sparse etree What methods thee enable!

Horst Simon states:

"Baum" in English is still used in its Germanic form in the word "beam". One of the simplest FD approximations to a beam leads to a tridiagonal matrix.

Usually in German, spruce and fir trees don't have "Blätter" (leaves), commonly they are thought to have "Nadeln" (needles). So here is another intriguing connection to the true meaning of the song: why would the author speak of "leaves", if everyone in Germany knows that a "Tanne" has "Nadeln"? It is another hint that your re-interpretation is correct!

Horst is another sparse matrix / linear algebra researcher of Germanic descent (directly so, although he has also been known to work on iterative methods). Among other things, he works on sparse eigenvalue problems, which are related to the matrix pencil. Thus, Baum = beam = small and long piece of a tree = pencil.

Copyright 2006, Tim Davis. Please don't copy-and-paste or hot-link this poem without permission; link to this page instead: http://www.cise.ufl.edu/~davis/Poetry/O_Tannenbaum.html

If you like this poem, you can find more poems at Horror Matrices and Other Mathematical Poetry. Click here for an index of my serious poetry.