Accurate and Efficient Algorithms for Computing Exponentials of Large Matrices with Applications

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

Matrix exponential is an important linear algebra tool that has a wide range of applications. Its efficient computation is a classical numerical linear algebra problem that is of considerable importance to many fields. This research project is concerned with numerical algorithms for computing exponentials of large matrices. The main objectives are: (1) to develop efficient preconditioning techniques for computing the product of the exponential of a matrix with a vector, and (2) to develop accurate and efficient algorithms to compute some selected entries of the exponential of an essentially nonnegative matrix. The proposed research will advance theory and algorithms for matrix exponentials in the setting of iterative methods for large scale problems. It will systemically address the problems of preconditioning and entrywise relative accuracy that are critically important in certain applications. The resulting algorithms will improve the existing ones in computational efficiency and/or accuracy. At the conclusion of this project, robust MATLAB implementations of the algorithms developed will be made publicly available. The algorithms proposed in this project will provide new computational tools that are sufficiently efficient and/or accurate to meet the challenges posed by many large scale application problems. A fully developed efficient preconditioning technique would significantly advance the state of the art in solving large scale initial value problems, which are used to model and solve a large number of practical problems in science and engineering. The proposed algorithms for accurately computing selected entries of the exponential of a large essentially nonnegative matrix would remove the numerical accuracy issue that may present a significant challenge to the traditional algorithms. The need for entrywise accurate computations arise in continuous-time Markov chain models, where the entries represent transition probabilities, and in large complex networks, where the entries define various network properties such as connectivity. Thus, the new algorithms will be applicable to a wide range of problems that involves continuous-time Markov chains or complex networks. They include problems from genetics, sociology, neurology, biological networks, social networks and homeland security, telecommunication networks, and computer networks.