Wednesday, 9 November 2016

The New NAG Optimization Modelling Suite

Nowadays a vast majority of optimization solvers can handle very complex problems involving many variables and various types of the constraints with a different structure. Designing an interface for such a solver, which would allow a complex input without compromising the ease of use, is challenging.
A new suite of routines, the NAG Optimization Modelling Suite, has been introduced in Mark 26 of the NAG Library to tackle the input of complex problems without forming difficult interfaces with a daunting number of arguments. The suite is used by the new optimization solvers introduced at this mark; the semidefinite programming solver and the interior point method for nonlinear optimization. The suite will expand in the years to come to handle more problem types.
The main aim of the NAG Optimization Modelling Suite is the ability to define and solve various optimization problems in a uniform manner.
There are three key features of the suite. Firstly, the definition of the optimization problem and the call to the solver have been separated in such a way that the formulation of the problem is solver agnostic, i.e., the same problem can be set up in the same way for different solvers. Secondly, the problem representation is built up from basic components (for example, a QP problem is composed of a quadratic objective, simple bounds and linear constraints), therefore different types of problems reuse the same routines for their common parts. Finally, the call to the solver is notably simplified thanks to the fact that most of the information has already been provided. 
The suite can be found in Chapter E04 of the NAG Library, mainly as e04r and e04s routines. There are many examples accompanying the routines of the suite to demonstrate the best practice.  

Thursday, 20 October 2016

Calling NAG Routines from Julia

Julia Computing was founded in 2015 by the co-authors of the Julia programming language to help private businesses, government agencies and others develop and implement Julia-based solutions to their big data and analytics problems.
Julia is an open-source language for high-performance technical computing created by some of the best minds in mathematical and statistical computing.
Reid Atcheson, Accelerator Software Engineer, NAG, and Andy Greenwell, Senior Application Engineer, Julia Computing, have teamed up to ensure that NAG Library routines can be called from the Julia language. Read their piece here.

Thursday, 21 July 2016

Fortran Modernisation Workshop - An Attendee's Perspective

Jonathan Cooper, Research Lecturer, Department of Computer Science at The University of Oxford recently attended a Fortran Modernisation Workshop and has posted about the day:
This two day intense workshop covered a vast array of topics related to developing reliable computational science software in Fortran more effectively, yet still retained time for practical work trying these out and discussions between the course leaders and participants. It was attended by 31 students and staff members of the University. Wadud Miah (NAG) led the workshop, assisted in lecturing by Fatima Chami (Durham) and Kyle Fernandes (Cambridge).
Wadud began by arguing for the importance of good software engineering practices in computational science, then gave a potted history of Fortran culminating with a tour through the features in recent versions of the standard that facilitate writing good code. Sessions also covered supporting tools that enable good development practices, including a brief guest lecture from Mistral Contrastin (Cambridge) describing the CamFort program checker, which uses annotations in program comments to support checks such as consistent use of physical units.
The full list of topics included: tips for writing optimised and efficient Fortran, using the NetCDF and HDF5 scientific file formats for data sharing and efficient I/O, using GNU make to automate the build process, the pFUnit unit testing framework, code documentation with Doxygen, more reliable interoperability between C and Fortran in the latest Fortran version, an introduction to parallelism for Fortran (including using CUDA), in-memory visualisation using plplot, IEEE floating point exception handling, software verification and portability, and version control with git.
If you are interested in these topics but couldn’t make this iteration, the workshop will be repeated in multiple locations around the UK over the coming months: Southampton in July, Culham in August, London in September, and Daresbury in October. See here for full details and the up-to-date list.
Many thanks to the lecturers for providing their time for free to deliver this course, and to the Doctoral Training Centre for the venue (again at no cost). One advantage of the network of contacts that the RSDN has across Oxford is that we can often obtain suitable teaching space for free, so if there are advanced training courses that you would like to see happen, or indeed deliver, do get in touch.

