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

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.