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

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.

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.