Linear Algebra and Optimization: Structure, Sparsity, Algorithms and Software

拟议的工作计划是开发算法、支持理论和软件，以解决科学、工程、规划和经济中可能出现的大规模问题。可以从我们的工作中受益的现实生活应用程序比比皆是。工程师们的目标是建造尽可能安全的桥梁。制造商在其生产流程的设计中寻求最大的效率。投资者的目标是创造出既能避免高风险，又能获得良好回报的门户型股票。实验者们感兴趣的是蛋白质是如何保存的，以及在海量数据集中发现隐藏的结构。要找到“最佳”解决方案，通常需要构建一个数学模型来描述问题。这些模型通常很复杂，而且往往规模很大，这取决于大量的参数。有数百万和数十亿变量和限制的模型并不少见，但它们都不是相对较小但极其困难的模型。因此，必须在计算机上实现该模型，并使用计算机算法来求解该模型。后一项任务是拟议活动的核心。几乎所有这样的大规模问题都表现出潜在的数学结构或稀疏性。也就是说，大系统参数之间的相互作用通常是局部性的，很少涉及所有组件之间的任何直接相互作用。例如，一个电力网络可以用一个图来表示，其中节点相当于网络中的分支，元件位于边上。该图将是稀疏的，因为大多数节点仅连接到极少的其他节点。工程结构和许多其他问题都可以用类似的图表来表示。要有效地解决以这种方式表示的系统和模型，需要开发能够利用这些潜在的“更简单”结构的算法，这通常会缩小问题的规模，从而加快解决问题的速度。这种企业通常不仅导致实现现有方法的新软件，而且导致新的理论和实践算法的创建。在另一个极端，一些问题涉及所有组件之间的交互，尽管底层结构不那么透明，但它仍然存在。例如，原子论模型可能必须考虑每个原子之间的相互作用，无论它们有多小。在这些情况下，计算负担可能非常高，而这类问题一般只能通过复杂的大规模并行计算机来解决。我们将开发的方法将旨在有效和稳健地解决给定的问题。由于计算机不能准确地解决大多数数学问题，只能近似地解决，因此当务之急是确保通过应用我们的算法获得的解决方案高度准确，即接近问题的真正解决方案。但同样重要的是，我们在不牺牲精确度的情况下快速解决问题；如果模拟需要我们调查大量不同的场景，或者如果我们寻求解决的问题只是整个复杂得多的计算中的一个组件，这一点尤其正确。在多核机器上开发既快速又准确的算法是一个关键挑战。根据这笔拨款将生产的软件将包括在国际知名的数学软件库HSL和Galahad中，学者们可以免费获得这些软件库，用于研究和教学。这些库被英国和国外的科学和工程研究社区以及一些商业公司(包括Aspentech、Wolfram Research、Ziena Optimation、Altair Engineering和IBM)广泛使用。在英国，在过去的四年里，80多个大学部门使用HSL进行教学或研究。它的应用领域包括计算化学、工程设计、流体动力学、投资组合优化、电路理论。

The proposed program of work is to develop algorithms, supporting theory and software for solving large-scale problems as may occur in science, engineering, planning and economics. Real-life applications that can benefit from our work abound. Engineers aim to build bridges that are as light as safely possible. Manufacturers seek maximum efficiency in the design of their production processes. Investors aim at creating portofolios that avoid high risk while yielding a good return. Experimentalists are interested in how proteins hold, and in detecting hidden structure in vast data sets. Finding the 'best' solution commonly involves constructing a mathematical model to describe the problem. These models are usually complicated and often large scale, depending on alarge number of parameters. Models with millions and billions 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 or sparsity. That is to say, the interactions between the parameters of a large system are often localized and seldom involve any direct interaction between all the components. For example, an electrical network can be represented by a graph where nodes are equivalent to branches in the network and components are on the edges. This graph will be sparse in as much as most nodes are only connected to very few other nodes. Engineering structures, and many other problems, can be represented by a similar graph. To efficiently solve the systems and models represented in this way 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. For example, atomistic models may have to account for interactions between each atom, however small. 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. Developing algorithms that are both fast and accurate on multicore machines presents a key challenge.The software that will be produced under this grant will be included in the internationally renowned mathematical software libraries HSL and GALAHAD, which are freely available to academics for research and teaching. These libraries are extensively used by the scientific and engineering research community in the UK and abroad, as well as by some commercial companies (including Aspentech, Wolfram Research, Ziena Optimization, Altair Engineering, and IBM). In the UK, in the last four years, more than 80 university departments have used HSL for teaching or research. The areas in which it has been employed include computational chemistry, engineering design, fluid dynamics, portfolio optimization, circuit theory.