Wednesday, 15 June 2016

Analysis of performance optimisation service requests: what kind of codes are we helping as part of POP CoE?

by Sally Bridgwater, NAG HPC Application Analyst

NAG is a partner in the Performance Optimisation and Productivity Centre of Excellence (POP). POP was created with the aim of boosting the productivity of EU research and industry by providing free of charge services to advise on improving the performance of high performance computing (HPC) parallel software.

The POP team consists of six partner organisations from Germany, France, Spain and the UK. Over 30 codes have applied for the POP service so far since its kick-off in October 2015. I decided to have a look into the details of what types of codes POP is working with and see if any interesting themes emerge. Since this is quite early in the project it will be useful to revisit and see how it evolves over time.

First I decided to look at what languages all of the codes were written in. From my experience in Physics, I generally assumed that Fortran was the most prevalent language in academic/scientific applications.

This seems to be the case so far in the POP project, and correlates with the larger number of academic codes that have been investigated. However, surprisingly to me, C++ is not very far behind followed closely by the combination of C & Fortran. There is a small subset of applications using Python in some form, often not as the main backbone of the application though. The “Others” includes a small number of other combinations of C, C++ and Fortran.

The most common parallelization model so far in the POP project has been hybrid MPI+OpenMP. 

This was quite surprising to me at first since this can be complicated to include in applications and often hard to get working well. However, this point may be exactly why it is seen more often by POP. Developers that are keen and interested in performance and scalability may be more likely to try it and may also be interested in seeking advice on how to best make use of it and ensure it is working efficiently; which is where POP comes in. The “Other” schemes include Java, Pthreads and GASPI.

The application areas of codes worked on shows that Engineering and Earth & Atmospheric sciences are by far the most prevalent at the moment but there is still a good breadth of subject areas which will hopefully increase as the project continues.

The POP project has funding to work with EU organization so I had a look at which country the codes came from. Since some of them are large collaborative works I chose the country of their main participant.

Germany and the UK are the largest contributors so far. This may not be surprising as NAG, based in the UK, is leading the customer finding efforts and there are three German partners on the POP team. Also Germany is one of the leading countries in the EU for engineering and HPC so this may explain the large number of engineering based applications we have worked with so far; around 60% of the engineering codes in POP are from Germany.

Looking through this data throughout the evolution of the POP project can give us an interesting view of HPC in the EU and also shows us where the POP project needs to focus more attention. For example, making sure we reach out to all EU countries equally not just the ones easiest for us. There is a wide breadth of application areas already covered by the POP project but it would be great to try and expand it even more because the service can benefit anyone in any field working with parallel code for HPC.

Friday, 3 June 2016

Improved Accessibility for NAG’s Mathematical and Statistical Routines for Python Data Scientists

By John Muddle, NAG Technical Sales Support Engineer

NAG and Continuum have partnered together to provide conda packages for the NAG Library for Python (nag4py), the Python bindings for the NAG C Library. Users wishing to use the NAG Library with Anaconda can now install the bindings with a simple command (conda install -c nag nag4py) or the Anaconda Navigator GUI.

For those of us who use Anaconda, the Open Data Science platform, for package management and virtual environments, this enhancement provides immediate access to the 1,500+ numerical algorithms in the NAG Library. It also means that you can automatically download any future NAG Library updates as they are published on the NAG channel in Anaconda Cloud.

To illustrate how to use the NAG Library for Python, I have created an IPython Notebook that demonstrates the use of NAG’s implementation of the PELT algorithm to identify the changepoints of a stock whose price history has been stored in a MongoDB database. Using the example of Volkswagen (VOW), you can clearly see that a changepoint occurred when the news about the recent emissions scandal broke. This is an unsurprising result in this case, but in general, it will not always be as clear when and where a changepoint occurs.

