Algorithms and Software for Large-Scale Sparse or Structured Systems

Lead Research Organisation: STFC - Laboratories
Department Name: Scientific Computing Department

Abstract

Our work develops tools, underlying theory and techniques, for solvinglarge-scale problems as may occur in engineering and science. Real-lifeapplications 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 large-scale 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.

Publications


10 25 50
Arioli M (2013) Generalized Golub--Kahan Bidiagonalization and Stopping Criteria in SIAM Journal on Matrix Analysis and Applications
Arioli M (2009) Discrete Interpolation Norms with Applications in SIAM Journal on Numerical Analysis
Arioli M (2013) Chebyshev acceleration of iterative refinement in Numerical Algorithms
Arioli M (2015) Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix in SIAM Journal on Scientific Computing
 
Description Perhaps one of our major advances has been the development of the multifrontal method for the solution of sparse equations. This theme has continued in the Group after the poineering work of Duff and Reid in the 1980s at Harwell.
Exploitation Route Many people have developed algorithms and codes based on our original ideas.
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Energy,Environment,Financial Services, and Management Consultancy,Transport
 
Description Our findings and resultant software distributed in the HSL library and GALAHAD have been widely used in industry.
Sector Aerospace, Defence and Marine,Chemicals,Digital/Communication/Information Technologies (including Software),Energy,Financial Services, and Management Consultancy
Impact Types Societal,Economic
 
Description STFC Laboratories (Grouped)
Amount £1,500,000 (GBP)
Funding ID EP/I013067/1 
Organisation Science and Technologies Facilities Council (STFC) 
Sector Academic/University
Country United Kingdom of Great Britain & Northern Ireland (UK)
Start