Mathematica News

Bubble sort in a Mathematica pattern

2010-07-30T14:06:00.000-07:00

The Mathematica programming language has many unusual characteristics, two of which are:

Everything is an expression.
Pattern-based rewrite rules are obscenely powerful.

These kinds of characteristics are the foundation of what makes Mathematica a powerful programming language. For example, the bubble sort algorithm can be implemented in a single line without a loop in Mathematica using a single conditional rewrite rule that exchanges adjacent elements when they are out of order:

bubble[xs___, x_, y_, ys___] := bubble[xs, y, x, ys] /; x > y

This definition causes a new rewrite rule to be injected into Mathematica's global table of rewrite rules. Mathematica then applies this rule to any subexpression it sees that has the form bubble[..]. The pattern on the left side of the rule searches for a pair of adjacent arguments (x and y) to bubble where x>y. If the pattern matches then the expression is rewritten such that x and y are exchanged.

This example not only demonstrates the remarkable expressiveness of the Mathematica programming language but also some of the ensuing problems. We have no idea how efficiently Mathematica's pattern matcher will find adjacent elements that are out of order and it is unlikely that Mathematica will optimize this down to an in-place swap. Consequently, we cannot begin to predict how much time or space this function will require. A quick benchmark shows that sorting 100 small integers this way takes a whopping 0.63 seconds!

All pairs shortest paths

2010-07-30T11:38:00.000-07:00

The all-pairs shortest paths algorithm from graph theory computes the shortest paths from every vertex in a graph to every other vertex. The graph may be directed or undirected and may have weighted edges and even negative weights. The algorithm used is called Floyd-Warshall and it takes O(n³) time and O(n²) space where n is the number of vertices in the graph.

Although Wolfram Research cheekily worked this example into the Numb3rs TV show, Mathematica does not actually provide a complete implementation of the algorithm required to obtain the shortest paths but, rather, is only able to return the path lengths and further information that can be used to derive the paths themselves.

After considerable effort, we arrived at the following program to solve the all-pairs shortest paths problem for an example 1,005-vertex graph:

The errors are an unfortunate consequence of running Mathematica 7.0.1 on a two-socket 8-core 2.0GHz Intel E5405 Xeon machine because this causes half of Mathematica's kernels to die when trying to make use of parallelism (so half of the machine's power is wasted!). As you can see, the program took 13.9s to run.

Hopefully this program will help anyone else who wants to solve this problem using Mathematica.

Animations explaining Mathematica functions

2010-07-30T11:29:00.000-07:00

Here's a fun web page from Wolfram Research that has animations for a bunch of Mathematica's built-in functions.

Book review: Mathematica Cookbook by Sal Mangano

2010-07-30T11:27:00.000-07:00

O'Reilly just published a new book, the Mathematica Cookbook, about Wolfram Research's flagship product. This book contains many interesting examples from various different disciplines. Most of these are derived from freely available examples written by other people (primarily from Wolfram Research's original Mathematica Book and also the excellent Wolfram Demonstrations Project) but the author has simplified some of the programs to make them more accessible.

However, the density of the information in this book is incredibly low. Most pages are filled with superfluous Mathematica output that is often not even described in the text:

Dozens of triples on page 15.
Page 58 lists hundreds of numbers but the text does not even describe their significance.
Page 205 lists all of the words with a subset of the letters "thanksgiv".
Page 226 is raw XML data.
Pages 264-265 are solid code that renders a snowman with circles and some dots for snow (all in black and white).
Pages 303-304 are two more pages of code to plot a snowman in 3D.
Page 321 lists all of the properties in Mathematica's polyhedron database and page 322 draws 20 polyhedra before page 324 enumerates exactly the same polyhedron properties again.
Pages 334-335 enumerate image data numerically (three times).
Page 359 displays quadrant swapping with 25x more matrix elements than necessary.
Page 360 is the Fourier transform of an image and page 361 is an apparently identical one.
Page 507 lists every chemical element and page 571 lists every property of them.
Page 553 lists every property available for financial data and page 554 lists them all over again.
Page 572 contains an empty graph.
and so on...

Many pages are devoted to TreeForm plots of trees that convey no useful information, e.g. the trees drawn on page 129 in the section about red-black trees:

Would have been nice to see red and black colored nodes or even learn how to do that using Mathematica (assuming it is possible). In particular, half of page 115 is a TreeForm view so badly laid out by Mathematica that it is unreadable.

There are also some problems with the technical content itself. For example, the section on red-black trees is a simple translation from Okasaki's excellent book "Purely functional data structures". The only new functionality Sal Mangano added is a remove function but his implementation is completely wrong.

The book is chocked full of advice about optimization. This is both good and bad. Good because Mathematica users need all the help they can get with performance because Mathematica is so slow. Bad because the best advice for a Mathematica user when performance is even vaguely relevant is to ditch Mathematica in favor of a more modern tool with better performance. For example, section 14.10 "Compiling an Implementation of Explicit Trinomial for Fast Pricing of American Options" states that "You need a very fast pricer for American options" but the fastest Mathematica code given can be a whopping 960× slower than a comparably-simple F# solution. Furthermore, it turns out that this was not written by Sal Mangano (the author of the book) but by Andreas Lauschke (a Mathematica and Java consultant) and it is a translation of MATLAB code written by Ansgar Jüngel (an academic).

There are several multi-page program listings written as plain Mathematica code with embedded comments that are difficult to read (they are not even spaced out, let alone typeset properly!) instead of prose. Page 265 is a block of code, for example:

Although the book does contain a frustrating amount of blatant filler, it is very cheap (O'Reilly) and does contain several thought-provoking examples. Whether you use Mathematica or not, you'll probably learn something useful about the state-of-the-art in the Mathematica world by skimming this book. On a higher level, you will probably learn a lot more about business if you consider what this book and the army of Mathematica devotees behind it represent. After all, there is a lot of money in starting a religion!

FWIW, here are the interesting references from the book to original sources:

Interval Computations.
Sequential and parallel sorting algorithms.
Interactive data structure visualizations.
How to write a spelling corrector by Peter Norvig (of Google).
Data structures and efficient algorithms in Mathematica by Daniel Lichtblau.
Packrat parsing.
Twisted architecture by Chris Carlson.
Histogram equalization.
The Yale face database.
A tutorial on Principal Components Analysis by Lindsay I Smith.
Generatingfunctionology by Hilbert S Wilf.
Predator-Prey dynamics with type-2 functional response by Wilfried Gabriel.
Theory of Finite Element Analysis.
Finance-related Mathematica resources from Weber & Partner.