It is known that every Toeplitz matrix $T$ enjoys a circulant and skew circulant splitting (denoted $\text{CSCS}$) i.e., $T=C-S$ a circulant matrix and $S$ a skew circulant matrix. Based on the variant of such a splitting (also referred to as $\text{CSCS}$), we first develop classical $\text{CSCS}$ iterative methods and then introduce shifted $\text{CSCS}$ iterative methods for solving hermitian positive definite Toeplitz systems in this paper. The convergence of each method is analyzed. Numerical experiments show that the classical $\text{CSCS}$ iterative methods work slightly better than the Gauss–Seidel $(\text{GS})$ iterative methods if the $\text{CSCS}$ is convergent, and that there is always a constant $\alpha $ such that the shifted $\text{CSCS}$ iteration converges much faster than the Gauss–Seidel iteration, no matter whether the $\text{CSCS}$ itself is convergent or not.

We propose a robust numerical algorithm for solving the nonlinear eigenvalue problem A(ƛ)x = 0. Our algorithm is based on the idea of finding the value of ƛ for which A(ƛ) is singular by computing the smallest eigenvalue or singular value of A(ƛ) viewed as a constant matrix. To further enhance computational efficiency, we introduce and use the concept of signed singular value. Our method is applicable when A(ƛ) is large and nonsymmetric and has strong nonlinearity. Numerical experiments on a nonlinear eigenvalue problem arising in the computation of scaling exponent in turbulent flow show robustness and effectiveness of our method.

Some convergence bounds of the minimal residual (MINRES) method are studied when the method is applied for solving Hermitian indefinite linear systems. The matrices of these linear systems are supposed to have some properties so that their spectra are all clustered around ±1. New convergence bounds depending on the spectrum of the coefficient matrix are presented. Some numerical experiments are shown to demonstrate our theoretical results.

The Toda equation and its variants are studied in the filed of integrable systems. One particularly generalized time discretisation of the Toda equation is known as the discrete hungry Toda (dhToda) equation, which has two main variants referred to as the dhTodaI equation and dhTodaII equation. The dhToda equations have both been shown to be applicable to the computation of eigenvalues of totally nonnegative (TN) matrices, which are matrices without negative minors. The dhTodaI equation has been investigated with respect to the properties of integrable systems, but the dhTodaII equation has not. Explicit solutions using determinants and matrix representations called Lax pairs are often considered as symbolic properties of discrete integrable systems. In this paper, we clarify the determinant solution and Lax pair of the dhTodaII equation by focusing on an infinite sequence. We show that the resulting determinant solution firmly covers the general solution to the dhTodaII equation, and provide an asymptotic analysis of the general solution as discrete-time variable goes to infinity.

For problems governed by a non-normal operator, the leading eigenvalue of the operator is of limited interest and a more relevant measure of the stability is obtained by considering the harmonic forcing causing the largest system response. Various methods for determining this so-called optimal forcing exist, but they all suffer from great computational expense and are hence not practical for large-scale problems. In the present paper a new method is presented, which is applicable to problems of arbitrary size. The method does not rely on timestepping, but on the solution of linear systems, in which the inverse Laplacian acts as a preconditioner. By formulating the search for the optimal forcing as an eigenvalue problem based on the resolvent operator, repeated system solves amount to power iterations, in which the dominant eigenvalue is seen to correspond to the energy amplification in a system for a given frequency, and the eigenfunction to the corresponding forcing function. Implementation of the method requires only minor modifications of an existing timestepping code, and is applicable to any partial differential equation containing the Laplacian, such as the Navier-Stokes equations. We discuss the method, first, in the context of the linear Ginzburg-Landau equation and then, the two-dimensional lid-driven cavity flow governed by the Navier-Stokes equations. Most importantly, we demonstrate that for the lid-driven cavity, the optimal forcing can be computed using a factor of up to 500 times fewer operator evaluations than the standard method based on exponential timestepping.

