Least Squares: Fit for the Future

Lead Research Organisation: STFC - Laboratories
Department Name: Scientific Computing Department

Abstract

This project seeks to develop new algorithms, supporting theory and software for solving least squares problems that arise in science, engineering, planning and economics. Least squares involves finding an approximate solution of overdetermined or inexactly specified systems of equations. Real-life applications abound. Weather forecasters want to produce more accurate forecasts; climatologists want a better understanding of climate change; medics want to produce more accurate images in real time; financiers want to analyse and quantify the systematic risk of an investment by fitting a capital asset pricing model to observed financial data. Finding the 'best' solution commonly involves constructing a mathematical model to describe the problem and then fitting this model to observed data. Such models are usually complicated; models with millions of variables and restrictions are not uncommon, but neither are relatively small but fiendishly difficult ones. It is therefore imperative to implement the model on a computer and to use computer algorithms for solving it. The latter task is at the core of the proposed activities.

Nearly all such large-scale problems exhibit an underlying mathematical structure such as sparsity. That is to say, the interactions between the parameters of a large system are often localised and do not involve any direct interaction between all the components. To solve the systems and models represented in this way efficiently involves developing algorithms that are able to exploit these underlying 'simpler' structures, which often reduces the scale of the problems, and thus speeds up their solution. This enterprise commonly leads not only to new software that implements existing methods, but to the creation of new theoretical and practical algorithms. At the other extreme, some problems involve interaction between all components, and while the underlying structure is less transparent, it is nonetheless present. In these cases, the computational burden may be very high and such problems may generally only be solved by sophisticated use of massively parallel computers.

The methods we will develop will aim to solve the given problem efficiently and robustly. Since computers cannot solve most mathematical problems exactly, only approximately, a priority will be to ensure the solution obtained by applying our algorithms is highly accurate, that is, close to the 'true' solution of the problem. But it is also vital that we solve problems fast without sacrificing accuracy; this is particularly true if a simulation requires us to investigate a large number of different scenarios, or if the problem we seek to solve is simply a component in an overall vastly more complicated computation, or if new data arrives in real time and we need to adapt the model accordingly. Developing algorithms that are both fast and accurate on multicore machines presents a key challenge.

We aim to improve upon existing algorithms from several different angles, exploiting new mathematical techniques from areas such as optimization and the solution of partial differential equations. Parallelism will be designed into our new algorithms, allowing modern computer hardware to be exploited. These generic improvements will be coupled with the development of new techniques to exploit special features of problems from important application areas, including X-ray microscopy, crystallography and radiative transfer modelling.

Our new software will be made available through the internationally renowned mathematical software libraries HSL, GALAHAD and SPRAL. These are extensively used by the scientific and engineering research community in the UK and abroad, as well as by some commercial companies. Since 2010, more than 50 UK university departments have used HSL for teaching or research in a wide range of disciplines that includes computational chemistry, engineering design, fluid dynamics, portfolio optimization, and circuit theory.

Planned Impact

The method of least squares is a commonly-used approach to finding an appropriate solution of overdetermined or inexactly specified systems of equations. Since its development in the eighteenth century, the solution of least squares problems has been and continues to be a fundamental method in scientific data fitting. As reported in the headline article in a recent edition of Nature (514, 29 October 2014), Marquardt's SIAM 1963 paper (SIAM. J. App. Math, 11(2)) on methods for nonlinear-least squares is one of the one hundred most-cited papers of all time, which is an indicator of the importance of the area. Least squares solvers are used across a wide spectrum of disciplines in both academia and industry, for everything from simple curve fitting, through the estimation of satellite image sensor characteristics, data assimilation for weather forecasting and for climate modelling, to powering internet mapping services, exploration seismology, NMR spectroscopy, medical imaging, aerospace systems, and neural networks. Thus the range and number of potential beneficiaries is vast, including not only the computational scientists and engineers engaged in these areas but also the people and industries that exploit them. Ultimately this includes those in government involved in making policy decisions on areas such as climate change, as well as the public through, for example, better weather forecasts and advances in medical imaging. An integral part of this project will be ensuring our work has a significant impact on a wide range of application areas.

