EPSRC Reference: 
EP/E053351/1 
Title: 
Algorithms and Software for LargeScale Sparse or Structured Systems 
Principal Investigator: 
Duff, Professor I 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computational Sci and Eng  RAL 
Organisation: 
STFC Laboratories (Grouped) 
Scheme: 
Standard Research 
Starts: 
01 October 2007 
Ends: 
30 September 2011 
Value (£): 
1,604,203

EPSRC Research Topic Classifications: 
Numerical Analysis 
Parallel Computing 

EPSRC Industrial Sector Classifications: 
Aerospace, Defence and Marine 
Chemicals 
Communications 
Financial Services 
Information Technologies 
Transport Systems and Vehicles 

Related Grants: 

Panel History: 

Summary on Grant Application Form 
Our work develops tools, underlying theory and techniques, for solvinglargescale problems as may occur in engineering and science. Reallifeapplications that can benefit from our work abound. Engineers need to beable to accurately predict the vibration frequencies of bridges for theirsafe construction. Vehicle manufacturers use computer simulations of carcrashes to correctly build the component parts. Manufacturers seek maximumefficiency in the design of their production processes. Investors aim atcreating portofolios that avoid high risk while yielding a good return.Traffic planners need to decide on the level and ways of routing trafficto minimize congestion. Governments and organizations seek to formcoalitions that best represent their interests and that would besuccessful in the bargaining that characterizes a conflict resolutionprocess. Finding the 'best' solution for such processes commonly involvesconstructing a mathematical model to describe the problem. The resultingmodels are usually complex and large scale, depending on a large number ofparameters. Models with millions and billions of variables andrestrictions are not uncommon. It is therefore imperative to implement themodel on a computer and to use computer algorithms for solving it. Thelatter task is at the core of the Group's activities.Nearly all such largescale problems exhibit an underlying mathematicalstructure or sparsity. That is to say, the interactions between theparameters of a large system are often localized and seldom involve anydirect interaction between all the components. For example, an electricalnetwork can be represented by a graph where nodes are equivalent tobranches in the network and components are on the edges. This graph willbe sparse in as much as most nodes are only connected to very few othernodes. Engineering structures, and many other problems, can be representedby a similar graph. To efficiently solve the systems and modelsrepresented in this way involves developing algorithms that are able toexploit these underlying simpler structures, which often reduces thescale of the problems, and thus speeds up their solution. This enterprise,one of the Group's specializations, commonly leads, not only to newsoftware that implements existing methods, but to the creation of newtheoretical and practical algorithms.The methods and codes we develop aim to solve the given problemefficiently, and robustly, thus allowing the software to be employed in avariety of contexts and to be run on a diverse range of computers. Sincecomputers cannot solve mathematical problems exactly, only approximately,one of our priorities is to ensure that the solution obtained by applyingour algorithms to the models is highly accurate, close to the true solution of the problem.The software the Group has been producing is part of the internationallyrenowned mathematical software libraries HSL and GALAHAD, both of whichare freely available to UK academics for research and teaching. They havebeen extensively used by the scientific and engineering research communityin the UK and abroad, as well as by some commercial companies (Aspentech,Wolfram Research, Ziena Optimization, Altair Engineering, etc.). In the UKalone, in the last four years, more than 80 different university departmentshave used HSL packages for teaching and/or research. The areas in which ourcodes have been employed span a wide range, from computational chemistryand fluid dynamics to circuit theory, and many more.

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: 
http://www.stfc.ac.uk/CSE/randd/26555.aspx 
Further Information: 

Organisation Website: 
