More Like this

1. Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation

   https://doi.org/10.1137/22M1479853  

   Chen, Tyler; Greenbaum, Anne; Musco, Cameron; Musco, Christopher (June 2023, SIAM Journal on Matrix Analysis and Applications)

   Abstract. We describe a Lanczos-based algorithm for approximating the product of a rational matrix function with a vector. This algorithm, which we call the Lanczos method for optimal rational matrix function approximation (Lanczos-OR), returns the optimal approximation from a given Krylov subspace in a norm depending on the rational function’s denominator, and it can be computed using the information from a slightly larger Krylov subspace. We also provide a low-memory implementation which only requires storing a number of vectors proportional to the denominator degree of the rational function. Finally, we show that Lanczos-OR can be used to derive algorithms for computing other matrix functions, including the matrix sign function and quadrature-based rational function approximations. In many cases, it improves on the approximation quality of prior approaches, including the standard Lanczos method, with little additional computational overhead. 

   more » « less
2. Numerical experiments using the barycentric Lagrange treecode to compute correlated random displacements for Brownian dynamics simulations

   Wang, Lei; Krasny, Robert (January 2025, Journal of Computational Physics)

   To account for hydrodynamic interactions among solvated molecules, Brownian dynamics simulations require correlated random displacements based on the Rotne-Prager Yamakawa diffusion tensor D for a system of particles. The Spectral Lanczos Decomposition Method (SLDM) computes a sequence of Krylov subspace approximations, but each step requires a dense matrix-vector product Dq with a Lanczos vector q, and the quadratic cost of computing the product by direct summation (DS) is an obstacle for large-scale simulations. This work employs the barycentric Lagrange treecode (BLTC) to reduce the cost of the matrix-vector product while introducing a controllable approximation error. Numerical experiments compare the performance of SLDM-DS and SLDM-BLTC in serial and parallel (32 core, GPU) calculations. 

   more » « less
3. Analysis of stochastic Lanczos quadrature for spectrum approximation

   Chen, Tyler; Trogdon, Thomas; Ubaru, Shashanka (January 2021, Proceedings of the 38th International Conference on Machine Learning)

   The cumulative empirical spectral measure (CESM) $$\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$$ of a $$n\times n$$ symmetric matrix $$\mathbf{A}$$ is defined as the fraction of eigenvalues of $$\mathbf{A}$$ less than a given threshold, i.e., $$\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$$. Spectral sums $$\operatorname{tr}(f[\mathbf{A}])$$ can be computed as the Riemann–Stieltjes integral of $$f$$ against $$\Phi[\mathbf{A}]$$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $$t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$$ with probability at least $$1-\eta$$, by applying the Lanczos algorithm for $$\lceil 12 t^{-1} + \frac{1}{2} \rceil$$ iterations to $$\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments. 

   more » « less
4. On the shift‐invert Lanczos method for the buckling eigenvalue problem

   https://doi.org/10.1002/nme.6640  

   Lin, Chao‐Ping; Xie, Huiqing; Grimes, Roger; Bai, Zhaojun (March 2021, International Journal for Numerical Methods in Engineering)

   Abstract We consider the problem of extracting a few desired eigenpairs of the buckling eigenvalue problem , whereKis symmetric positive semi‐definite,K_Gis symmetric indefinite, and the pencil is singular, namely,KandK_Gshare a nontrivial common nullspace. Moreover, in practical buckling analysis of structures, bases for the nullspace ofKand the common nullspace ofKandK_Gare available. There are two open issues for developing an industrial strength shift‐invert Lanczos method: (1) the shift‐invert operator does not exist or is extremely ill‐conditioned, and (2) the use of the semi‐inner product induced byKdrives the Lanczos vectors rapidly toward the nullspace ofK, which leads to a rapid growth of the Lanczos vectors in norms and causes permanent loss of information and the failure of the method. In this paper, we address these two issues by proposing a generalized buckling spectral transformation of the singular pencil and a regularization of the inner product via a low‐rank updating of the semi‐positive definiteness ofK. The efficacy of our approach is demonstrated by numerical examples, including one from industrial buckling analysis. 

   more » « less
5. Lippmann-Schwinger-Lanczos algorithm for inverse scattering problems

   https://doi.org/10.1088/1361-6420/abfca4  

   Druskin, Zaslavsky (April 2022, 2022 Spring Central Sectional Meeting)

   We combine data-driven reduced order models (ROM) with the Lippmann- Schwinger integral equation to produce a direct nonlinear inversion method. The ROM is viewed as a Galerkin projection and is sparse due to Lanczos orthogonalization. Embedding into the continuous problem, a data-driven internal solution is produced. This internal solution is then used in the Lippmann-Schwinger equation, in a direct or iterative framework. The new approach also allows us to process non-square matrix-valued data-transfer functions, i.e., to remove the main limitation of the earlier versions of the ROM based inversion algorithms. We show numerical experiments for spectral domain data for which our inversion is far superior to the Born inversion. 

   more » « less