A divide and conquer attack on challenging least squares problems

his project seeks to solve challenging large-scale linear 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 are sparse. That is to say, the interactions between the parameters of a large system are localised and involve limited direct interactions 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, thus reducing the scale of the problems, allowing the use of parallelism and speeding up their solution on modern computer architectures.

Our focus will be on iterative methods, which are commonly the only possible class of methods that can be used to tackle very large problems. However, to obtain a solution in an acceptable number of steps, it is generally necessary to transform the given system to another one that has the same solution but is simpler to solve. This is called preconditioning. The choice of preconditioner is problem dependent and for least squares problem there are currently few options available. Thus, we seek to develop a class of novel preconditioners that are highly efficient and robust when applied to large-scale least squares problems. We will develop new algorithms and underlying theory and, very importantly, we will implement these algorithms in high quality software that will be made available through our internationally renowned mathematical software library HSL. This is extensively used by the scientific and engineering research community in the UK and abroad, as well as by some commercial companies. The software will also be incorporated in the widely-used PETSc suite of packages for scalable computation.