Avoiding matrix exponentials for large transition rate matrices.

Area of Science:

• Computational Mathematics
• Scientific Computing
• Biophysics

Background:

• Matrix exponentiation is computationally intensive (O(N^3) time, O(N^2) memory).
• Rate matrices are frequently used in scientific applications, particularly in modeling dynamical processes.
• Existing methods face challenges with computational cost and numerical precision.

Purpose of the Study:

• To explore and benchmark five distinct methods for matrix exponentiation, focusing on rate matrices.
• To identify novel, computationally efficient methods for matrix exponentiation.
• To analyze the implications of these methods on downstream computational tasks like Monte Carlo sampling.

Main Methods:

• Leveraged mathematical analogies between matrix exponentials and Markov jump processes (MJPs).
• Developed a novel MJP-based method by restricting 'trajectory' jumps.
• Benchmarked Runge-Kutta integrators and Krylov subspace methods for general matrix exponentiation.

Main Results:

• Identified a novel MJP-based method with improved computational scaling.
• Krylov subspace methods and the novel MJP method achieve O(N^2) time complexity.
• Achieved reduced memory requirements to O(N) for the most competitive methods.

Conclusions:

• The novel MJP-based method and Krylov subspace methods offer significant computational advantages for exponentiating rate matrices.
• These optimized methods reduce computational time and memory footprint, enabling more efficient scientific simulations.
• The findings have implications for improving the mixing properties of Monte Carlo posterior samplers.