So far, conda packages for the NAG Library for Python have been made available for 64-bit Linux, Mac and Windows platforms. On Linux and Mac, a conda package for the NAG C Library will automatically be installed alongside the Python bindings, so no further configuration is necessary. A Windows conda package for the NAG C Library is coming soon. Until then, a separate installation of the NAG C Library is required. In all cases, the Python bindings require NumPy, so that will also be installed by conda if necessary.

Use of the NAG C Library requires a valid licence key, which is available here: The NAG Library is also available for a 30-day trial.

Tuesday, 17 May 2016

Who are the Customers of NAG's Impartial Expert HPC Consulting?

One of the questions I get asked most often while out and about in the HPC community at conferences, or visiting (prospective) customers is: "Who are your HPC consulting customers?".

The simple answer to that is most prefer to remain confidential, because they see a competitive advantage from using our HPC advice or services.

There are a few we are very proud to be able to name. For example NAG has worked with EPSRC to provide the Computational Science and Engineering Support Service as part of the HECToR national supercomputing service, and to provide independent expert advice on the technology options and procurement for the UK's national academic supercomputers (HECToR and ARCHER).

We enjoyed working with our friends at Red Oak Consulting to support the KAUST Shaheen II supercomputer procurement recently - see our joint press release.

There have been others that we have been able to name over the years. But, who are the confidential customers? Well, obviously I'm not going to be too indiscreet, but I can give some clues.

The oil and gas sector is a huge consumer of HPC, with clear articulations of the business value of exploiting HPC. In this sector, we have several active customers, including some of the worlds biggest and best-known oil companies. We are providing advice or hands-on support for technology planning, procurements, HPC software engineering and performance enhancements, HPC user support, cloud migration, and some other things, including HPC software experts permanently based on customer sites.

Internally, I lump together manufacturing, aerospace, high-tech engineering, etc. into one sector. Here, we have multiple customers, from multi-national companies to focused teams. We are mostly providing either HPC software performance services or experience-based advice on HPC technology planning and service delivery, including cloud.

Other active sectors include government/public sector/HPC centres; technology/IT companies; and finance. Life/medical sciences has not traditionally been a big sector for our HPC consulting but we have a few customer conversations there and expect this to grow over time.

Interestingly, although most customers remain totally confidential, the rules for some mean that they can be acknowledged in-person to non-competitors if we have a business reason to do so.

However, I think I will have to fall back on our marketing statistics to show the full HPC consulting experience of the NAG and Red Oak team:
  • 40+ projects in HPC strategy, procurement, or technology advice;
  • Throughout the world - UK, Europe, North America, Asia, Australia, Middle East, ...;
  • We have helped with around $1bn of customer HPC projects;
  • We have worked in academia, government and industry.
So, why do private sector and public sector organisations bring us in to help, when they often have in-house HPC expertise? Because we have experience across a diverse set of HPC users, we have genuine HPC technical expertise, and we have guaranteed independence and impartiality. That combination of experience, technical expertise and impartiality has been proven to deliver real value, reduce risks and ensure a better outcome for HPC strategy, technology, procurement and software performance projects.

I hope I've given a hint of our HPC consulting activity without being too indiscreet (if the reader is frustrated at the lack of detail then I'm probably doing a good job of respecting our clients' confidentiality wishes.)

If you are interested in more, please find me at various HPC events (e.g., ISC16 in Frankfurt in June), or via twitter (@hpcnotes), or via the NAG team:

Wednesday, 11 May 2016

Portfolio Credit Risk: New Technical Report

In the latest NAG technical report we examine the main theoretical aspects in some models used in Portfolio credit risk. We introduce the well-known Vasicek model, the large homogeneous portfolios or Vasicek distribution and their corresponding generalizations. An illustrative example considering factors following a logistic distribution is presented. Numerical experiments for several homogeneous portfolios are performed in order to compare these methods. Finally, we use the NAG Toolbox for MATLAB® for implementing prototypes of these models quickly.

