The NAG Library is a set of mathematical and statistical algorithms used by thousands around the world for the solution of numerical problems. Every release of the Library has included numerical code contributed by professionals working in industry and academia. These esteemed “Code Contributors” generously give their code to help others gain benefit from their expert algorithms. Each code donated is then documented, tested, maintained and supported by NAG experts and engineered to run on different software and hardware configurations. This Q&A looks into the code contribution process by interviewing members of teams that have contributed code in order to gain their insight into the activity.
Interviewees
- Christopher Mower, Msc Student University of Manchester
- Craig Lucas, NAG Senior Technical Consultant
- Edvin Deadman, NAG Accelerator Software Engineer and former University of Manchester KtP Associate
Q: Tell us a little about how the relationship with the Numerical Algorithms Group (NAG) and your team began, and how it has evolved to the present?
Craig Lucas – speaking of his role in the NAG / University of Manchester KTP project
Collaboration between the University of Manchester and NAG goes back to NAG’s roots as a university software collaboration. The parties here go back to my Ph.D., as Nick Higham was my supervisor; although Nick worked with other NAG employees, too. Knowledge transfer Partnerships (KtPs) were suggested to the school of Maths, and they are excellent ways to collaborate. As well as funding for the parties concerned, they provide a framework to work in, with regular access to the academics. The glue in the KtP was the associate who would take their academic knowledge and embed it in industry; the NAG Library in our case. We employed Edvin Deadman who very successfully carried this role out, adding over 40 new routines to the Library. After the KtP, Edvin worked for the university for 18 months and is now back at NAG, and will no doubt continue to work with Nick and colleagues in some way or another.
Edvin Deadman
In October 2011, NAG and the university of Manchester began a three-year Knowledge transfer Partnership (KtP). My role as the ‘KtP Associate’ was to implement the algorithms developed at the university by Professor Nick Higham’s Numerical Linear Algebra Group into the NAG Library.
At the end of the project, I continued to work with Nick Higham at the University of Manchester for 18 months as a post-doctoral research associate, before re-joining NAG in May 2015.
Craig Lucas – speaking of his role in the Nearest Correlation Matrix team at NAG
Development of Nearest Correlation Matrix (NCM) codes at NAG dates back to 2008 when our first routine was developed from an algorithm by Rüdiger Borsdorf during his Msc with Nick Higham. Rüdiger went on to do a Ph.D. with Nick, funded by NAG, with myself as his industrial supervisor. During this time, he wrote a new routine based on his research, and I extended the original NCM routine.
- Read more: The Code Contributors: Still More Insights on Future-proofing Algorithmic Code with the NAG Library
Our customers still needed additional functionality and, after talking to Defeng Sun, who had written the original algorithm, with Qi that Rüdiger had improved, I wrote a new one that included element-wise weights. I had some MATLAB code to start with, which was an enormous help.
Two years later, a new student of Nick’s, Natasa Strabic, started looking at a completely different shrinking algorithm for NCM. I had just met Chris Mower and, with Natasa’s help, he wrote a new routine for the Library. I later extended this for Mark 26 to allow users to fix arbitrary elements.
Christopher Mower
I first met Craig Lucas, senior technical Consultant at NAG while I was doing my Msc at the university of Manchester when he gave a talk to my class. Afterwards, I had a chat with him and explained that I was looking for work experience and something interesting to do over the summer. About a month later, I received an e-mail saying that he had found a project that might interest me, and could we meet for a chat. I met him at the University of Manchester, where we also met Natasa, who gave a presentation about a new Nearest Correlation Matrix method called shrinking to restore definiteness to approximated correlation matrices she, Professor Nicholas Higham and Vedran Sego had been working on.
Q: Why did your team choose to contribute code to the NAG Library, and how does it benefit you?
Christopher Mower
The method developed by Higham, Strabic and Sego is a novel approach to correcting indefiniteness of approximated correlation matrices. It possesses desirable properties often sought in practice and is extremely fast compared to current methods. Because of this, it made sense to contribute the routines to the NAG Library.
Being a Code Contributor has benefited me a great deal. In an ever more competitive job market, it is certainly almost necessary to have work and/or research experience when applying for a position; NAG has given me both of these. My work experience was in the summer of 2014, when I implemented a variant of the shrinking method: G02AN. The research experience came in summer 2015, when NAG sponsored my Msc dissertation, entitled Shrinking for Restoring Definiteness, and supervised by Professor Nicholas J. Higham. My dissertation is to be published in MiMs ePrint, set to appear in late 2015.
Craig Lucas – speaking of his role in the Nearest Correlation Matrix team at NAG
Our university collaborations work for all parties concerned. We have Msc students with work experience and funding, Ph.D. students demonstrating collaboration and utility of their work, the university gets funding and satisfies its need to demonstrate impact of their research council-funded work, and the NAG Library gets new routines.
Q: You contributed code as a team; can you describe how the development process worked within a group environment?
Edvin Deadman
The process would begin with the Numerical Linear Algebra Group at the University of Manchester. The output of their research would typically be combinations of peer-reviewed papers containing new algorithms, and MATLAB code used to test them. From this research output, we would choose algorithms that we believed would be useful to NAG Library users. I would then implement them in Fortran, looking out for any potential improvements that could be made, and write the accompanying documentation.
Writing a new NAG routine is far from being the longest stage of the process. That honor goes to writing the test program for the routine! Each new routine has an associated test code which performs numerous checks to make sure the routine is robust, stable and gives the expected numerical results.
Craig Lucas – speaking of his role in the NAG / University of Manchester KTP project
The KtP gave the collaboration structure. The associate was required to understand existing research (as well as contribute to ongoing work) and write the code. The code would go through NAG’s usual peer review process and the associate (Edvin) got support from the industrial supervisor, (me), and other NAG colleagues as you would expect.
Craig Lucas – speaking of his role in the Nearest Correlation Matrix team at NAG
Most of the routines mentioned here have had an academic paper and MATLAB code. A staff member at NAG then writes the Fortran, the testing code and documentation. When students have written work, they do so under the supervision of someone at NAG.
Christopher Mower
The relationship between NAG and the University of Manchester is beneficial for all involved. The Nearest Correlation Matrix project is a great example of how a number of parties can work together to achieve an end goal that benefits all in a unique and individual way. NAG adds to the increasing functionality of the NAG Library, NAG customers receive the benefit of the increased functionality, and the University is able to clearly demonstrate the impact of its research conducted by its staff and students.
Q: Could you talk a little about / describe the specific code/s that your team contributed to the Library?
Craig Lucas – speaking of his role in the Nearest Correlation Matrix team at NAG
All of the NCM routines do one thing. They take a matrix (a square and symmetric grid of numbers that are between −1 and 1, with 1’s on the diagonal) and make it a true correlation matrix mathematically. We think of the input as an approximate correlation matrix, in that it looks like one but doesn’t have the important mathematical property of being positive semidefinite (having eigenvalues that are greater or equal to zero). In practice, some inputs may not be between −1 and 1, may not be symmetric and may not have 1’s on the diagonal and the routines would fix that too.
- Read more: The Code Contributors: Still More Insights on Future-proofing Algorithmic Code with the NAG Library
The differences between them are mainly about fixing and weighting some of the original entries. Users want to apply their expert judgement. They know some entries are true and should remain unchanged. They may wish to emphasize some entries so they change less in the final output of the routines. They may also wish to strengthen the positiveness of the output, ensuring it is positive definite (that is, only has positive eigenvalue). This is important for further analysis.
So, what we provide now is a suit of routines offering users plenty of choice.
Christopher Mower
The code restores positive semidefiniteness to an indefinite approximated correlation matrix through a transformation known as shrinking. The method takes the approximate, a target correlation matrix and finds a new correlation matrix that can be thought of as a compromise between the two extremes, which in some technical sense is optimal. The compromise is found by a modified bisection method and exploits properties of positive definite matrices to elicit fast execution times.
Edvin Deadman
The routines I contributed concern matrix functions. You are probably familiar with ‘normal’ functions, such as the exponential, sine, cosine or square root of a number. Well, it turns out that it is possible to define, for example, the exponential of a matrix, too. As it happens, this turns out to be very useful in all sorts of areas of science and engineering, from finance to theoretical physics. The Numerical Linear Algebra Group at the University of Manchester has developed many new algorithms for computing functions of matrices, and it is these algorithms that I implemented for the NAG Library. We now have a comprehensive suite of matrix function routines in Chapter F01.
