EPSRC Reference: 
EP/I013067/1 
Title: 
Linear Algebra and Optimization: Structure, Sparsity, Algorithms and Software 
Principal Investigator: 
Scott, Professor JA 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computational Science & Engineering 
Organisation: 
STFC Laboratories (Grouped) 
Scheme: 
Standard Research 
Starts: 
03 October 2011 
Ends: 
02 October 2015 
Value (£): 
1,489,217

EPSRC Research Topic Classifications: 
High Performance Computing 
Numerical Analysis 
Parallel Computing 
System on Chip 

EPSRC Industrial Sector Classifications: 

Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
09 Sep 2010

Mathematics Prioritisation Panel

Announced


Summary on Grant Application Form 
The proposed program of work is to develop algorithms, supporting theory and software for solving largescale problems as may occur in science, engineering, planning and economics. Reallife 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 largescale 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 vastlymorecomplicated 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.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