We described the most widely used models for the calculation of default probabilities in portfolio credit risk. We introduced the Vasicek one-factor model and its generalization for factors following non Normal distributions. Similarly, we presented the large portfolio approximation method and we generated closed-form expressions for the so-called general loss distribution. In section 7 we provide code for the main routines used throughout this technical report. The code is not designed to be fast, but to serve as a guidance and point of departure for more elaborate implementations. Furthermore, the code can be easily extended to heterogeneous portfolios. As shown, only a few lines of code using the NAG Toolbox for MATLAB are required to implement the studied models, which makes it extraordinarily suitable for prototyping.

You can read the report here.

Wednesday, 20 April 2016

Multidimensional Improvements to the NAG Riemann Solvers

The NAG Library contains routines for solving the partial differential equations specific to compressible, ideal fluid flow. These equations are generally written in conservation law form where the conserved quantities are mass density, momentum and total energy of the fluid.  This set of equations can be solved using a finite volume technique that considers each conserved variable as a volume average over a finite volume (typically a small cube) and sums the fluxes (flow rates per unit area) computed at the faces surrounding the volume to get the total rate of change of a particular variable for that volume.

Several methods exist to solve this set of coupled equations (e.g. Flux Corrected Transport, ENO and WENO schemes, etc.). I focus here on the Godunov method where, in its simplest form, the fluxes are computed by solving a Riemann problem at the interface between two cells in the computational mesh. In such methods, appropriately limited (I do not address limiting procedures here, but see e.g. [Toro, 1999]) states left and right of a cell interface are computed. These states are assumed to be constant, discontinuous states, i.e. a Riemann problem. The Riemann problem does have an exact solution which can be used to finally compute the fluxes at the cell interface. The NAG Library possesses a routine for computing the exact solution and returning the fluxes to the user in one spatial dimension (D03PX). The NAG Library also possesses three other approximate "Riemann Solvers": Roe’s solver (D03PU), Osher’s solver (D03PV), and the HLL solver (D03PW). Descriptions of all these algorithms can be found in [Toro, 1999]. To make these routines more generally useful they should be able to handle the full set of three dimensional equations and this blog discusses the modifications to these routines to accomplish this.

In order to extend the current set of Riemann solvers to two and three dimensions, velocities in two additional spatial dimensions must be added to the set of equations describing the fluid flow. The expression for the total energy is also modified to account for these additional velocities. Each of the Riemann solvers mentioned above were modified to take these velocities into account. Each was plugged into an existing two/three dimensional fluid code that I had written earlier. It uses "Monotonic Upsteam-Centered Scheme Limiting" (MUSCL) [van Leer 1976, Toro, 1999] to compute the left and right states for input into the Riemann solver of choice. The method is formally second order in time and space. It also uses dynamic adaptive mesh refinement using the PARAMESH adaptive mesh package [MacNeice et al., 1999, 2000, Olson, 2006, Olson and MacNeice, 2005]. Since it is a multidimensional code, it requires Riemann solvers that can compute and return fluxes for the momenta in all three spatial directions. Therefore, I have produced modified versions of the Riemann solvers in the NAG Library to do this. The solvers modified are D03PX (exact), D03PU (Roe’s solver), D03PV (Osher’s solver), D03PW (HLL solver). Details of all these solvers can also be found in Toro’s book. In addition to this work, we are currently researching a range of improvements to the PDE functionality offered in the NAG Library and encourage users to discuss their requirements with us.