We present a high-order discontinuous Galerkin (DG) method for the time domain Maxwell's equations in three-dimensional heterogeneous media. New hierarchical orthonormal basis functions on unstructured tetrahedral meshes are used for spatial discretization while Runge-Kutta methods for time discretization. A uniaxial perfectly matched layer (UPML) is employed to terminate the computational domain. Exponential convergence with respect to the order of the basis functions is observed and large parallel speedup is obtained for a plane-wave scattering model. The rapid decay of the out-going wave in the UPML is shown in a dipole radiation simulation. Moreover, the low frequency electromagnetic fields excited by a horizontal electric dipole (HED) and a vertical magnetic dipole (VMD) over a layered conductive half-space and a high frequency ground penetrating radar (GPR) detection for an underground structure are investigated, showing the high accuracy and broadband simulation capability of the proposed method.

We generalize the accelerated Hermitian and skew-Hermitian splitting (AHSS) iteration methods for large sparse saddle-point problems. These methods involve four iteration parameters whose special choices can recover the preconditioned HSS and accelerated HSS iteration methods. Also a new efficient case is introduced and we theoretically prove that this new method converges to the unique solution of the saddle-point problem. Numerical experiments are used to further examine the effectiveness and robustness of iterations.

The space fractional coupled nonlinear Schrödinger (CNLS) equations are discretized by an implicit conservative difference scheme with the fractional centered difference formula, which is unconditionally stable. The coefficient matrix of the discretized linear system is equal to the sum of a complex scaled identity matrix which can be written as the imaginary unit times the identity matrix and a symmetric Toeplitz-plusdiagonal matrix. In this paper, we present new preconditioners based on Hermitian and skew-Hermitian splitting (HSS) for such Toeplitz-like matrix. Theoretically, we show that all the eigenvalues of the resulting preconditioned matrices lie in the interior of the disk of radius 1 centered at the point (1,0). Thus Krylov subspace methods with the proposed preconditioners converge very fast. Numerical examples are given to illustrate the effectiveness of the proposed preconditioners.

In this paper we consider the computation of some eigenpairs with smallest eigenvalues in modulus of large-scale polynomial eigenvalue problem. Recently, a partially orthogonal projection method and its refinement scheme were presented for solving the polynomial eigenvalue problem. The methods preserve the structures and properties of the original polynomial eigenvalue problem. Implicitly updating the starting vector and constructing better projection subspace, we develop an implicitly restarted version of the partially orthogonal projection method. Combining the implicit restarting strategy with the refinement scheme, we present an implicitly restarted refined partially orthogonal projection method. In order to avoid the situation that the converged eigenvalues converge repeatedly in the later iterations, we propose a novel explicit non-equivalence low-rank deflation technique. Finally some numerical experiments show that the implicitly restarted refined partially orthogonal projection method with the explicit non-equivalence low-rank deflation technique is efficient and robust.

For symmetric eigenvalue problems, we constructed a three-term recurrence polynomial filter by means of Chebyshev polynomials. The new filtering technique does not need to solve linear systems and only needs matrix-vector products. It is a memory conserving filtering technique for its three-term recurrence relation. As an application, we use this filtering strategy to the Davidson method and propose the filtered-Davidson method. Through choosing suitable shifts, this method can gain cubic convergence rate locally. Theory and numerical experiments show the efficiency of the new filtering technique.

We study the convergence of an Ulm-like Cayley transform method for solving inverse eigenvalue problems which avoids solving approximate Jacobian equations. Under the nonsingularity assumption of the relative generalized Jacobian matrices at the solution, a convergence analysis covering both the distinct and multiple eigenvalues cases is provided and the quadratical convergence is proved. Moreover, numerical experiments are given in the last section to illustrate our results.

Properties and comparison theorems for the maximal solution of the periodic discrete-time Riccati equation are supplemented by an extension of some earlier results and analysis, for the discrete-time Riccati equation to the periodic case.

The anisotropic perfectly matched layer (APML) defines a continuous vector field outside a rectangle domain and performs the complex coordinate stretching along the vector field. Inspired by [Z. Chen et al., Inverse Probl. Imag., 7, (2013):663–678] and based on the idea of the shortest distance, we propose a new approach to construct the vector field which still allows us to prove the exponential decay of the stretched Green function without the constraint on the thickness of the PML layer. Moreover, by using the reflection argument, we prove the stability of the PML problem in the PML layer and the convergence of the PML method. Numerical experiments are also included.

