权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

线性代数和优化：结构、稀疏性、算法和软件

基本信息

批准号：
EP/I013067/1
负责人：
Jennifer Scott
金额：
$ 189.76万
依托单位：
Science and Technology Facilities Council
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2011
资助国家：
英国
起止时间：
2011 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FI013067%2F1
关键词：
Linear Algebra Optimization Structure Sparsity

项目摘要

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.

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