Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userK$omega$ -- Open-source library for the shifted Krylov subspace method of the form $(zI-H)x=b$
117
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We develop K$omega$, an open-source linear algebra library for the shifted Krylov subspace methods. The methods solve a set of shifted linear equations $(z_k I-H)x^{(k)}=b, (k=0,1,2,...)$ for a given matrix $H$ and a vector $b$, simultaneously. The leading order of the operational cost is the same as that for a single equation. The shift invariance of the Krylov subspace is the mathematical foundation of the shifted Krylov subspace methods. Applications in materials science are presented to demonstrate the advantages of the algorithm over the standard Krylov subspace methods such as the Lanczos method. We introduce benchmark calculations of (i) an excited (optical) spectrum and (ii) intermediate eigenvalues by the contour integral on the complex plane. In combination with the quantum lattice solver $mathcal{H} Phi$, K$omega$ can realize parallel computation of excitation spectra and intermediate eigenvalues for various quantum lattice models.
rate research
Read More
We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework. As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.
New algorithms are proposed for the Tucker approximation of a 3-tensor, that access it using only the tensor-by-vector-by-vector multiplication subroutine. In the matrix case, Krylov methods are methods of choice to approximate the dominant column and row subspaces of a sparse or structured matrix given through the matrix-by-vector multiplication subroutine. Using the Wedderburn rank reduction formula, we propose an algorithm of matrix approximation that computes Krylov subspaces and allows generalization to the tensor case. Several variants of proposed tensor algorithms differ by pivoting strategies, overall cost and quality of approximation. By convincing numerical experiments we show that the proposed methods are faster and more accurate than the minimal Krylov recursion, proposed recently by Elden and Savas.
Many Krylov subspace methods for shifted linear systems take advantage of the invariance of the Krylov subspace under a shift of the matrix. However, exploiting this fact in the non-Hermitian case introduces restrictions; e.g., initial residuals must be collinear and this collinearity must be maintained at restart. Thus we cannot simultaneously solve shifted systems with unrelated right-hand sides using this strategy, and all shifted residuals cannot be simultaneously minimized over a Krylov subspace such that collinearity is maintained. It has been shown that this renders them generally incompatible with techniques of subspace recycling [Soodhalter et al. APNUM 14]. This problem, however, can be overcome. By interpreting a family of shifted systems as one Sylvester equation, we can take advantage of the known shift invariance of the Krylov subspace generated by the Sylvester operator. Thus we can simultaneously solve all systems over one block Krylov subspace using FOM or GMRES type methods, even when they have unrelated right-hand sides. Because residual collinearity is no longer a requirement at restart, these methods are fully compatible with subspace recycling techniques. Furthermore, we realize the benefits of block sparse matrix operations which arise in the context of high-performance computing applications. In this paper, we discuss exploiting this Sylvester equation point of view which has yielded methods for shifted systems which are compatible with unrelated right-hand sides. From this, we propose a recycled GMRES method for simultaneous solution of shifted systems.Numerical experiments demonstrate the effectiveness of the methods.
This paper presents the use of element-based algebraic multigrid (AMGe) hierarchies, implemented in the ParELAG (Parallel Element Agglomeration Algebraic Multigrid Upscaling and Solvers) library, to produce multilevel preconditioners and solvers for H(curl) and H(div) formulations. ParELAG constructs hierarchies of compatible nested spaces, forming an exact de Rham sequence on each level. This allows the application of hybrid smoothers on all levels and AMS (Auxiliary-space Maxwell Solver) or ADS (Auxiliary-space Divergence Solver) on the coarsest levels, obtaining complete multigrid cycles. Numerical results are presented, showing the parallel performance of the proposed methods. As a part of the exposition, this paper demonstrates some of the capabilities of ParELAG and outlines some of the components and procedures within the library.
We propose a new method for the approximate solution of the Lyapunov equation with rank-$1$ right-hand side, which is based on extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the connection between the Lyapunov equation, solution of systems of linear ODEs and alternating least squares method for low-rank approximation. The numerical experiments confirm the effectiveness of our approach.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