To test my implementations of these Riemann solvers, I have set up and run a test problem. The problem is run in two space dimensions and the domain of the problem is 0 to 40 in the x direction and 0 to 10 in the y direction. The entire domain is initially filled with fluid of density ρ = 1. and given a supersonic velocity of Mach 2.7 in the x direction. Into this flow a circular dense region (a blob) of ρ = 10 and radius 1 is inserted. The boundary conditions are set to produce a constant inflow of Mach 2.7 at the x = 0 boundary and outflow at the x = 40 boundary. Reflecting boundary conditions are set at the y = 0 and y = 10 boundaries. As the simulation proceeds a bow shock forms at the front of the dense blob. The dense blob is compressed and flattened and at later times Raleigh-Taylor and Kelvin-Helmholtz instabilities form at the interface between the dense blob and the supersonic flow. In the figure below, each panel shows a different time in the evolution of the mass density of the blob as it interacts with the supersonic flow surrounding it.

Results using the modified NAG HLL solver are shown in the next set of figures. The results are virtually identical to those from the original code. The rest of the NAG Riemann solvers that I have modified give similar results.



P. MacNeice, K. M. Olson, C. Mobarry, R. de Fainchtein, and C. Packer. Paramesh: A parallel adaptive mesh refinement community toolkit. NASA Tech. Rep. CR-1999- 209483, 1999.

P. MacNeice, K. M. Olson, C. Mobarry, R. de Fainchtein, and C. Packer. Paramesh: A parallel adaptive mesh refinement community toolkit. Comput. Phys. Commun., 126: 330–354, 2000.

K. Olson. Paramesh: A parallel adaptive grid tool. In A. Deane, A. Ecer, G. Brenner, D. Emerson, J. McDonough, J. Periaux, N. Stofuka, and D. Tromeaur-Dervout, editors, ”Parallel Computational Fluid Dynamics, Theory and Applications”. Elsevier, 2006.

K. Olson and P. MacNeice. An overview of the paramesh amr software package and some of its applications. In T. Plewa, T. Linde, and G. V. Weirs, editors, ”Adaptive Mesh Refinement Theory and Applications, Proceedings of the Chicago Workshop on Adaptive Mesh Refinement Methods”, volume 41 of Lecture Notes in Computational Science and Engineering, pages 315–330. Springer, 2005.

E. F. Toro. Riemann Solver and Numerical Methods for Fluid Dynamics, A Practical Introduction. Springer, Berlin, 1999.

B. van Leer, A New Approach to Numerical Gas Dynamics, "Computing in Plasma Physics and Astrophysics", Max-Planck-Institute fur Physik, Garching, Germany, April 1976.

Tuesday, 8 March 2016

Inspiring future talent - International Women's Day

On International Women’s Day we are delighted to publish an interview with NAG Placement Student, Heather Briggs, in which she speaks about her time at school, what led her to her degree choice, and the challenges and highlights she has experienced along the way. 

Heather, can you tell us a little about your school days – which subjects were you drawn to and did you receive encouragement from your teachers to continue with these into higher education?

It started quite early for me, I went to a very small rural primary school with 5 other children in my year. I was 6 months older than the rest of my year so I was moved up quite quickly. After 4 years in the higher year group I was moved down again because the local secondary school wouldn’t accept me early but I was allowed to continue doing maths lessons with the year above until they left the school. So I was definitely inclined towards maths over any other subject from a young age, although at secondary school I enjoyed science as well. I don’t remember any specific encouragement in science but in maths I was invited as a year 10 student to attend a ‘gifted and talented’ day of lectures at Portsmouth University. The top 5 maths students in the year were invited, I remember asking my teacher before accepting whether I was actually in the top 5 or if they just wanted to take a girl. She showed me the year rankings, where I saw that I was third. I didn’t really need extra encouragement to continue with both science and maths, it was obvious to me; they were by far my best subjects. I wasn’t creative; I wanted to understand how things worked. At A level I took Physics (how the universe works), Maths, Economics (how the world works) and Psychology (how the mind works). I didn’t get on with Psychology and dropped it after a year but in the other 3 subjects I had very enthusiastic teachers who made lessons interesting and fun.

Who or what influenced your degree choice?  

