A divide and conquer attack on challenging least squares problems

他的项目旨在解决科学，工程，规划和经济学中出现的具有挑战性的大规模线性最小二乘问题。最小二乘法涉及到求超定或不精确指定的方程组的近似解。现实生活中的应用比比皆是。天气预报员希望做出更准确的预报;气候学家希望更好地了解气候变化;医务人员希望在真实的时间内制作更准确的图像;金融家希望通过将资本资产定价模型与观察到的金融数据相拟合来分析和量化投资的系统性风险。寻找“最佳”解决方案通常涉及构建一个数学模型来描述问题，然后将该模型与观察到的数据进行拟合。这类模型通常都很复杂，包含数百万个变量和限制的模型并不少见，但也不是相对较小但极其困难的模型。因此，必须在计算机上实现这一模型，并使用计算机算法来解决这一问题，后一项任务是拟议活动的核心，几乎所有这类大规模问题都是稀疏的。也就是说，大系统的参数之间的相互作用是局部的，并且涉及所有组件之间有限的直接相互作用。为了有效地解决以这种方式表示的系统和模型，需要开发能够利用这些底层“更简单”结构的算法，从而减少问题的规模，允许使用并行性并加快现代计算机架构的解决方案。我们的重点将放在迭代方法，这通常是唯一可能的方法，可用于解决非常大的问题。然而，为了在可接受的步骤中获得解，通常需要将给定系统转换为具有相同解但更容易求解的另一个系统。这被称为预处理。预条件的选择是问题依赖性的，对于最小二乘问题，目前几乎没有可用的选项。因此，我们寻求开发一类新的预条件，是高效和强大的应用于大规模的最小二乘问题。我们将开发新的算法和基础理论，非常重要的是，我们将在高质量的软件中实现这些算法，这些软件将通过我们国际知名的数学软件库HSL提供。这是广泛使用的科学和工程研究界在英国和国外，以及一些商业公司。该软件还将被纳入广泛使用的PETSc套件中，以进行可扩展的计算。

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.