Linear Algebra and Optimization: Structure, Sparsity, Algorithms and Software

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

Abstract

The proposed program of work is to develop algorithms, supporting theory and software for solving large-scale problems as may occur in science, engineering, planning and economics. Real-life applications that can benefit from our work abound. Engineers aim to build bridges that are as light as safely possible. Manufacturers seek maximum efficiency in the design of their production processes. Investors aim at creating portofolios that avoid high risk while yielding a good return. Experimentalists are interested in how proteins hold, and in detecting hidden structure in vast data sets. Finding the 'best' solution commonly involves constructing a mathematical model to describe the problem. These models are usually complicated and often large scale, depending on alarge number of parameters. Models with millions and billions of variables and restrictions are not uncommon, but neither are relatively small but fiendishly difficult ones. It is therefore imperative to implement the model on a computer and to use computer algorithms for solving it. The latter task is at the core of the proposed activities.Nearly all such large-scale problems exhibit an underlying mathematical structure or sparsity. That is to say, the interactions between the parameters of a large system are often localized and seldom involve any direct interaction between all the components. For example, an electrical network can be represented by a graph where nodes are equivalent to branches in the network and components are on the edges. This graph will be sparse in as much as most nodes are only connected to very few other nodes. Engineering structures, and many other problems, can be represented by a similar graph. To efficiently solve the systems and models represented in this way involves developing algorithms that are able to exploit these underlying 'simpler' structures, which often reduces the scale of the problems, and thus speeds up their solution. This enterprise commonly leads not only to new software that implements existing methods, but to the creation of new theoretical and practical algorithms. At the other extreme, some problems involve interaction between all components, and while the underlying structure is less transparent, it is nonetheless present. For example, atomistic models may have to account for interactions between each atom, however small. In these cases, the computational burden may be very high and such problems may generally only be solved by sophisticated use of massively parallel computers.The methods we will develop will aim to solve the given problem efficiently and robustly. Since computers cannot solve most mathematical problems exactly, only approximately, a priority will be to ensure the solution obtained by applying our algorithms is highly accurate, that is, close to the 'true' solution of the problem. But it is also vital that we solve problems fast without sacrificing accuracy; this is particularly true if a simulation requires us to investigate a large number of different scenarios, or if the problem we seek to solve is simply a component in an overall vastly-more-complicated computation. Developing algorithms that are both fast and accurate on multicore machines presents a key challenge.The software that will be produced under this grant will be included in the internationally renowned mathematical software libraries HSL and GALAHAD, which are freely available to academics for research and teaching. These libraries are extensively used by the scientific and engineering research community in the UK and abroad, as well as by some commercial companies (including Aspentech, Wolfram Research, Ziena Optimization, Altair Engineering, and IBM). In the UK, in the last four years, more than 80 university departments have used HSL for teaching or research. The areas in which it has been employed include computational chemistry, engineering design, fluid dynamics, portfolio optimization, circuit theory.

Planned Impact

