Добірка наукової літератури з теми "Jacobi-Davidson Iteration"

The Jacobi–Davidson iteration method is very efficient in solving Hermitian eigenvalue problems. If the correction equation involved in the Jacobi–Davidson iteration is solved accurately, the simplified Jacobi–Davidson iteration is equivalent to the Rayleigh quotient iteration which achieves cubic convergence rate locally. When the involved linear system is solved by an iteration method, these two methods are also equivalent. In this paper, we present the convergence analysis of the simplified Jacobi–Davidson method and present the estimate of iteration numbers of the inner correction equation. Furthermore, based on the convergence factor, we can see how the accuracy of the inner iteration controls the outer iteration.

The Jacobi–Davidson iteration method is efficient for computing several eigenpairs of Hermitian matrices. Although the involved correction equation in the Jacobi–Davidson method has many developed variants, the behaviors of them are not clear for us. In this paper, we aim to explore, theoretically, the convergence property of the Jacobi–Davidson method influenced by different types of correction equations. As a by-product, we derive the optimal expansion vector, which imposed a shift-and-invert transform on a vector located in the prescribed subspace, to expand the current subspace.

Many methods for computing eigenvalues of a large sparse matrix involve shift-invert transformations which require the solution of a shifted linear system at each step. This thesis deals with shift-invert iterative techniques for solving eigenvalue problems where the arising linear systems are solved inexactly using a second iterative technique. This approach leads to an inner-outer type algorithm. We provide convergence results for the outer iterative eigenvalue computation as well as techniques for efficient inner solves. In particular eigenvalue computations using inexact inverse iteration, the Jacobi-Davidson method without subspace expansion and the shift-invert Arnoldi method as a subspace method are investigated in detail. A general convergence result for inexact inverse iteration for the non-Hermitian generalised eigenvalue problem is given, using only minimal assumptions. This convergence result is obtained in two different ways; on the one hand, we use an equivalence result between inexact inverse iteration applied to the generalised eigenproblem and modified Newton's method; on the other hand, a splitting method is used which generalises the idea of orthogonal decomposition. Both approaches also include an analysis for the convergence theory of a version of inexact Jacobi-Davidson method, where equivalences between Newton's method, inverse iteration and the Jacobi-Davidson method are exploited. To improve the efficiency of the inner iterative solves we introduce a new tuning strategy which can be applied to any standard preconditioner. We give a detailed analysis on this new preconditioning idea and show how the number of iterations for the inner iterative method and hence the total number of iterations can be reduced significantly by the application of this tuning strategy. The analysis of the tuned preconditioner is carried out for both Hermitian and non-Hermitian eigenproblems. We show how the preconditioner can be implemented efficiently and illustrate its performance using various numerical examples. An equivalence result between the preconditioned simplified Jacobi-Davidson method and inexact inverse iteration with the tuned preconditioner is given. Finally, we discuss the shift-invert Arnoldi method both in the standard and restarted fashion. First, existing relaxation strategies for the outer iterative solves are extended to implicitly restarted Arnoldi's method. Second, we apply the idea of tuning the preconditioner to the inner iterative solve. As for inexact inverse iteration the tuned preconditioner for inexact Arnoldi's method is shown to provide significant savings in the number of inner solves. The theory in this thesis is supported by many numerical examples.

Model order reduction (MOR) refers to the process of reducing the size of large scale discrete systems with the goal of capturing their behavior in a small and tractable model known as the reduced order model (ROM). ROMs are invariably constructed by projecting the original system onto a low rank subspace that captures the physics for specified range/s of parameter/s. The parameters, say for electromagnetic scattering, can be the frequency of excitation, angle of incidence, and/or material parameters. Thus, ROMs enable fast parameter sweep analysis and quick prototyping. Historically, a majority of the MOR techniques dealt with systems that are either linear or linearizable. Such techniques were developed around the numerically robust and computationally efficient Krylov subspace methods such as the Arnoldi or the Lanczos algorithm for single input, single output (SISO) systems. For multiple input, multiple output (MIMO) case, the block versions of these algorithms were used. In particular, the Lanczos algorithm could be used to construct a Padé approximation of the original system. Furthermore, since Krylov subspace based ROMs could preserve important attributes of the original system, like passivity, they were specifically popular in large-scale interconnect modeling. However, the frequency domain finite element method (FEM) (used in this work), in the presence of absorbing boundaries (or perfectly matched layers) and/or losses in the media leads to matrix systems that exhibit nonlinear dependence on the frequency of excitation. One can approximate this nonlinear dependence with a matrix polynomial system through Taylor expansion and linearize the system followed by a projection via Arnoldi (PVA) or Padé via Lanczos (PVL) to construct the ROM. However, linearizations usually increase the system size depending upon the polynomial degree besides having a different sparsity pattern than the matrix polynomial. Alternatively, one can tackle the nonlinearity directly by matching the moments using what is known as asymptotic waveform evaluation (AWE). AWE is inherently an ill-conditioned process. A recent work known as the well-conditioned AWE (WCAWE) improves its conditioning by enforcing implicit orthonormalization while still matching moments, by introducing some correction terms. However, WCAWE can be cumbersome to implement and appears to be inherently sequential. This work reports a novel perspective on the AWE space and proposes a parallelizable multilevel Krylov subspace generation technique that improves the accuracy/bandwidth of the ROM even further. We also introduce a novel adaptation of the Jacobi-Davidson algorithm, which is used to solve nonlinear eigenvalue problems (NLEVP), to target solutions and their derivatives (AWE space) for the matrix system rather than the underlying NLEVP, and formulate its well-conditioned form. By doing so, we enable the use of a new preconditioned iterative solver for AWE. Finally, noting the bottleneck posed by the reassembly of excitation vector derivatives at the expansion points in certain types of multipoint AWE ROMs, we propose an algorithm to reuse the derivatives, thus saving on the ROM setup time considerably, without sacrificing accuracy. The efficacy of the proposed algorithms is verified through several practical examples. The work is concluded with pointers to many possibilities for future research, like preconditioners, parallelization and domain-decomposition.