I watched a lot of science fiction growing up which heavily influenced my decision to do a Physics degree, I can’t remember ever wanting to study anything else. I wanted to be like Samantha Carter, a Theoretical Astrophysicist in Stargate SG-1. My school held a careers fair when I was in year 9 (age 14) and the University of Surrey had a stand. The course that caught my eye was ‘Space Technology and Planetary Exploration’ which I thought sounded brilliant. I later found out that it was a Postgraduate Masters course but decided I wanted to go to Surrey anyway and would aim for their Physics course instead. One negative experience during my time at school took place at a compulsory appointment with the school’s Career Advisor. I told her about the Surrey course that I intended to apply for and the required entry grades to which she replied “You’ll never get onto that course, you need to aim lower”. I left the appointment in shock and promptly decided that she clearly didn’t know what she was talking about and ignored her advice entirely. Fast forward 3 years to A level results day when I achieved exactly the grades I needed to get into Surrey on the Physics with Nuclear Astrophysics course.

Tell us about your time at University; the challenges and highlights? 

I started at The University of Surrey on an MPhys course, an integrated Masters degree with a research year between the first and second half of your final year. I decided halfway through my first year that research and labs were not for me, and changed to the standard BSc course. At the time of writing this I have only completed 2 years of my degree so I think the biggest challenge I have faced thus far was getting used to the sheer amount of work involved. The majority of my first year I started the week with 4 hours of lab time in the morning and 4 hours of lectures back to back in the afternoon. 9 hours solid on campus with a 1 hour break for lunch left me feeling exhausted and a little disillusioned with the idea of a physics degree. By the second year the hours were a little more evenly spread across the week so it became easier. I think the main highlight was being the first in my circle of friends to get accepted on a work placement. Also finding out I had averaged a first on a certain set of exams when I was sure I was going to have to explain to my tutor why I had done so badly compared to previous results!

Did you have any standout role models during your time at school and University? 

I don’t know about role models as such, but my first science teacher was my Headteacher from primary school. She taught years 5 and 6 science lessons once a week. Having Mrs Dalziell as a specific science teacher at that young age combined with watching Sam save the world using Physics on Stargate, normalised seeing women in science for me. I feel this made it easier for me to ignore the perceptions and continue with the subjects I enjoyed.

When did you begin thinking about your plans post University? 

I first started thinking about what I will do after my degree when my course leader began talking about finding a work placement during my first year. But I didn’t think about it seriously until just after Christmas this year. I am now half way through my placement year, working at the Numerical Algorithms Group in Oxford, and am thinking more about what I will do after my final year. Although at this stage I still don’t really have a firm idea of what I want to do.

How did you decide on a career choice? 

I haven’t yet as I’m only halfway through my undergraduate degree. Physics is not one of those degrees that leads you towards a certain job. Physics graduates have such a wide range of options available to them, which is great. The only thing I do know is that I don’t want to pursue Physics in academia. For now I'm planning a year of further study for a PGCE (teaching qualification) but I haven't made any longer term decisions.

How did you end up at NAG?

At Surrey you are strongly encouraged to try for a placement year, even if you don’t know what you want to do. It can be a great way to help you decide what to do after University, if only to rule something out! I spent a few weeks looking through the placement database looking for interesting sounding computing related placements. For the most part I was left disappointed. I understand that it is difficult to say what a placement student might end up doing in a workplace since they are there for such a short time but most of the job descriptions were so vague they didn’t compel me to apply. Many of them only listed what the company did or the values they were looking for in a student, and didn’t feature anything about what you’d actually be working on for the year.

In comparison, NAG had a detailed description of possible projects you might work on and directed those interested to a page on their website that showed an article written by a previous placement student about her experience working there. I thought it sounded like something I could see myself doing for a year so I applied. One of the great things about the work I am doing is that it involves Fortran, the programming language we are taught as part of the Physics degree.

I only applied for one other placement, and ended up declining their interview as NAG had already offered me the job. 6 months down the line, I believe I made the right choice. There have been a few hiccups along the way due to having to move to a new city (the other placement was based very near Surrey) but it has been worth it, I’m enjoying the job and can’t believe I’m already over halfway through my year here.

