Algorithms and Software for Large-Scale Sparse or Structured Systems

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.