Among this wide variety of practical applications, important guidance (in the form of test data and interaction with users) will initially come from our local collaborators (Diamond Light Source, STFC-ISIS and RAL Space) and will be in areas such as X-ray microscopy, crystallography, the analysis of neutron scattering and muon spectroscopy data, and radiative transfer modelling.

A key means of guaranteeing impact will be the development and distribution of software. Indeed, much of the planned research will lead to the design and development of high quality open source mathematical software that implements our new algorithms. This software will be included within the Group's internationally renowned and well established mathematical software libraries HSL, GALAHAD and/or SPRAL. The software will be fully supported and maintained by the Group. It will be primarily written using standard Fortran for portability and efficiency but by providing interfaces for other languages, notably MATLAB and C, we will further widen accessibility and the potential user base.

The theoretical outcomes as well as the software will be promoted through journal publications, technical reports, conference presentations, web pages, and through an international workshop that the Group will organise during the second year of the project and that will involve application users.

Publications


10 25 50
Curtis F (2016) An interior-point trust-funnel algorithm for nonlinear optimization in Mathematical Programming
Curtis F (2016) An interior-point trust-funnel algorithm for nonlinear optimization in Mathematical Programming
Gould N (2016) A Note on Performance Profiles for Benchmarking Software in ACM Transactions on Mathematical Software
 
Description Least squares for Diamond 
Organisation DIAMOND Light Source Ltd
Department Diamond
Country United Kingdom of Great Britain & Northern Ireland (UK) 
Sector Academic/University 
PI Contribution We have tested new least squares software that we have been developing under the grant on problem data provided by Diamond. Results have been shared with Diamond.
Collaborator Contribution Diamond has provided data and has been involved in a number of project meetings to plan possible future work.
Impact Outputs are still preliminary.
Start Year 2016
 
Description Least squares for Mantid 
Organisation Science and Technologies Facilities Council (STFC)
Department ISIS Facility (Rutherford Appleton)
Country United Kingdom of Great Britain & Northern Ireland (UK) 
Sector Public 
PI Contribution The team has been working on improving the least squares solvers used by the Mantid package https://www.mantidproject.org/Main_Page We have developed new software that has been integrated into Mantid. We have also performed performance testing on new and old algorithms.
Collaborator Contribution The Mantid team provided us with training in using Mantid and with test problems. Furthermore, they have contributed to fortnightly project progress review meetings. In addition, they have provided direct funding to the team (so far, equivalent to approximately 1 FTE).
Impact New software for GALAHAD, a code package RALFit and new test problems.
Start Year 2015
 
Description Research collaboration on evaluation complexity issues for the solution of nonlinear least-squares problems 
Organisation University of Namur
Country Belgium, Kingdom of 
Sector Academic/University 
PI Contribution This is a collaboration involving Professor Coralia Cartis (Oxford) and Professor Philippe Toint (Namur). The aim is to understand the worst-case function evaluation complexity of state-of-the-art methods for solving nonlinear least-squares problems. Our research has found (i) methods that improve on current best-known estimates in the general (non-zero residual) case and (ii) achieve very fast convergence when the optimal residuals are zero.
Collaborator Contribution This has been a long-term collaboration stretching back thirty years and resulting in over sixty joint publications (with the senior author, Toint) and ten years (and twenty publications with the junior one, Cartis).
Impact See publication and software lists
 
Description Research collaboration on evaluation complexity issues for the solution of nonlinear least-squares problems 
Organisation University of Oxford
Department Department of Oncology
Country United Kingdom of Great Britain & Northern Ireland (UK) 
Sector Academic/University 
PI Contribution This is a collaboration involving Professor Coralia Cartis (Oxford) and Professor Philippe Toint (Namur). The aim is to understand the worst-case function evaluation complexity of state-of-the-art methods for solving nonlinear least-squares problems. Our research has found (i) methods that improve on current best-known estimates in the general (non-zero residual) case and (ii) achieve very fast convergence when the optimal residuals are zero.
Collaborator Contribution This has been a long-term collaboration stretching back thirty years and resulting in over sixty joint publications (with the senior author, Toint) and ten years (and twenty publications with the junior one, Cartis).
Impact See publication and software lists
 
