skip to main content


Title: Inexact rational Krylov subspace method for eigenvalue problems
An inexact rational Krylov subspace method is studied to solve large-scale nonsymmetric eigenvalue problems. Each iteration (outer step) of the rational Krylov subspace method requires solution to a shifted linear system to enlarge the subspace, performed by an iterative linear solver for large-scale problems. Errors are introduced at each outer step if these linear systems are solved approx- imately by iterative methods (inner step), and they accumulate in the rational Krylov subspace. In this article, we derive an upper bound on the errors intro- duced at each outer step to maintain the same convergence as exact rational Krylov subspace method for approximating an invariant subspace. Since this bound is inversely proportional to the current eigenresidual norm of the target invariant subspace, the tolerance of iterative linear solves at each outer step can be relaxed with the outer iteration progress. A restarted variant of the inexact rational Krylov subspace method is also proposed. Numerical experiments show the effectiveness of relaxing the inner tolerance to save computational cost.  more » « less
Award ID(s):
2111496 1819097
NSF-PAR ID:
10344800
Author(s) / Creator(s):
;
Editor(s):
Ye, Qiang
Date Published:
Journal Name:
Numerical Linear Algebra with Applications
ISSN:
1070-5325
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. One-particle Green’s functions obtained from the self-consistent solution of the Dyson equation can be employed in the evaluation of spectroscopic and thermodynamic properties for both molecules and solids. However, typical acceleration techniques used in the traditional quantum chemistry self-consistent algorithms cannot be easily deployed for the Green’s function methods because of a non-convex grand potential functional and a non-idempotent density matrix. Moreover, the optimization problem can become more challenging due to the inclusion of correlation effects, changing chemical potential, and fluctuations of the number of particles. In this paper, we study acceleration techniques to target the self-consistent solution of the Dyson equation directly. We use the direct inversion in the iterative subspace (DIIS), the least-squared commutator in the iterative subspace (LCIIS), and the Krylov space accelerated inexact Newton method (KAIN). We observe that the definition of the residual has a significant impact on the convergence of the iterative procedure. Based on the Dyson equation, we generalize the concept of the commutator residual used in DIIS and LCIIS and compare it with the difference residual used in DIIS and KAIN. The commutator residuals outperform the difference residuals for all considered molecular and solid systems within both GW and GF2. For a number of bond-breaking problems, we found that an easily obtained high-temperature solution with effectively suppressed correlations is a very effective starting point for reaching convergence of the problematic low-temperature solutions through a sequential reduction of temperature during calculations.

     
    more » « less
  2. Abstract Bregman-type iterative methods have received considerable attention in recent years due to their ease of implementation and the high quality of the computed solutions they deliver. However, these iterative methods may require a large number of iterations and this reduces their usefulness. This paper develops a computationally attractive linearized Bregman algorithm by projecting the problem to be solved into an appropriately chosen low-dimensional Krylov subspace. The projection reduces the computational effort required for each iteration. A variant of this solution method, in which nonnegativity of each computed iterate is imposed, also is described. Extensive numerical examples illustrate the performance of the proposed methods. 
    more » « less
  3. Electrical Impedance Tomography (EIT) is a well-known imaging technique for detecting the electrical properties of an object in order to detect anomalies, such as conductive or resistive targets. More specifically, EIT has many applications in medical imaging for the detection and location of bodily tumors since it is an affordable and non-invasive method, which aims to recover the internal conductivity of a body using voltage measurements resulting from applying low frequency current at electrodes placed at its surface. Mathematically, the reconstruction of the internal conductivity is a severely ill-posed inverse problem and yields a poor quality image reconstruction. To remedy this difficulty, at least in part, we regularize and solve the nonlinear minimization problem by the aid of a Krylov subspace-type method for the linear sub problem during each iteration. In EIT, a tumor or general anomaly can be modeled as a piecewise constant perturbation of a smooth background, hence, we solve the regularized problem on a subspace of relatively small dimension by the Flexible Golub-Kahan process that provides solutions that have sparse representation. For comparison, we use a well-known modified Gauss–Newton algorithm as a benchmark. Using simulations, we demonstrate the effectiveness of the proposed method. The obtained reconstructions indicate that the Krylov subspace method is better adapted to solve the ill-posed EIT problem and results in higher resolution images and faster convergence compared to reconstructions using the modified Gauss–Newton algorithm. 
    more » « less
  4. In this paper, we propose a new spatial temperature aware transient EM induced stress analysis method. The new method consists of two new contributions: First, we propose a new TM-aware void saturation volume estimation method for fast immortality check in the post-voiding phase for the first time. We derive the analytic formula to estimate the void saturation in the presence of spatial temperature gradients due to Joule heating. Second, we developed a fast numerical solution for EM-induced stress analysis for multi-segment interconnect trees considering TM effect. The new method first transforms the coupled EM-TM partial differential equations into linear time-invariant ordinary differential equations (ODEs). Then extended Krylov subspace-based reduction technique is employed to reduce the size of the original system matrices so that they can be efficiently simulated in the time domain. The proposed method can perform the simulation process for both void nucleation and void growth phases under time-varying input currents and position-dependent temperatures. The numerical results show that, compared to the recently proposed semi-analytic EM-TM method, the proposed method can lead to about 28x speedup on average for the interconnect with up to 1000 branches for both void nucleation and growth phases with negligible errors. 
    more » « less
  5. null (Ed.)
    Abstract Randomized methods can be competitive for the solution of problems with a large matrix of low rank. They also have been applied successfully to the solution of large-scale linear discrete ill-posed problems by Tikhonov regularization (Xiang and Zou in Inverse Probl 29:085008, 2013). This entails the computation of an approximation of a partial singular value decomposition of a large matrix A that is of numerical low rank. The present paper compares a randomized method to a Krylov subspace method based on Golub–Kahan bidiagonalization with respect to accuracy and computing time and discusses characteristics of linear discrete ill-posed problems that make them well suited for solution by a randomized method. 
    more » « less