The need to solve linear systems and optimization problems lies at the heart of a huge range of problems within science, engineering, industry and commerce. Thus there is potentially a wide spectrum of beneficiaries for the proposed program of work, both within academia and within industry. Industries such as aerospace (optimal design of aeroplane components subject to flow constraints), utilities (power generation subject to Kirchhoff or similar continuous mass-balance laws) and finance (parameter fitting to Black-Scholes or similar models) are obvious target audiences for the software the Group will develop. Other application areas are numerous and include oil extraction from porous media, heart pump design, medical imaging, wake vortex minimization, weather forecasting, optimal structure design and free-material optimization. The potential impact of the grant is thus significant with regard to science and industry and also for wealth creation and improvements in the quality of life. Much of the planned research will lead to the development of high quality mathematical software. This software will be included within the Group's well-established software libraries HSL and/or GALAHAD, both of which are fully supported and maintained. These internationally renowned libraries are freely available for academic research and teaching purposes and are available under licence to industry. Developing reliable, well-documented code based on sound numerical methods takes months and sometimes years to build; because a four-year grant is sought, we will be able to carry out the theoretical work, develop the high-quality software and make it available within the timescale of the grant. We will continue to develop our software using standard Fortran; comprehensive testing using a number of modern software tools on a range of platforms using a variety of Fortran compilers will ensure the packages are efficient, robust and portable. We will increasingly aim to produce interfaces for other languages, notably Matlab and C, further widening accessibility and the potential user base. Building on the experience the Group has gained in recent years of distributing academic licences via the web, for commercial users, evaluation licences for individual packages will be available via the Group's webpages. To encourage potential users to try out our software, there will be no charge for three-month evaluation licences. To facilitate the purchase of licences for non-academic in-house research, our intention is that standard (non-incorporation) licences will also be made available on the web. Incorporation licences (which will allow the licensee to include one or more HSL or GALAHAD packages in a product that is then sold or distributed to third parties) will be negotiated on an individual basis in partnership with STFC Innovations Ltd.

Publications


10 25 50
Amestoy P (2015) Parallel Computation of Entries of ${A}^{-1}$ in SIAM Journal on Scientific Computing
Arioli M (2013) Stopping Criteria for Adaptive Finite Element Solvers in SIAM Journal on Scientific Computing
Arioli M (2015) Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix in SIAM Journal on Scientific Computing
Arioli M (2013) Generalized Golub--Kahan Bidiagonalization and Stopping Criteria in SIAM Journal on Matrix Analysis and Applications
Arioli M (2013) Chebyshev acceleration of iterative refinement in Numerical Algorithms
Bai Z (2011) Preface in Linear Algebra and its Applications
Barker A (2016) A Fast Solver for an H1 Regularized PDE-Constrained Optimization Problem in Communications in Computational Physics
 
Description The key objective of this work was the development of algorithms, supporting theory and software for solving large-scale problems as occur frequently in science, engineering and economics.

The algorithms and the theory that we have developed are discussed in our publications; the software has been made available through the internationally renowned mathematical software libraries HSL and GALAHAD. In addition, we have started a new library called SPRAL (Sparse Parallel Robust Algorithms Library). SPRAL is an open-source library for sparse linear algebra and associated algorithms.
Exploitation Route As the software is available (and is fully documented and maintained) it is straightforward for others to use it. We are now taking the ideas forward into other packages (some with collaborators elsewhere), further enhancing the HSL library for both academic and commercial users.

The research leading to our findings has been partially responsible for securing funding by the European
Union's Horizon 2020 research and innovation program under grant agreement number 671633.

Note that the source code for our software is made available and so others can use ideas from the codes in their own development work. This is important in the complex area of sparse matrix software.
Sectors Aerospace, Defence and Marine,Chemicals,Construction,Creative Economy,Digital/Communication/Information Technologies (including Software),Energy,Environment,Financial Services, and Management Consultancy,Transport,Other
URL http://www.scd.stfc.ac.uk/SCD/44240.aspx
 
Description Much of the research carried out under this project has led to the development of mathematical software which is available through the HSL, GALAHAD and/or SPRAL libraries. These are fully supported and maintained libraries that are developed by the NA Group at RAL. Users from a wide range of disciplines have downloaded the software. The sparse direct linear solvers are widely used for solving large sparse linear systems of equations which arise in numerous applications, both in their own right and as subproblems. Many of our users are academics but we also have a number of users from industry. These include F1 teams (Redbull and Mercedes), water industries, finance (through inclusion of one of our solvers in a package developed by NAG Ltd for financial customers), and animation (we may not disclose the name).
First Year Of Impact 2012
Sector Aerospace, Defence and Marine,Construction,Energy,Environment,Financial Services, and Management Consultancy,Other
Impact Types Societal,Economic
 
Description Mathematics responsive mode
Amount £1,500,000 (GBP)
Funding ID EP/I013067/1 
Organisation EPSRC and CRUK 
Sector Private
Country United Kingdom of Great Britain & Northern Ireland (UK)
Start 10/2011 
End 09/2015
 
