Linear Algebra and Optimization: Structure, Sparsity, Algorithms and Software
Lead Research Organisation:
Science and Technology Facilities Council
Department Name: Computational Science & Engineering
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
N I M Gould
(2012)
On the complexity of the steepest-descent with exact linesearches
Pestana J
(2016)
Null-Space Preconditioners for Saddle Point Systems
in SIAM Journal on Matrix Analysis and Applications
Rees T
(2017)
A comparative study of null-space factorizations for sparse symmetric saddle point systems
in Numerical Linear Algebra with Applications
Reid J
(2012)
Partial factorization of a dense symmetric indefinite matrix
in ACM Transactions on Mathematical Software
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
(2014)
On Signed Incomplete Cholesky Factorization Preconditioners for Saddle-Point Systems
in SIAM Journal on Scientific Computing
Scott J
(2014)
On Positive Semidefinite Modification Schemes for Incomplete Cholesky Factorization
in SIAM Journal on Scientific Computing
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). |
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 | Engineering and Physical Sciences Research Council (EPSRC) |
Sector | Public |
Country | United Kingdom |
Start | 09/2011 |
End | 09/2015 |
Description | NLAFET |
Amount | € 4,000,000 (EUR) |
Funding ID | 671633 |
Organisation | European Commission H2020 |
Sector | Public |
Country | Belgium |
Start | 11/2015 |
End | 04/2019 |
Description | Research collaboration on evaluation complexity issues for the solution of nonlinear least-squares problems |
Organisation | University of Namur |
Country | Belgium |
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 |
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 |
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 |