# 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

Arioli M
(2013)

*Chebyshev acceleration of iterative refinement*in Numerical Algorithms
Arioli M
(2013)

*Generalized Golub--Kahan Bidiagonalization and Stopping Criteria*in SIAM Journal on Matrix Analysis and Applications
Arioli M
(2012)

*Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method*in Computer Physics Communications
Arioli M
(2009)

*Discrete Interpolation Norms with Applications*in SIAM Journal on Numerical Analysis
Arioli M
(2015)

*Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix*in SIAM Journal on Scientific Computing
Browne P
(2012)

*A fast method for binary programming using first-order derivatives, with application to topology optimization with buckling constraints*in International Journal for Numerical Methods in Engineering
Cartis C
(2010)

*On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems*in SIAM Journal on Optimization
Cartis C
(2011)

*On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming*in SIAM Journal on Optimization
Cartis C
(2012)

*On the complexity of finding first-order critical points in constrained nonlinear optimization*in Mathematical Programming
Cartis C
(2013)

*On the Evaluation Complexity of Cubic Regularization Methods for Potentially Rank-Deficient Nonlinear Least-Squares Problems and Its Relevance to Constrained Nonlinear Optimization*in SIAM Journal on OptimizationDescription | 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 |