Description Research collaboration on sparse linear systems and sparse least squares 
Organisation Academy of Sciences of the Czech Republic
Country Czech Republic 
Sector Learned Society 
PI Contribution This is a research collaboration with Professor Miroslav Tuma (Charles University and Academy of Science of the Czech Republic). Scott and Tuma have worked together (and continue to work together) on developing new efficient and robust preconditioners for sparse symmetric linear systems and sparse least squares problems. Scott visits Prague approximately once each year for a week to push the project forwards and to set new goals for future work.
Collaborator Contribution Professor Miroslav Tuma visits Rutherford Appleton Lab. each year to collaborate with Scott. He funds this through grants from the Czech Republic. He also hosts visits by Scott (providing office space etc).
Impact A number of publications have been written; these are listed in the relevant sections of the form. The publications are in leading numerical analysis journals. In addition, new packages have been developed for the internationally renowned HSL mathematical software library (HSL_MI28, HSL_MI30 and HSL_MI35; see http://www.hsl.rl.ac.uk/catalogue/ for details).
Start Year 2009
 
Description Research collaboration on sparse linear systems and sparse least squares 
Organisation Charles University
Department Mathematical Institute
Country Czech Republic 
Sector Academic/University 
PI Contribution This is a research collaboration with Professor Miroslav Tuma (Charles University and Academy of Science of the Czech Republic). Scott and Tuma have worked together (and continue to work together) on developing new efficient and robust preconditioners for sparse symmetric linear systems and sparse least squares problems. Scott visits Prague approximately once each year for a week to push the project forwards and to set new goals for future work.
Collaborator Contribution Professor Miroslav Tuma visits Rutherford Appleton Lab. each year to collaborate with Scott. He funds this through grants from the Czech Republic. He also hosts visits by Scott (providing office space etc).
Impact A number of publications have been written; these are listed in the relevant sections of the form. The publications are in leading numerical analysis journals. In addition, new packages have been developed for the internationally renowned HSL mathematical software library (HSL_MI28, HSL_MI30 and HSL_MI35; see http://www.hsl.rl.ac.uk/catalogue/ for details).
Start Year 2009
 
Title Incomplete factorization preconditioner for solving large sparse linear least squares problems 
Description HSL_MI35 computes an incomplete factorization preconditioner that may be used in the solution of weighted sparse linear least squares problems. 
Type Of Technology Software 
Year Produced 2016 
Impact The software is available within the HSL mathematical software library. It is freely available to academics for teaching and research purposes. A paper has been written and published (january 2017) that demonstrates the effectiveness of the software compared with state-of-the-art alternatives. It is too early to know what the take up of the software will be (9 downloads as of February 2017). Version 1.2.0 released September 2016. 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi35.html
 
Title Nonlinear least-squares examples with CUTEst 
Description CUTEst is a collection of artificial and real-life optimization test examples along with interfaces to many commonly-available optimization solvers. Recently, a large number of nonlinear least-squares examples from a variety of sources have been added. 
Type Of Technology Software 
Year Produced 2016 
Open Source License? Yes  
Impact These test examples have informed improvements to both of our nonlinear least-squares software packages (RALFit and NLS), ad consequently improved the robustness of Mantid's fitting capabilities. 
URL https://ccpforge.cse.rl.ac.uk/gf/project/cutest/wiki/
 
Title Package NLS from GALAHAD 
Description NLS is a Fortran package for solving large-scale nonlinear least-squares problems. The package provides many standard and new options, and there is an interface to the CUTEst test-problem suite. 
Type Of Technology Software 
Year Produced 2017 
Open Source License? Yes  
Impact This has acted as a prototype for RALFit, our least-squares package that has been incorporated into Mantid 
URL https://ccpforge.cse.rl.ac.uk/gf/project/galahad/scmsvn/?action=browse&path=%2Ftrunk%2Fdoc%2Fnls.pdf
 
Title RALFit: A non-linear least squares solver 
Description RALFit is a software package for solving nonlinear least-squares problems. It is written in modern Fortran, and has C and Python interfaces. 
Type Of Technology Software 
Year Produced 2016 
Open Source License? Yes  
Impact It has been incorporated into the Mantid data analysis package 
URL https://github.com/ralna/ralfit