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.