Standard Krylov subspace solvers for self-adjoint problems have rigorous convergence bounds based solely on eigenvalues. However, for non-self-adjoint problems, eigenvalues do not determine behavior even for widely used iterative methods. In this paper, we discuss time-dependent PDE problems, which are always non-self-adjoint. We propose a block circulant preconditioner for the all-at-once evolutionary PDE system which has block Toeplitz structure. Through reordering of variables to obtain a symmetric system, we are able to rigorously establish convergence bounds for MINRES which guarantee a number of iterations independent of the number of time-steps for the all-at-once system. If the spatial differential operators are simultaneously diagonalizable, we are able to quickly apply the preconditioner through use of a sine transform; and for those that are not, we are able to use an algebraic multigrid process to provide a good approximation. Results are presented for solution to both the heat and convection ...

When simulating a mechanism from science or engineering, or an industrial process, one is frequently required to construct a mathematical model, and then resolve this model numerically. If accurate numerical solutions are necessary or desirable, this can involve solving large‐scale systems of equations. One major class of solution methods is that of preconditioned iterative methods, involving preconditioners which are computationally cheap to apply while also capturing information contained in the linear system. In this article, we give a short survey of the field of preconditioning. We introduce a range of preconditioners for partial differential equations, followed by optimization problems, before discussing preconditioners constructed with less standard objectives in mind.

The solution of quadratic or locally quadratic extremum problems subject to linear(ized) constraints gives rise to linear systems in saddle point form. This is true whether in the continuous or the discrete setting, so saddle point systems arising from the discretization of partial differential equation problems, such as those describing electromagnetic problems or incompressible flow, lead to equations with this structure, as do, for example, interior point methods and the sequential quadratic programming approach to nonlinear optimization. This survey concerns iterative solution methods for these problems and, in particular, shows how the problem formulation leads to natural preconditioners which guarantee a fast rate of convergence of the relevant iterative methods. These preconditioners are related to the original extremum problem and their effectiveness---in terms of rapidity of convergence---is established here via a proof of general bounds on the eigenvalues of the preconditioned saddle point matrix on which iteration convergence depends.

This paper addresses the extension of the factorization of a Hermitian matrix by an eigenvalue decomposition (EVD) to the case of a parahermitian matrix that is analytic at least on an annulus containing the unit circle. Such parahermitian matrices contain polynomials or rational functions in the complex variable z and arise, e.g., as cross spectral density matrices in broadband array problems. Specifically, conditions for the existence and uniqueness of eigenvalues and eigenvectors of a parahermitian matrix EVD are given, such that these can be represented by a power or Laurent series that is absolutely convergent, at least on the unit circle, permitting a direct realization in the time domain. Based on an analysis of the unit circle, we prove that eigenvalues exist as unique and convergent but likely infinite-length Laurent series. The eigenvectors can have an arbitrary phase response and are shown to exist as convergent Laurent series if eigenvalues are selected as analytic functions on the unit circle, and if the phase response is selected such that the eigenvectors are Hölder continuous with α > 1/2 on the unit circle. In the case of a discontinuous phase response or if spectral majorisation is enforced for intersecting eigenvalues, an absolutely convergent Laurent series solution for the eigenvectors of a parahermitian EVD does not exist. We provide some examples, comment on the approximation of a parahermitian matrix EVD by Laurent polynomial factors, and compare our findings to the solutions provided by polynomial matrix EVD algorithms.

Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171--176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established.