Probing With Displacements For Variance Reduction And The Effectiveness Of Sketched Krylov Eigenvalue Solvers

Scientific Computing is a multidisciplinary field that intersects Computer Science, Mathematics, and some other discipline to address complex problems utilizing computational systems. Numerical Linear Algebra (NLA), a subfield within Scientific Computing, develops and analyzes numerical algorithms for tasks involving linear operators such as matrices and their transformations. This dissertation focuses on developing kernels for two specific areas of NLA. Firstly, we explore variance reduction methods for trace approximation. In Lattice Quantum Chromodynamics (LQCD), computing the trace of a matrix inverse is crucial for investigating interactions among quarks and gluons in subatomic space. However, directly computing a matrix inverse is computationally expensive, motivating the use of stochastic methods to estimate the trace directly. Higher accuracy models result in a high variance of the trace estimator, resulting in techniques such as Probing that leverage the structures of LQCD matrices to reduce this variance. More recently, the development of so-called ``disconnected diagrams'' in LQCD necessitate the sum of certain off-diagonal elements in the matrix inverse, rendering Probing ineffective. In this work, we propose an extension to the Probing method that can lessen the variance of the trace estimator in such scenarios. Secondly, we investigate the viability of a technique that uses randomized subspace projections in Krylov-based iterative methods to approximate a subset of the eigenpairs of a large matrix. A common computational bottleneck for iterative methods comes from the need to consistently reorthogonalize the basis being constructed to ensure the accurate extraction of eigenpair approximations. While randomized subspace projections, often referred to as ``sketching'' methods, were originally introduced to reduce the size of large least-squares problems into more manageable ones, it was later observed that sketching techniques can be integrated into iterative methods to extract information from a non-orthogonal basis with minimal accuracy lost. We investigate the efficiency of these sketching methods using two iterative methods, Lanczos and Generalized Davidson, with and without restarting, within the high-performance software library PRIMME.