We consider perturbation bounds and condition numbers for a complex indefinite linear algebraic system, which is of interest in science and engineering. Some existing results are improved, and illustrative numerical examples are provided.

The paper aims to develop an effective preconditioner and conduct the convergence analysis of the corresponding preconditioned GMRES for the solution of discrete problems originating from multi-group radiation diffusion equations. We firstly investigate the performances of the most widely used preconditioners (ILU(k) and AMG) and their combinations (Bco and Bco), and provide drawbacks on their feasibilities. Secondly, we reveal the underlying complementarity of ILU(k) and AMG by analyzing the features suitable for AMG using more detailed measurements on multiscale nature of matrices and the effect of ILU(k) on multiscale nature. Moreover, we present an adaptive combined preconditioner Bcoα involving an improved ILU(0) along with its convergence constraints. Numerical results demonstrate that Bcoα-GMRES holds the best robustness and efficiency. At last, we analyze the convergence of GMRES with combined preconditioning which not only provides a persuasive support for our proposed algorithms, but also updates the existing estimation theory on condition numbers of combined preconditioned systems.

For any given matrix A ∈ℂnxn, a preconditioner tU(A) called the superoptimal preconditioner was proposed in 1992 by Tyrtyshnikov. It has been shown that tU(A) is an efficient preconditioner for solving various structured systems, for instance, Toeplitz-like systems. In this paper, we construct the superoptimal preconditioners for different functions of matrices. Let f be a function of matrices from ℂnxn to ℂnxn. For any A ∈ ℂ nxn, one may construct two superoptimal preconditioners for f(A): tU(f(A)) and f(tU(A)). We establish basic properties of tU(f(A)) and f(tU(A)) for different functions of matrices. Some numerical tests demonstrate that the proposed preconditioners are very efficient for solving the system f(A)x = b.

Conjugate symplectic eigenvalue problems arise in solving discrete linear-quadratic optimal control problems and discrete algebraic Riccati equations. In this article, backward errors of approximate pairs of conjugate symplectic matrices are obtained from their properties. Several numerical examples are given to illustrate the results.

This paper presents a parallel algorithm for finding the smallest eigenvalue of a family of Hankel matrices that are ill-conditioned. Such matrices arise in random matrix theory and require the use of extremely high precision arithmetic. Surprisingly, we find that a group of commonly-used approaches that are designed for high efficiency are actually less efficient than a direct approach for this class of matrices. We then develop a parallel implementation of the algorithm that takes into account the unusually high cost of individual arithmetic operations. Our approach combines message passing and shared memory, achieving near-perfect scalability and high tolerance for network latency. We are thus able to find solutions for much larger matrices than previously possible, with the potential for extending this work to systems with greater levels of parallelism. The contributions of this work are in three areas: determination that a direct algorithm based on the secant method is more effective when extreme fixed-point precision is required than are the algorithms more typically used in parallel floating-point computations; the particular mix of optimizations required for extreme precision large matrix operations on a modern multi-core cluster, and the numerical results themselves.

The Teter, Payne, and Allan “preconditioning” function plays a significant role in planewave DFT calculations. This function is often called the TPA preconditioner. We present a detailed study of this “preconditioning” function. We develop a general formula that can readily generate a class of “preconditioning” functions. These functions have higher order approximation accuracy and fulfill the two essential “preconditioning” purposes as required in planewave DFT calculations. Our general class of functions are expected to have applications in other areas.

A finite-element multigrid scheme for elliptic Nash-equilibrium multiobjective optimal control problems with control constraints is investigated. The multigrid computational framework implements a nonlinear multigrid strategy with collective smoothing for solving the multiobjective optimality system discretized with finite elements. Error estimates for the optimal solution and two-grid local Fourier analysis of the multigrid scheme are presented. Results of numerical experiments are presented to demonstrate the effectiveness of the proposed framework.