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

矩阵指数是一种重要的线性代数工具，有着广泛的应用。它的高效计算是一个经典的数值线性代数问题，在许多领域都具有相当重要的意义。本研究项目是关于计算大型矩阵指数的数值算法。其主要目标是：(1)发展有效的预条件技术来计算矩阵与向量的指数的乘积，以及(2)发展精确而高效的算法来计算本质上非负矩阵的指数的某些选定项。本文的研究将对大规模问题迭代方法中矩阵指数的理论和算法的研究起到推动作用。它将系统地解决在某些应用程序中至关重要的预条件和条目相对精度问题。所得到的算法将在计算效率和/或精度方面改进现有的算法。在该项目结束时，所开发算法的稳健的MatLab实现将公开可用。该项目中提出的算法将提供足够高效和/或准确的新的计算工具，以应对许多大规模应用问题所带来的挑战。大规模的初值问题被用来模拟和解决科学和工程中的大量实际问题，一种充分发展的有效的预处理技术将大大提高解决大规模初值问题的水平。所提出的精确计算大的本质非负矩阵的指数的选定项的算法将消除可能对传统算法构成重大挑战的数值精度问题。在连续时间马尔可夫链模型中，以及在大型复杂网络中，条目定义了各种网络属性，例如连通性，出现了对条目精确计算的需求，其中条目表示转移概率。因此，新算法将适用于涉及连续时间马尔可夫链或复杂网络的广泛问题。这些问题包括遗传学、社会学、神经学、生物网络、社会网络和国土安全、电信网络和计算机网络。

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.