Algorithms and Software for Large-Scale Sparse or Structured Systems
Lead Research Organisation:
Science and Technology Facilities Council
Department Name: Computational Sci and Eng - RAL
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
(2018)
A finite element method for quantum graphs
in IMA Journal of Numerical Analysis
Arioli M
(2015)
Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix
in SIAM Journal on Scientific Computing
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
(2012)
Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method
in Computer Physics Communications
Arioli M
(2013)
Generalized Golub--Kahan Bidiagonalization and Stopping Criteria
in SIAM Journal on Matrix Analysis and Applications
Bai Z
(2009)
Numerical study on incomplete orthogonal factorization preconditioners
in Journal of Computational and Applied Mathematics
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
(2012)
An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
in IMA Journal of Numerical Analysis
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 Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization
in SIAM Journal on Optimization
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 Optimization
Cartis C
(2012)
Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization
in Optimization Methods and Software
Cartis C
(2009)
Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results
in Mathematical Programming
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
(2012)
On the complexity of finding first-order critical points in constrained nonlinear optimization
in Mathematical Programming
Cartis C
(2012)
Complexity bounds for second-order optimality in unconstrained optimization
in Journal of Complexity
Cartis C
(2013)
A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function
in Optimization Methods and Software
Dollar H
(2009)
A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows
in Numerical Linear Algebra with Applications
Duff I
(2010)
On accurate and time efficient solution of primal-mixed finite element equations in multiscale solid mechanics
in International Journal for Numerical Methods in Biomedical Engineering
Duff I
(2010)
On the Block Triangular Form of Symmetric Matrices
in SIAM Review
Fowkes J
(2012)
A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions
in Journal of Global Optimization
Gould N
(2010)
Spectral Analysis of Saddle Point Matrices with Indefinite Leading Blocks
in SIAM Journal on Matrix Analysis and Applications
Gould N
(2011)
A second-derivative SQP method with a 'trust-region-free' predictor step
in IMA Journal of Numerical Analysis
Gould N
(2010)
On solving trust-region and other regularised subproblems in optimization
in Mathematical Programming Computation
Gould N
(2013)
Trajectory-following methods for large-scale degenerate convex quadratic programming
in Mathematical Programming Computation
Gould N
(2011)
How good are extrapolated bi-projection methods for linear feasibility problems?
in Computational Optimization and Applications
Gould N
(2010)
A Second Derivative SQP Method: Local Convergence and Practical Issues
in SIAM Journal on Optimization
Gould N
(2010)
A Second Derivative SQP Method: Global Convergence
in SIAM Journal on Optimization
Gould N
(2011)
Updating the regularization parameter in the adaptive cubic regularization algorithm
in Computational Optimization and Applications
Guo X
(2011)
Semilocal and global convergence of the Newton-HSS method for systems of nonlinear equations
in Numerical Linear Algebra with Applications
Hogg J
(2013)
New Parallel Sparse Direct Solvers for Multicore Architectures
in Algorithms
Hogg J
(2010)
Design of a Multicore Sparse Cholesky Factorization Using DAGs
in SIAM Journal on Scientific Computing
Hogg J
(2012)
An efficient analyse phase for element problems
in Numerical Linear Algebra with Applications
Rees T
(2010)
Optimal Solvers for PDE-Constrained Optimization
in SIAM Journal on Scientific Computing
Reid J
(2009)
An out-of-core sparse Cholesky solver
in ACM Transactions on Mathematical Software
Reid J
(2008)
An efficient out-of-core multifrontal solver for large-scale unsymmetric element problems
in International Journal for Numerical Methods in Engineering
Reid J
(2012)
Partial factorization of a dense symmetric indefinite matrix
in ACM Transactions on Mathematical Software
Scott J
(2010)
The importance of structure in incomplete factorization preconditioners
in BIT Numerical Mathematics
Scott J
(2014)
Level-based heuristics and hill climbing for the antibandwidth maximization problem THE ANTIBANDWIDTH MAXIMIZATION PROBLEM
in Numerical Linear Algebra with Applications
Scott J
(2010)
Scaling and pivoting in an out-of-core sparse direct solver
in ACM Transactions on Mathematical Software
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 | Public |
Country | United Kingdom |
Start |