point

 

 Remember me

Register  |   Lost password?

 

 

MoneyScience Financial Training: Introduction to QuantLib Development with Luigi Ballabio - September 22-24, London, UK - Further Information
GPUs, Monte Carlo Simulation and Kooderive with Professor Mark Joshi - October 29-31, London, UK - Further Information


Seeing the good for the trees

Mon, 12 Sep 2011 03:41:28 GMT

We put a lot of effort into trying to ensure that our numerical libraries are available on the platforms that are most popular with our users. For each library, this leads to a proliferation of implementations, each of which is targeted at a specific combination of compute processor, operating system and compiler. The details of current implementations are on our website - for example, here is the list for the NAG Fortran Library, which also includes download links for each implementation. Although this list - which currently features forty-nine implementations - is an impressive array (and the fruits of a great deal of careful work on the part of our implementation team), its presentation could perhaps be viewed as being tricky to navigate by those who are searching for the appropriate implementation for their particular system.

Recently I was asked if I could produce a more intelligible representation of pages like this. I was reminded initially of a decision tree, mainly because we already make use of these tools in our documentation as a way to help users select the most appropriate algorithm (or NAG routine) for the solution of their problem. For example, figure 1 shows one of the decision trees which is part of the documentation for chapter D01 of the NAG Fortran Library, which deals with numerical integration, or quadrature.

This chapter currently contains twenty-nine routines, each of which is tailor-made for a different type of problem (e.g. integrands defined as a set of points or a function, functions that contain singularities, integration intervals that are finite, semi-infinite or infinite, etc), and the decision tree guides the user to a correct choice by asking questions about their problem.

Recasting the implementation list as a decision tree (with questions such as "what platform?", "what operating system?", "what compiler?") seemed, then, to be the way forward. However, I was conscious that I didn't want something which was as as set in stone as figure 1; for one thing, I was unsure about the initial layout of my tree. I also knew that the tree would require maintenance as new implementations became available - for example, the latest release of the NAG Fortran Library is currently being made available on more platforms, and the picture (and the list) will have to be periodically updated to reflect this. In addition, because the tree only contains branching nodes (points at which the path diverges) and leaf nodes (points at which the path terminates) but no converging nodes (points at which several paths come together), it could quickly become very large, and difficult to draw by hand.

Fortunately, there are a range of options for the display of decision trees. Some of these - for example, this one and this one - also incorporate the calculation of the tree itself (for use in machine learning applications), but this isn't necessary in the present example because we already have the structure of our tree. The display of trees and graphs is an active research area (see, for example, here) and there is a variety of freely-available applications (for example this one and this one) which can be used. In the end, I chose prefuse, which is a Java-based toolkit for building interactive applications in information visualization, chiefly because their treeview demo appeared to be close to what I wanted to do.

I downloaded the prefuse distribution and, after some only limited success with the supplied build script, followed the advice of the documentation and built it from within the Eclipse IDE (more specifically, their advice was to use Eclipse "if you are a Java novice", which certainly rang a bell with me). Adapting the treeview demo to my purposes was very straightforward because the tree structure and node names are read in as an XML file whose format is very simple (there are essentially just three elements: tree, branch and leaf; these are labelled via attributes). Figure 2 is a screen shot of the treeview demo running as a Java applet in the browser, displaying the implementation information for the NAG Fortran Library (i.e., based on the information presented here).

The instructions at the bottom of the web page give the details of the applet's interface: how the user can pan, zoom and also change the orientation of the tree from its default left-to-right ordering. Clicking on any of the nodes expands the tree from that point (and collapses any expanded node at the same level) which facilitates navigation. Figure 3 shows the applet being used to determine the appropriate implementation of the NAG Fortran Library for applications built on machines having the Sun X64 architecture, and using the Sun Studio 11 compiler; its NAG product code is FLSA622DCL.

In a similar fashion, Figure 4 is a partial screenshot of the applet being used to select the correct implementation of the NAG Fortran Library for applications built on machines having the AMD64 architecture, and using the GNU Fortran compiler with the ILP64 data model; its NAG product code is FLL6A22DHL. Note that, in this screenshot, the orientation of the tree has been switched to a top-to-bottom ordering, which might be easier to navigate for some users.

The applet is currently being tested internally at NAG, but initial feedback seems to indicate that its presentation of the implementation data represents a helpful supplement to the list format which has been in use up until now.

, , , , , , , , , , , , , , , , , , , ,