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.