Advances in Numerical Linear Algebra and Randomized Algorithms

The field of numerical linear algebra is witnessing significant developments with the integration of randomized techniques, leading to improved numerical stability and efficiency in various algorithms. Notably, the incorporation of random sketching techniques into block orthogonalization schemes and Krylov subspace methods is enhancing the stability and accuracy of these solvers. Furthermore, the development of scalable libraries for selected inversion and Cholesky decomposition of structured sparse matrices is facilitating faster and more efficient computations in scientific applications. Researchers are also exploring the application of randomized strong rank-revealing QR factorization for low-rank matrix approximation and column subset selection. Additionally, there is a growing interest in analyzing the numerical stability of sketched GMRES and developing techniques for lifting linear sketches to obtain optimal bounds and adversarial robustness. Other noteworthy developments include the proposal of new rational filters for large-scale eigenvalue problems and the acceleration of restarted Krylov methods using randomization. Notable papers include:

  • Serinv, a scalable library for selected inversion, achieving up to two orders of magnitude speedup over existing solvers.
  • A study on the numerical stability of sketched GMRES, demonstrating backward stability under certain conditions.
  • A proposal for accelerating restarted Krylov methods with randomization, showing improved convergence rates in some cases.

Sources

Random-sketching Techniques to Enhance the Numerically Stability of Block Orthogonalization Algorithms for s-step GMRES

Serinv: A Scalable Library for the Selected Inversion of Block-Tridiagonal with Arrowhead Matrices

Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation

On the numerical stability of sketched GMRES

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

On computing the zeros of a class of Sobolev orthogonal polynomials

Variants of thick-restart Lanczos for the Bethe-Salpeter eigenvalue problem

A shifted Laplace rational filter for large-scale eigenvalue problems

Accelerating a restarted Krylov method for matrix functions with randomization

Built with on top of