Description Research collaboration on evaluation complexity issues for the solution of nonlinear least-squares problems 
Organisation University of Namur
Country Belgium, Kingdom of 
Sector Academic/University 
PI Contribution This is a collaboration involving Professor Coralia Cartis (Oxford) and Professor Philippe Toint (Namur). The aim is to understand the worst-case function evaluation complexity of state-of-the-art methods for solving nonlinear least-squares problems. Our research has found (i) methods that improve on current best-known estimates in the general (non-zero residual) case and (ii) achieve very fast convergence when the optimal residuals are zero.
Collaborator Contribution This has been a long-term collaboration stretching back thirty years and resulting in over sixty joint publications (with the senior author, Toint) and ten years (and twenty publications with the junior one, Cartis).
Impact See publication and software lists
 
Description Research collaboration on evaluation complexity issues for the solution of nonlinear least-squares problems 
Organisation University of Oxford
Department Department of Oncology
Country United Kingdom of Great Britain & Northern Ireland (UK) 
Sector Academic/University 
PI Contribution This is a collaboration involving Professor Coralia Cartis (Oxford) and Professor Philippe Toint (Namur). The aim is to understand the worst-case function evaluation complexity of state-of-the-art methods for solving nonlinear least-squares problems. Our research has found (i) methods that improve on current best-known estimates in the general (non-zero residual) case and (ii) achieve very fast convergence when the optimal residuals are zero.
Collaborator Contribution This has been a long-term collaboration stretching back thirty years and resulting in over sixty joint publications (with the senior author, Toint) and ten years (and twenty publications with the junior one, Cartis).
Impact See publication and software lists
 
