An official website of the United States government
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
Numerical experiments using the barycentric Lagrange treecode to compute correlated random displacements for Brownian dynamics simulations
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
- Award ID(s):
- 2110767
- PAR ID:
- 10646897
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Journal of Computational Physics
- ISSN:
- 0021-9991
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Recombinant adeno‐associated virus (rAAV) vectors are a promising platform for in vivo gene therapies. However, cost‐effective, well‐characterized processes necessary to manufacture rAAV therapeutics are challenging to develop without an understanding of how process parameters (PPs) affect rAAV product quality attributes (PQAs). In this work, a central composite orthogonal experimental design was employed to examine the influence of four PPs for transient transfection complex formation (polyethylenimine:DNA [PEI:DNA] ratio, total DNA/cell, cocktail volume, and incubation time) on three rAAV PQAs related to capsid content (vector genome titer, vector genome:capsid particle ratio, and two‐dimensional vector genome titer ratio). A regression model was established for each PQA using partial least squares, and a design space (DS) was defined in which Monte Carlo simulations predicted < 1% probability of failure (POF) to meet predetermined PQA specifications. Of the three PQAs, viral genome titer was most strongly correlated with changes in complexation PPs. The DS and acceptable PP ranges were largest when incubation time and cocktail volume were kept at mid‐high setpoints, and PEI:DNA ratio and total DNA/cell were at low‐mid setpoints. Verification experiments confirmed model predictive capability, and this work establishes a framework for studying other rAAV PPs and their relationship to PQAs.more » « less
-
Approximating the action of a matrix function $$f(\vec{A})$$ on a vector $$\vec{b}$$ is an increasingly important primitive in machine learning, data science, and statistics, with applications such as sampling high dimensional Gaussians, Gaussian process regression and Bayesian inference, principle component analysis, and approximating Hessian spectral densities. Over the past decade, a number of algorithms enjoying strong theoretical guarantees have been proposed for this task. Many of the most successful belong to a family of algorithms called \emph{Krylov subspace methods}. Remarkably, a classic Krylov subspace method, called the Lanczos method for matrix functions (Lanczos-FA), frequently outperforms newer methods in practice. Our main result is a theoretical justification for this finding: we show that, for a natural class of \emph{rational functions}, Lanczos-FA matches the error of the best possible Krylov subspace method up to a multiplicative approximation factor. The approximation factor depends on the degree of $f(x)$'s denominator and the condition number of $$\vec{A}$$, but not on the number of iterations $$k$$. Our result provides a strong justification for the excellent performance of Lanczos-FA, especially on functions that are well approximated by rationals, such as the matrix square root.more » « less
-
null (Ed.)The power method is commonly applied to compute the Perron vector of large adjacency matrices. Blondel et al. [SIAM Rev. 46, 2004] investigated its performance when the adjacency matrix has multiple eigenvalues of the same magnitude. It is well known that the Lanczos method typically requires fewer iterations than the power method to determine eigenvectors with the desired accuracy. However, the Lanczos method demands more computer storage, which may make it impractical to apply to very large problems. The present paper adapts the analysis by Blondel et al. to the Lanczos and restarted Lanczos methods. The restarted methods are found to yield fast convergence and to require less computer storage than the Lanczos method. Computed examples illustrate the theory presented. Applications of the Arnoldi method are also discussed.more » « less
-
We study algorithms for approximating the spectral density (i.e., the eigenvalue distribution) of a symmetric matrix A ∈ ℝn×n that is accessed through matrix-vector product queries. Recent work has analyzed popular Krylov subspace methods for this problem, showing that they output an ∈ · || A||2 error approximation to the spectral density in the Wasserstein-1 metric using O (1/∈ ) matrix-vector products. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of A before estimating the spectral density, we give an improved error bound of ∈ · σℓ (A) using O (ℓ log n + 1/∈ ) matrix-vector products, where σℓ (A) is the ℓth largest singular value of A. In the common case when A exhibits fast singular value decay and so σℓ (A) « ||A||2, our bound can be much stronger than prior work. We also show that it is nearly tight: any algorithm giving error ∈ · σℓ (A) must use Ω(ℓ + 1/∈ ) matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method essentially matches the above bound for any choice of parameter ℓ, even though SLQ itself is parameter-free and performs no explicit deflation. Our bound helps to explain the strong practical performance and observed ‘spectrum adaptive’ nature of SLQ, and motivates a simple variant of the method that achieves an even tighter error bound. Technically, our results require a careful analysis of how eigenvalues and eigenvectors are approximated by (block) Krylov subspace methods, which may be of independent interest. Our error bound for SLQ leverages an analysis of the method that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform ‘implicit deflation’ as part of moment matching.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
