Effective preconditioners for linear systems in fractional diffusion
Lead Research Organisation:
University of Strathclyde
Department Name: Mathematics and Statistics
Abstract
Mathematical models of the diffusion of signals and particles are important for gaining insights into many key challenges facing the UK today. These problems include understanding how fluid flows through the ground, which helps to ensure that we have safe drinking water; characterising the propagation of electrical impulses through the heart, which aids our understanding of heart disease; and developing accurate models of financial processes, which improve our economy by providing better predictions of financial markets. This project focuses on so-called fractional diffusion problems, which occur when the diffusion process involves a number of different flow rates or long-range effects. Fractional diffusion occurs in many applications, including the groundwater flow, cardiac electrical propagation, and finance problems listed above.
Solving mathematical models of fractional diffusion is challenging, and typically requires a numerical method, i.e. a computer simulation. Usually, the most time-consuming part of this simulation is solving thousands, or even millions, of interdependent linear equations on a computer. Indeed, the time required to solve this system of equations may be so large that we are prevented from simulating fractional diffusion problems that capture the true complexity of real-world applications. Reducing this solve time is thus crucial if we are to generate new scientific insights in important applications involving fractional diffusion.
This project will develop new methods for solving these huge systems of equations that are guaranteed to be fast. We will focus on iterative solvers, which are well suited to the class of numerical methods (computer simulations) on which we focus. Iterative solvers of systems of equations compute a new approximation to the solution at each step, and so are fast if a good approximation is found after only a few iterations. However, this is generally only possible if we apply a convergence accelerator, called a preconditioner, which captures the 'essence' of the linear system, but is cheap to use.
For many fractional diffusion problems, this preconditioner is currently chosen heuristically, i.e. without theoretical justification. Consequently, the preconditioner may fail to reduce the (very large) computation time needed to solve the linear system. The goal of this project is to propose new preconditioners and iterative methods that are theoretically justified, and hence guaranteed to converge quickly, for a range of fractional diffusion problems. We will develop new software that will enable people with fractional diffusion problems to easily use our improved solvers. Additionally we will apply these fast preconditioners and iterative solvers in a fractional diffusion model of groundwater flow of an important UK aquifer. Solving this model quickly will enable us to better track our drinking water, and identify possible sources of contamination.
Solving mathematical models of fractional diffusion is challenging, and typically requires a numerical method, i.e. a computer simulation. Usually, the most time-consuming part of this simulation is solving thousands, or even millions, of interdependent linear equations on a computer. Indeed, the time required to solve this system of equations may be so large that we are prevented from simulating fractional diffusion problems that capture the true complexity of real-world applications. Reducing this solve time is thus crucial if we are to generate new scientific insights in important applications involving fractional diffusion.
This project will develop new methods for solving these huge systems of equations that are guaranteed to be fast. We will focus on iterative solvers, which are well suited to the class of numerical methods (computer simulations) on which we focus. Iterative solvers of systems of equations compute a new approximation to the solution at each step, and so are fast if a good approximation is found after only a few iterations. However, this is generally only possible if we apply a convergence accelerator, called a preconditioner, which captures the 'essence' of the linear system, but is cheap to use.
For many fractional diffusion problems, this preconditioner is currently chosen heuristically, i.e. without theoretical justification. Consequently, the preconditioner may fail to reduce the (very large) computation time needed to solve the linear system. The goal of this project is to propose new preconditioners and iterative methods that are theoretically justified, and hence guaranteed to converge quickly, for a range of fractional diffusion problems. We will develop new software that will enable people with fractional diffusion problems to easily use our improved solvers. Additionally we will apply these fast preconditioners and iterative solvers in a fractional diffusion model of groundwater flow of an important UK aquifer. Solving this model quickly will enable us to better track our drinking water, and identify possible sources of contamination.
Planned Impact
The outcome of the proposed research will be state-of-the-art methods for the numerical solution of fractional diffusion problems. Since fractional diffusion equations arise in models with heterogenous or anomalous diffusion rates, they are applicable to a number of important physical processes in, e.g. hydrology, finance and biology. Companies in these fields looking to improve their understanding of these diffusion processes may, therefore, benefit from our research.
One specific application we have identified is groundwater flow in the presence of rock fractures, which often occurs in aquifers. We will work with the British Geological Society to implement our solvers in a fractional diffusion model of fluid transport through a UK aquifer. Since quality issues affect almost 50% of public supply groundwater in the UK, it is clear that improved models of groundwater flow, that give insight into where and why these quality issues arise, could have real economic and societal benefits.
Other external beneficiaries will be identified by working with Strathclyde University's Statistics and Mathematics Advice, Research and Training (SMART) consultancy unit, and the university's Technology and Innovation Centre, both of which connect academics to external partners. Additionally, a two-day workshop will bring together academics and industrial partners with an interest in fractional diffusion problems. The aim of this workshop will be to foster collaborations and develop new pathways to impact.
Since easy-to-use, well documented software is critical to the uptake of our work, we will provide Python and Matlab codes on a dedicated website with examples of use. The site will also discuss the different numerical methods available to solve fractional diffusion problems and will provide links to other researchers in this field. We will additionally discuss our results with the Numerical Algorithms Group, who provide the largest commercially available collection of numerical and statistical algorithms in the world, and will aim to produce preconditioners of value to their collection.
Public engagement will also form part of our strategy to maximise impact. Specific events we will target are the Engage with Strathclyde week, the University's flagship knowledge exchange event; the Glasgow Science Festival, which attracts more than 50 000 members of the public annually; and the "meet the scientist" scheme at the University of Glasgow. To ensure these activities are successful, the Principal Investigator will also undertake public engagement training.
One specific application we have identified is groundwater flow in the presence of rock fractures, which often occurs in aquifers. We will work with the British Geological Society to implement our solvers in a fractional diffusion model of fluid transport through a UK aquifer. Since quality issues affect almost 50% of public supply groundwater in the UK, it is clear that improved models of groundwater flow, that give insight into where and why these quality issues arise, could have real economic and societal benefits.
Other external beneficiaries will be identified by working with Strathclyde University's Statistics and Mathematics Advice, Research and Training (SMART) consultancy unit, and the university's Technology and Innovation Centre, both of which connect academics to external partners. Additionally, a two-day workshop will bring together academics and industrial partners with an interest in fractional diffusion problems. The aim of this workshop will be to foster collaborations and develop new pathways to impact.
Since easy-to-use, well documented software is critical to the uptake of our work, we will provide Python and Matlab codes on a dedicated website with examples of use. The site will also discuss the different numerical methods available to solve fractional diffusion problems and will provide links to other researchers in this field. We will additionally discuss our results with the Numerical Algorithms Group, who provide the largest commercially available collection of numerical and statistical algorithms in the world, and will aim to produce preconditioners of value to their collection.
Public engagement will also form part of our strategy to maximise impact. Specific events we will target are the Engage with Strathclyde week, the University's flagship knowledge exchange event; the Glasgow Science Festival, which attracts more than 50 000 members of the public annually; and the "meet the scientist" scheme at the University of Glasgow. To ensure these activities are successful, the Principal Investigator will also undertake public engagement training.
People |
ORCID iD |
Jennifer Pestana (Principal Investigator) |
Publications
Bootland N
(2021)
Analysis of parallel Schwarz algorithms for time-harmonic problems using block Toeplitz matrices
in ETNA - Electronic Transactions on Numerical Analysis
Pearson J
(2020)
Preconditioners for Krylov subspace methods: An overview
in GAMM-Mitteilungen
Pestana J
(2019)
Preconditioners for Symmetrized Toeplitz and Multilevel Toeplitz Matrices
in SIAM Journal on Matrix Analysis and Applications
Mazza M
(2018)
Spectral properties of flipped Toeplitz matrices and related preconditioning
in BIT Numerical Mathematics
Mazza M
(2021)
The Asymptotic Spectrum of Flipped Multilevel Toeplitz Matrices and of Certain Preconditionings
in SIAM Journal on Matrix Analysis and Applications
Description | It is normally necessary to use a numerical method to approximate the solution of a fractional diffusion equation. A key part of these numerical methods is the solution, by a computer, of large linear systems (set of simultaneous equations), and this is usually very time consuming. However, when we approximate the solution of certain constant-coefficient fractional diffusion equations at equally-spaced points, we obtain a linear system with certain (Toeplitz) structure. Using this structure allows us to introduce symmetry into the linear system. The first key finding of this project is the development of new preconditioners that exploit this symmetry to reduce the time it takes a computer to solve fractional diffusion equations. More theoretical findings were also obtained. First, we have been able to relate each structured, symmetrized system to a much simpler function. Since it is much easier to understand the properties of this function than it is to characterise the properties of the linear system, this relationship provides a convenient tool for researchers to analyse new preconditioners for accelerating the solution of these linear systems. The results of this work can also be applied to linear systems from different applications that have the same multilevel Toeplitz structure. Second, we have characterised the eigenvalues of symmetrized multilevel circulant matrices, which arise not only in certain fractional diffusion problems but also in signal and image processing, and partial differential equations. |
Exploitation Route | These findings could be used to enable researchers to solve fractional diffusion equations at higher resolutions. These highly detailed solutions are necessary for accurately capturing detail in problems modelled by fractional diffusion equations in, e.g., hydrology, finance and biology. Since the Toeplitz structure exploited here also appears when other mathematical models, e.g., those involving partial differential equations and integral equations, are solved by certain numerical methods, the findings of this project could also help accelerate the solution of these other mathematical models. |
Sectors | Environment,Healthcare,Manufacturing, including Industrial Biotechology,Pharmaceuticals and Medical Biotechnology |
URL | http://personal.strath.ac.uk/jennifer.pestana/ |
Title | Algorithms for: "Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices" |
Description | "Codes for preconditioned iterative methods for fractional diffusion problems, associated with the manuscript ""Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices"" by J. Pestana, 2018. Code is available from a GitHub-Zenodo integrated archive. " |
Type Of Material | Database/Collection of data |
Year Produced | 2018 |
Provided To Others? | Yes |
Impact | . |
Description | Departmental Seminar at Queensland University of Technology |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Departmental Seminar at Queensland University of Technology |
Year(s) Of Engagement Activity | 2018 |
Description | Glasgow Applied Mathematics Seminar |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | Regional |
Primary Audience | Professional Practitioners |
Results and Impact | Glasgow Applied Mathematics Seminar |
Year(s) Of Engagement Activity | 2018 |
Description | Hosting a visitor for Numerical Analysis and Scientific Computing Seminar |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | Local |
Primary Audience | Professional Practitioners |
Results and Impact | Hosting Silvia Gazzola (University of Bath) for Numerical Analysis and Scientific Computing Seminar |
Year(s) Of Engagement Activity | 2019 |
Description | Hosting a visitor for Numerical Analysis and Scientific Computing Seminar |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | Local |
Primary Audience | Professional Practitioners |
Results and Impact | Hosted Kirk Soodhalter (Trinity College Dublin) for Numerical Analysis and Scientific Computing Seminar |
Year(s) Of Engagement Activity | 2018 |
Description | Hosting a visitor for Strathclyde-Edinburgh Numerical Linear Algebra Seminar |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | Regional |
Primary Audience | Professional Practitioners |
Results and Impact | Hosting Stefano Serra-Capizzano (Insubria University) for Strathclyde-Edinburgh Numerical Linear Algebra Seminar |
Year(s) Of Engagement Activity | 2019 |
Description | Numerical Analysis and Scientific Computing Seminar at School of Mathematics, University of Manchester |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Professional Practitioners |
Results and Impact | Numerical Analysis and Scientific Computing Seminar at School of Mathematics, University of Manchester |
Year(s) Of Engagement Activity | 2018 |
Description | Symmetrizing Nonsymmetric Toeplitz Matrices in Fractional Diffusion Problems |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Symmetrizing Nonsymmetric Toeplitz Matrices in Fractional Diffusion Problems at SIAM Annual Meeting in Portland, United States. |
Year(s) Of Engagement Activity | 2018 |
Description | Symmetrizing nonsymmetric Toeplitz matrices in fractional diffusion problems |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Symmetrizing nonsymmetric Toeplitz matrices in fractional diffusion problems at SIAM Conference on Applied Linear Algebra in Hong Kong |
Year(s) Of Engagement Activity | 2018 |
Description | Talk at Advances in Numerical Linear Algebra Workshop, Manchester |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Invited talk at Workshop on Advances in Numerical Linear Algebra: Celebrating the Centenary of the Birth of Jame H. Wilkinson, May 29-30, 2019, Manchester. |
Year(s) Of Engagement Activity | 2019 |
URL | https://nla-group.org/advances-in-numerical-linear-algebra-2019/ |
Description | Website |
Form Of Engagement Activity | Engagement focused website, blog or social media channel |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | A website was designed to give a brief description of fractional diffusion, its applications, and the challenges of working with these equations. The website is suitable for a general audience, with pointers to further information or project details for those with a mathematical background. It puts the project in the context of wider research and improved understanding of natural phenomena. |
Year(s) Of Engagement Activity | 2019 |
URL | http://www.fracdiffpreconditioners.net |