Arrowhead Factorization of Real Symmetric Matrices and its Applications in Optimized Eigendecomposition

This work introduces a new matrix decomposition, that we termed arrowhead factorization (AF). We showcase its applications as a novel method to compute all eigenvalues and eigenvectors of certain symmetric real matrices in the class of generalized arrowhead matrices. We present a clear definition and proof by construction of the existence of AF, detailing how to bridge the gap to full eigende-composition. Our proposed method was tested against state-of-the-art routines, implemented in OpenBLAS, AOCL and Intel oneAPI MKL, using three synthetic benchmarks inspired by real world scientific applications. These experiments highlighted up to 49× faster runtimes, proving the validity and efficacy of our approach. Furthermore, we applied our method to a practical scenario by conducting a numerical experiment on simulation data derived from Golden-rule instanton theory. This real world application showed a performance gain ranging from 2.5×, for exact eigendecomposition, to over 38× with the most aggressive approximation strategy, underscoring the efficiency, robustness and flexibility of our algorithm.