An inexact inverse iteration for large sparse eigenvalue problems

In this paper, we propose an inverse inexact iteration method for the computation of the eigenvalue with the smallest modulus and its associated eigenvector for a large sparse matrix. The linear systems of the traditional inverse iteration are solved with accuracy that depends on the eigenvalue with the second smallest modulus and iteration numbers. We prove that this approach preserves the linear convergence of inverse iteration. We also propose two practical formulas for the accuracy bound which are used in actual implementation. © 1997 John Wiley & Sons, Ltd.     

On the ADI method for Sylvester equations

This paper is concerned with the numerical solution of large scale Sylvester equations AX−XB=C, Lyapunov equations as a special case in particular included, with C having very small rank. For stable Lyapunov equations, Penzl (2000) [22] and Li and White (2002) [20] demonstrated that the so-called Cholesky factor ADI method with decent shift parameters can be very effective. In this paper we present a generalization of the Cholesky factor ADI method for Sylvester equations. An easily implementable extension of Penz’s shift strategy for the Lyapunov equation is presented for the current case. It is demonstrated that Galerkin projection via ADI subspaces often produces much more accurate solutions than ADI solutions.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

An implicit preconditioning strategy for large-scale generalized Sylvester equations

Large-scale generalized Sylvester equations appear in several important applications. Although the involved operator is linear, solving them requires specialized techniques. Different numerical methods have been designed to solve them, including direct factorization methods suitable for small size problems, and Krylov-type iterative methods for large-scale problems. For these iterative schemes, preconditioning is always a difficult task that deserves to be addressed. We present and analyze an implicit preconditioning strategy specially designed for solving generalized Sylvester equations that uses a preconditioned residual direction at every iteration. The advantage is that the preconditioned direction is built implicitly, avoiding the explicit knowledge of the given matrices. Only the effect of the matrix-vector product with the given matrices is required. We present encouraging numerical experiments for a set of different problems coming from several applications.     

The new alternating direction implicit difference methods for the wave equations

A new second-order alternating direction implicit (ADI) scheme, based on the idea of the operator splitting, is presented for solving two-dimensional wave equations. The scheme is also extended to a high-order compact difference scheme. Both of them have the advantages of unconditional stability, less impact of the perturbing terms on the accuracy, and being convenient to compute the boundary values of the intermediates. Besides this, the compact scheme has high-order accuracy and costs less in computational time. Numerical examples are presented and the results are very satisfactory.     

The new alternating direction implicit difference methods for solving three-dimensional parabolic equations

A new alternating direction implicit (ADI) scheme for solving three-dimensional parabolic equations with nonhomogeneous boundary conditions is presented. The scheme is also extended to high-order compact difference scheme. Both of them have the advantages of unconditional stability and being convenient to compute the boundary values of the intermediates. Besides this, the compact scheme has high-order accuracy and uses less computational time. Numerical examples are presented and the results are very satisfactory.     

求解Sylvester矩阵方程的一种改进的梯度方法

提出了一种改进的梯度迭代算法来求解Sylvester矩阵方程和Lyapunov矩阵方程.该梯度算法是通过构造一种特殊的矩阵分裂,综合利用Jaucobi迭代算法和梯度迭代算法的求解思路.与已知的梯度算法相比,提高了算法的迭代效率.同时研究了该算法在满足初始条件下的收敛性.数值算例验证了该算法的有效性.     

A class of one-parameter alternating direction implicit methods for two-dimensional wave equations with discrete and distributed time-variable delays

For solving the initial-boundary value problem of two-dimensional wave equations with discrete and distributed time-variable delays, in the present paper, we first construct a class of basic one-parameter methods. In order to raise the computational efficiency of this class methods, we remold the methods as one-parameter alternating direction implicit (ADI) methods. Under the suitable conditions, the remolded methods are proved to be stable and convergent of second order in both of time and space. With several numerical experiments, the computational effectiveness and theoretical exactness of the methods are confirmed. Moreover, it is illustrated that the proposed one-parameter ADI method has the better advantage in computational efficiency than the basic one-parameter methods.     

A partial inexact alternating direction method for structured variational inequalities

In this article, a new method is proposed for solving a class of structured variational inequalities (SVIs). The proposed method is referred to as the partial inexact proximal alternating direction (piPAD) method. In the method, two subproblems are solved independently. One is handled by an inexact proximal point method and the other is solved directly. This feature is the major difference between the proposed method and some existing alternating direction-like methods. The convergence of the piPAD method is proved. Two examples of the modern convex optimization problem arising from engineering and information sciences, which can be reformulated into the encountered SVIs, are presented to demonstrate the applicability of the piPAD method. Also, some preliminary numerical results are reported to validate the feasibility and efficiency of the piPAD method.     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

Fourth-order alternating direction implicit compact finite difference schemes for two-dimensional Schrödinger equations

In this paper, alternating direction implicit compact finite difference schemes are devised for the numerical solution of two-dimensional Schrödinger equations. The convergence rates of the present schemes are of order O(h⁴+τ²). Numerical experiments show that these schemes preserve the conservation laws of charge and energy and achieve the expected convergence rates. Representative simulations show that the proposed schemes are applicable to problems of engineering interest and competitive when compared to other existing procedures.     

Finite iterative algorithm for the complex generalized Sylvester tensor equations

A finite iterative algorithm is proposed to solve a class of complex generalized Sylvester tensor equations. The properties of this proposed algorithm are discussed based on a real inner product of two complex tensors and the finite convergence of this algorithm is obtained. Two numerical examples are offered to illustrate the effectiveness of the proposed algorithm.     