Description Research collaboration on sparse linear systems and sparse least squares 
Organisation Academy of Sciences of the Czech Republic
Country Czech Republic 
Sector Learned Society 
PI Contribution This is a research collaboration with Professor Miroslav Tuma (Charles University and Academy of Science of the Czech Republic). Scott and Tuma have worked together (and continue to work together) on developing new efficient and robust preconditioners for sparse symmetric linear systems and sparse least squares problems. Scott visits Prague approximately once each year for a week to push the project forwards and to set new goals for future work.
Collaborator Contribution Professor Miroslav Tuma visits Rutherford Appleton Lab. each year to collaborate with Scott. He funds this through grants from the Czech Republic. He also hosts visits by Scott (providing office space etc).
Impact A number of publications have been written; these are listed in the relevant sections of the form. The publications are in leading numerical analysis journals. In addition, new packages have been developed for the internationally renowned HSL mathematical software library (HSL_MI28, HSL_MI30 and HSL_MI35; see http://www.hsl.rl.ac.uk/catalogue/ for details).
Start Year 2009
 
Description Research collaboration on sparse linear systems and sparse least squares 
Organisation Charles University
Department Mathematical Institute
Country Czech Republic 
Sector Academic/University 
PI Contribution This is a research collaboration with Professor Miroslav Tuma (Charles University and Academy of Science of the Czech Republic). Scott and Tuma have worked together (and continue to work together) on developing new efficient and robust preconditioners for sparse symmetric linear systems and sparse least squares problems. Scott visits Prague approximately once each year for a week to push the project forwards and to set new goals for future work.
Collaborator Contribution Professor Miroslav Tuma visits Rutherford Appleton Lab. each year to collaborate with Scott. He funds this through grants from the Czech Republic. He also hosts visits by Scott (providing office space etc).
Impact A number of publications have been written; these are listed in the relevant sections of the form. The publications are in leading numerical analysis journals. In addition, new packages have been developed for the internationally renowned HSL mathematical software library (HSL_MI28, HSL_MI30 and HSL_MI35; see http://www.hsl.rl.ac.uk/catalogue/ for details).
Start Year 2009
 
Title CUTEst 
Description CUTEst, a constrained and unconstrained testing environment (with safe threads) is the latest incarnation of the CUTE package. It enables users to compare developing and established algorithms by perfoming tests on a very large suite of realistic optimization test examples. 
Type Of Technology Software 
Year Produced 2013 
Open Source License? Yes  
Impact CUTEst is the defacto testing tool for nonlinear optimization, and is used by almost all algorithm developers to evaluate their software. 
URL http://ccpforge.cse.rl.ac.uk/gf/project/cutest/wiki/
 
Title GALAHAD 
Description G?ALAHAD is a thread-safe library of Fortran 2003 packages for solving nonlinear optimization problems. At present, the areas covered by the library are unconstrained and bound-constrained optimization, quadratic programming, nonlinear programming, systems of nonlinear equations and inequalities, and nonlinear least squares problems. Although the first release was in 2005, packages are added regularly, and the latest release incorporating outcomes from this grant was in 2015. 
Type Of Technology Software 
Open Source License? Yes  
Impact GALAHAD has been downloaded by many thousands of application programmers. For example, it performs an important role within the radiative transfer model and a retrieval algorithm SCIATRAN http://www.iup.uni-bremen.de/sciatran/ 
URL http://www.galahad.rl.ac.uk/
 
Title HSL_MA86 
Description Sparse symmetric inde?nite linear system solver using OpenMP 
Type Of Technology Software 
Year Produced 2011 
Impact Downloaded by 232 third-party users as HSL_MA86. Downloaded by 2121 third-party users as part of coinhsl package. 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_ma86.xml
 
Title HSL_MA97 
Description Sparse direct solver for symmetric indefinite problems. Focus on delivering reliable results on top of standard technologies, and including a comprehensive set of features. 
Type Of Technology Software 
Year Produced 2011 
Impact Wide-spread use through IPOPT and other more commercial optimization libraries. 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_ma97.html
 
Title HSL_MC80 
Description Matching-based ordering and scaling for sparse symmetric matrices 
Type Of Technology Software 
Year Produced 2012 
Impact Incorporated into all our linear solvers since - best solution to numerically difficult problems. Downloaded by 29 users as HSL_MC80. Downloaded by >2500 users as part of other packages. 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mc80.html
 
Title HSL_MI20 v2 
Description Unsymmetric system: algebraic multigrid preconditioner Extended to add additional functionality in 2015 
Type Of Technology Software 
Year Produced 2015 
Impact This field left blank 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi20.html
 
Title HSL_MI28 
Description Incomplete Sparse Cholesky factorization 
Type Of Technology Software 
Year Produced 2013 
Impact Downloaded by 44 users (as of Feb 2015) 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi28.html
 
Title HSL_MI29 
Description MPGMRES: an extension of GMRES which allows multiple preconditioners 
Type Of Technology Software 
Year Produced 2013 
Impact Downloaded by 28 users (as of Feb 2016) 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi29.xml
 
Title HSL_MI30 
Description Symmetric inde?nite saddle-point system: signed incomplete Cholesky factorization 
Type Of Technology Software 
Year Produced 2014 
Impact Downloaded by 13 users (Feb 2016) 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi30.html
 
Title HSL_MI32 
Description Symmetric possibly-inde?nite system: MINRES method 
Type Of Technology Software 
Year Produced 2015 
Impact Downloaded by 7 users (Feb 2016) 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi32.html
 
Title HSL_MI35 
Description Sparse least squares: incomplete factorization preconditioner 
Type Of Technology Software 
Year Produced 2015 
Impact Downloaded by 4 users (as of Feb 2016) 
URL http://www.hsl.rl.ac.uk/catalogue/hsl_mi35.html
 
Title SPRAL/SSIDS 
Description Sparse Symmetric Indefinite Solver for GPUs 
Type Of Technology Software 
Year Produced 2015 
Open Source License? Yes  
Impact First sparse direct solver to work on GPUs 
URL http://www.numerical.rl.ac.uk/spral