Least Squares: Fit for the Future

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.

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.