A class of block alternating splitting implicit iteration methods for double saddle point linear systems

In the framework of a special block alternating splitting implicit (BASI) iteration scheme for generalized saddle point problems, we establish some new iteration methods for solving double saddle point problems by means of a suitable partitioning strategy. Convergence analysis of the corresponding BASI iteration methods indicates that they are convergent unconditionally under certain weak requirements for the related matrix splittings, which are satisfied directly for our specific application to double saddle point problems. Numerical examples for liquid crystal director and time-harmonic eddy current models are presented to demonstrate the efficiency of the proposed BASI preconditioners to accelerate the GMRES method.     

A modified gradient based algorithm for solving Sylvester equations

In this paper a modified gradient based algorithm for solving Sylvester equations is presented. Different from the gradient based method introduced by Ding and Chen [7] and the relaxed gradient based algorithm proposed by Niu et al. [18], the information generated in the first half-iterative step is fully exploited and used to construct the approximate solution. Theoretical analysis shows that the new method converges under certain assumptions. Numerical results are given to verify the efficiency of the new method.     

A combination of Sylvester block sum and block matrix Kronecker map for explicit solutions of Sylvester system of matrix equations

In this paper, we consider an explicit solution of system of Sylvester matrix equations of the form A₁V₁ ? E₁V₁F₁ = B₁W₁ and A₂V₂ ? E₂V₂F₂ = B₂W₂ with F₁ and F₂ being arbitrary matrices, where V₁,W₁,V₂ and W₂ are the matrices to be determined. First, the definitions, of the matrix polynomial of block matrix, Sylvester sum, and Kronecker product of block matrices are defined. Some definitions, lemmas, and theorems that are needed to propose our method are stated and proved. Numerical test problems are solved to illustrate the suggested technique.     

LSQR iterative method for generalized coupled Sylvester matrix equations

An iterative method is proposed to solve generalized coupled Sylvester matrix equations, based on a matrix form of the least-squares QR-factorization (LSQR) algorithm. By this iterative method on the selection of special initial matrices, we can obtain the minimum Frobenius norm solutions or the minimum Frobenius norm least-squares solutions over some constrained matrices, such as symmetric, generalized bisymmetric and (R, S)-symmetric matrices. Meanwhile, the optimal approximate solutions to the given matrices can be derived by solving the corresponding new generalized coupled Sylvester matrix equations. Finally, numerical examples are given to illustrate the effectiveness of the present method.     

On the explicit solutions of forms of the Sylvester and the Yakubovich matrix equations

In this paper, we consider the explicit solutions of two matrix equations, namely, the Yakubovich matrix equation V−AVF=BW and Sylvester matrix equations AV−EVF=BW,AV+BW=EVF and AV−VF=BW. For this purpose, we make use of Kronecker map and Sylvester sum as well as the concept of coefficients of characteristic polynomial of the matrix A. Some lemmas and theorems are stated and proved where explicit and parametric solutions are obtained. The proposed methods are illustrated by numerical examples. The results obtained show that the methods are very neat and efficient.     

Tuned preconditioners for inexact two‐sided inverse and Rayleigh quotient iteration

Convergence results are provided for inexact two‐sided inverse and Rayleigh quotient iteration, which extend the previously established results to the generalized non‐Hermitian eigenproblem and inexact solves with a decreasing solve tolerance. Moreover, the simultaneous solution of the forward and adjoint problem arising in two‐sided methods is considered, and the successful tuning strategy for preconditioners is extended to two‐sided methods, creating a novel way of preconditioning two‐sided algorithms. Furthermore, it is shown that inexact two‐sided Rayleigh quotient iteration and the inexact two‐sided Jacobi‐Davidson method (without subspace expansion) applied to the generalized preconditioned eigenvalue problem are equivalent when a certain number of steps of a Petrov–Galerkin–Krylov method is used and when this specific tuning strategy is applied. Copyright © 2014 John Wiley & Sons, Ltd.     

Analysis and efficient implementation of alternating direction implicit finite volume method for Riesz space‐fractional diffusion equations in two space dimensions

In this article, we develop a Crank–Nicolson alternating direction implicit finite volume method for time‐dependent Riesz space‐fractional diffusion equation in two space dimensions. Norm‐based stability and convergence analysis are given to show that the developed method is unconditionally stable and of second‐order accuracy both in space and time. Furthermore, we develop a lossless matrix‐free fast conjugate gradient method for the implementation of the numerical scheme, which only has memory requirement and computational complexity per iteration with N being the total number of spatial unknowns. Several numerical experiments are presented to demonstrate the effectiveness and efficiency of the proposed scheme for large‐scale modeling and simulations.     

On HSS-based iteration methods for weakly nonlinear systems

Based on separable property of the linear and the nonlinear terms and on the Hermitian and skew-Hermitian splitting of the coefficient matrix, we present the Picard-HSS and the nonlinear HSS-like iteration methods for solving a class of large scale systems of weakly nonlinear equations. The advantage of these methods over the Newton and the Newton-HSS iteration methods is that they do not require explicit construction and accurate computation of the Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Hence, computational workloads and computer memory may be saved in actual implementations. Under suitable conditions, we establish local convergence theorems for both Picard-HSS and nonlinear HSS-like iteration methods. Numerical implementations show that both Picard-HSS and nonlinear HSS-like iteration methods are feasible, effective, and robust nonlinear solvers for this class of large scale systems of weakly nonlinear equations.