Describe your role at NAG? What’s a typical day at work like? 

I am a placement student in the software Implementations team, my role title Software Engineer. My typical day involves running example programs and checking results to test different versions of the NAG Library on different systems.

What can NAG and other technical companies do to encourage more women into technology careers? 

There was an after school computer club I attended briefly while at secondary school, the Computer Club for Girls, here is a direct quote from their website* “Computer Clubs for Girls (CC4G) – a fun way to inspire and motivate 9 to 14 year old girls with, and through, ICT. Featuring girl-centric topics like music, fashion and celebrity, CC4G develops skills through games and challenges.” For starters, organisations should avoid using language such as girl-centric topics like music, fashion and celebrity! To give the organisation some credit they do appear to have rebranded to ‘TechFutureGirls’ since then and changed the content to something less stereotypical.

Maybe companies could advertise to schools what kinds of job roles are available in computing and give practical advice about how to begin coding? In addition to this schools need to broaden their subject offerings, for example the sixth form that I studied at offered ICT but not Computing at A level. The computing assignments are the part of my degree I enjoy the most and are the reason I applied for the placement here at NAG.

I had been interested in coding before university and had looked up online courses like codecademy but if you google ‘What programming language should I learn?’ you get hundreds of conflicting opinions, mainly on personal blogs and it can be overwhelming trying to figure out where to even start. I expect I would’ve taken Computing in place of Psychology had it been on offer when I made my decision on which A levels to take. Hindsight is 20/20 and I’m not sure I knew enough about it at the time to have made that decision.


If you are interested in a work placement or internship at NAG see our 'Careers at NAG' pages. NAG is committed to creating a diverse workplace. We outlined our commitment in 2015 and continue to push on in this area.

Monday, 22 February 2016

Changepoint Analysis using MongoDB and NAG4PY

Recently, I attended the Alan Tayler Day at St. Catherine’s College, Oxford, organised by the Smith Institute. One of the speakers was Dr Rebecca Killick, of Lancaster University, whose talk highlighted her collaboration with NAG that has led to the inclusion of the PELT algorithm into the NAG Library. Dr Killick's collaboration with NAG started in her student days, when she was the runner-up in the "Take Aim" competition, another event run by the Smith Institute and, this year, sponsored by NAG along with Babcock, BT, CATAPULT Satellite Applications, ESPRC, Experian, GCHQ and National Nuclear Laboratory."

The PELT algorithm, of Killick et al, is designed to detect changepoints in an ordered sequence of data, for example, a time series. A changepoint is the location in the series (or time) at which one or more properties of the sequence, such as the mean, changes. A typical example of this is the time at which the average price of a stock changes to a new average value; this is an example that we will consider in more detail later in this post. PELT is an acronym for Pruned Exact Linear Time, where pruned stands for the pruning technique applied to the data to reduce the computation cost. Exact, in this situation, stands for the nature of the search algorithm for the changepoints; it is guaranteed to find the exact minimisation of a cost function used to determine the changepoints. Finally, the algorithm is linear in time, this means that, as long as the number of changepoints grows linearly, the cost of the algorithm is linear O(n), where n is the number of data points. More information about the PELT algorithm can be found in our documentation and Killick et al. (2012).

In an IPython Notebook, which can also be accessed via NAG’s GitHub, I demonstrate how one could calculate the changepoints of a stock price that has been stored in a MongoDB database. Using the example of Volkswagen, I have shown that a changepoint occurred around the time that the news broke about the recent emissions scandal. One should be careful here and note that the reason behind a changepoint is not necessarily obvious and that changepoints may not occur where one intuitively expects them to.

For those of you who are interested, the winners of the latest Take Aim prize were Georg Maierhofer and Rachael Bonnebaigt, University of Cambridge.