NAGnews 134

In this issue:

Fixing a Block of Correlations with a Shrinking Method: Mark 25 NAG Library Focus

In Mark 25 of the NAG Library we have once again extended the functionality in the area of computing the Nearest Correlation Matrix (NCM). This mini-article sheds some light on the new functionality.

In today's NAGnews we focus on an entirely new NAG Library NCM routine.

Fixing a Block of Correlations with a Shrinking Method - extract from mini-article

We turn our attention to fixing some of the elements that are known to be true correlations. Mark 25 of the NAG Library introduces a new routine, g02an, which preserves a leading block of correlations in our approximate matrix. Using the shrinking method of Higham, Strabi? and Šego, the routine finds a true correlation matrix.

G is again our input matrix and we find the smallest ? in the interval [0,1] that gives a positive semidefinite result. The smaller the ? is the closer we stay to our original matrix, and any ? preserves the leading submatrix A, which needs to be positive definite.

The example shown in the image above is from the routine documentation which finds the smallest uniform perturbation ? to G, such that the output is a correlation matrix and the k by k leading principle submatrix of the input is preserved.

Travelling Rugby Fan Problem

The Rugby World Cup is well underway here in England. So far, I have been lucky enough to witness Japan beat South Africa at the Community Stadium in Brighton and next on my list is the nail biting encounter between England and Australia at Twickenham in South West London. All this travelling got me thinking, what would be the fastest circular route to visit all the stadia hosting a Rugby World Cup game if one was lucky enough to have tickets?

The naive approach is to go to Google Maps and choose the best order yourself. However, and this is where NAG comes in, algorithms exist to solve this type of problem. In fact, this is quite a famous problem and is commonly referred to as the Travelling Salesman Problem (TSP). A good introduction to the TSP can be found here.

So what can we use instead? The NAG Library contains a routine, H03BB, which can provide an approximate solution to the symmetric TSP. I was drawn to this routine for several reason: it has recently been added to the Library in Mark 25 and it simulates an interesting physical process called annealing.

Annealing is the process of heating a metal to a certain temperature and then cooling it slowly. The reason for doing this is to remove any stresses that have developed during the original formation. On the molecular scale, energetic atoms are free to rearrange themselves into the lowest energy state. This reduces impurities in the crystalline structure.

Taken from a blog post by John Muddle, NAG Technical Sales Support Engineer. Read the entire post here.

Algorithmic Differentiation: From Runtime to Compile Time Adjoints

C++11 takes dco/c++ one step closer to an AD compiler (and works in CUDA on Linux) click here to view online

There are two main approaches to producing Adjoint codes through Algorithmic Differentiation: compile time adjoint code or runtime adjoints. Compile time code is either handwritten or produced by an AD compiler, whereas runtime adjoints are usually implemented through operator overloading and tape interpretation, e.g. dco/c++. Although the compile time approach can produce more efficient code, there is very limited compile time AD tool support for C++, and it involves keeping two separate source trees in sync.

We present a new approach based on a C++11 Metaprogram AD compiler. A simplified AD compiler is written as a C++11 metaprogram and applied to blocks of staight-line code (code with no control flow). A single source can produce passive or adjoint output. Initial results are very promising: the metaprogram adjoint code is as fast as handwritten adjoint code, and is 2x to 3x faster than tape based dco/c++.

NAG Services help PSI to improve pump station efficiency for pipelines

The PSI Group develops and integrates software for utilities, manufactures and infrastructures. A team from PSI focussing on oil and gas pipeline efficiencies, leak detection and pipeline monitoring, approached NAG to talk about mathematical approaches for an optimization problem they had. The project objective was to optimize the simultaneous operation of pumps while maintaining pressure level and flow rates. NAG experts were commissioned to improve their existing model and to reduce its computing time.

This particular pipeline scenario had been modelled as a mixed integer programming problem with tens to hundreds of variables. NAG has extensive knowledge and expertise in this area of optimization.

NAG and PSI discussed the mechanics of the existing model; some constraints were found to be redundant and new formulations were proposed to improve the speed of the solver. During this phase NAG advised on software sources for new routines, including open source and NAG Library options. A fast and stable solver was selected that met the requirements of the model and could be easily integrated into PSIs commercial applications.

Alongside this, NAG advised PSI on the use of specialised optimization modelling languages to aid the development of future models. Following this the new integrated solver was tested successfully within the new optimization model. The new solution provided PSI with substantial improvements and benefits including the reduction of computation time.

Speaking about the project, Michael Kratsch of PSI said "The increase in speed that we are now able to achieve, when solving our specific pipeline problem, was amazing and the knowledge we were given about optimization solvers, problem formulation and modelling techniques was more than we hoped for. NAG's people are a pleasure to work with and I couldn't have wished for more from any consultancy engagement".

Best of the Blog

Introducing the Team: Kathy Godwin, Quality Manager and Libraries Project Manager

In this post we introduce Kathy Godwin. In her own words Kathy keeps everyone at NAG on their toes by checking everything, how it was done, when it was done, was it done to spec, was it thoroughly and successfully tested/checked, could we have done it any better, is the customer happy, is the Developer happy, is the team happy. Read more.

Life Service Award 2015 - David Sayers

It was a pleasure to see David Sayers, NAG Honorarium, receive the award at our recent AGM. As has become customary, Professor James Davenport, Professor of Information Technology, University of Bath presented David with the award. Read more.

Training Courses & Events

NAG will be at the following exhibitions and conferences over the next few months.

NAGnews - Past Issues