Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

Preconditioners for Ill-Conditioned Toeplitz Matrices

This paper is concerned with the solution of systems of linear equations A _N x = b, where denotes a sequence of positive definite Hermitian ill-conditioned Toeplitz matrices arising from a (real-valued) nonnegative generating function f C ₂ with zeros. We construct positive definite Hermitian preconditioners M _N such that the eigenvalues of M _N ^–1 A _N are clustered at 1 and the corresponding PCG-method requires only O(N log N) arithmetical operations to achieve a prescribed precision. We sketch how our preconditioning technique can be extended to symmetric Toeplitz systems, doubly symmetric block Toeplitz systems with Toeplitz blocks and non-Hermitian Toeplitz systems. Numerical tests confirm the theoretical expectations.     

Fast orthogonal decomposition of rank deficient Toeplitzmatrices

A 9mn-algorithm for computing an orthogonal factorization of a well-conditionedm×n Toeplitz matrixT was presented in Cybenko [8]. In the present paper we discuss extensions of this algorithm to cover rank deficient Toeplitz matrices that do not have many consecutive ill-conditioned submatricesT(:, 1:i) fori=1, ...,n. Our algorithms are stillO(mn).This work was supported by the Danish Technical Research Counsil, J. No. 16-4963-1, and the Danish Natural Science Research Counsil, J.No. 11-8977-1.     

Circulant Preconditioners for Indefinite Toeplitz Systems

In recent papers circulant preconditioners were proposed for ill-conditioned Hermitian Toeplitz matrices generated by 2-periodic continuous functions with zeros of even order. It was show that the spectra of the preconditioned matrices are uniformly bounded except for a finite number of outliers and therefore the conjugate gradient method, when applied to solving these circulant preconditioned systems, converges very quickly. In this paper, we consider indefinite Toeplitz matrices generated by 2-periodic continuous functions with zeros of odd order. In particular, we show that the singular values of the preconditioned matrices are essentially bounded. Numerical results are presented to illustrate the fast convergence of CGNE, MINRES and QMR methods.This revised version was published online in October 2005 with corrections to the Cover Date.     

Linear preservers and quantum information science

In this article, a brief survey of recent results on linear preserver problems and quantum information science is given. In addition, characterization is obtained for linear operators φ on mn?×?mn Hermitian matrices such that φ(A???B) and A???B have the same spectrum for any m?×?m Hermitian A and n?×?n Hermitian B. Such a map has the form A???B???U(?₁(A)????₂(B))U* for mn?×?mn Hermitian matrices in tensor form A???B, where U is a unitary matrix, and for j?∈?{1,?2}, ? _j is the identity map?X???X or the transposition map?X???X ^t . The structure of linear maps leaving invariant the spectral radius of matrices in tensor form A???B is also obtained. The results are connected to bipartite (quantum) systems and are extended to multipartite systems.     

Band plus algebra preconditioners for two-level Toeplitz systems

In this paper we are interested in the fast and efficient solution of nm×nm symmetric positive definite ill-conditioned Block Toeplitz with Toeplitz Blocks (BTTB) systems of the form T _nm (f)x=b, where the generating function f is a priori known. The preconditioner that we propose and analyze is an extension of the one proposed in (D. Noutsos and P. Vassalos, Comput. Math. Appl., 56 (2008), pp. 1255–1270) and it arises as a product of a Block band Toeplitz matrix and matrices that may belong to any trigonometric matrix algebra. The underlying idea of the proposed scheme is to embody the well known advantages characterizing each component of the product when used alone. As a result we obtain spectral equivalence and a weak clustering of the eigenvalues of the preconditioned matrix around unity, ensuring the convergence of the Preconditioned Conjugate Gradient (PCG) method with a number of iterations independent of the partial dimensions. Finally, we compare our method with techniques already employed in the literature. A wide range of numerical experiments confirms the effectiveness of the proposed procedure and the adherence to the theoretical analysis.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

A look-ahead Bareiss algorithm for general Toeplitz matrices

Summary. The Bareiss algorithm is one of the classical fast solvers for systems of linear equations with Toeplitz coefficient matrices. The method takes advantage of the special structure, and it computes the solution of a Toeplitz system of order~ with only~ arithmetic operations, instead of~ operations. However, the original Bareiss algorithm requires that all leading principal submatrices be nonsingular, and the algorithm is numerically unstable if singular or ill-conditioned submatrices occur. In this paper, an extension of the Bareiss algorithm to general Toeplitz systems is presented. Using look-ahead techniques, the proposed algorithm can skip over arbitrary blocks of singular or ill-conditioned submatrices, and at the same time, it still fully exploits the Toeplitz structure. Implementation details and operations counts are given, and numerical experiments are reported. We also discuss special versions of the proposed look-ahead Bareiss algorithm for Hermitian indefinite Toeplitz systems and banded Toeplitz systems. Received August 27, 1993 / Revised version received March 1994     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Toeplitz approximate inverse preconditioner for banded Toeplitz matrices

In this paper we introduce a new preconditioner for banded Toeplitz matrices, whose inverse is itself a Toeplitz matrix. Given a banded Hermitian positive definite Toeplitz matrixT, we construct a Toepliz matrixM such that the spectrum ofMT is clustered around one; specifically, if the bandwidth ofT is , all but eigenvalues ofMT are exactly one. Thus the preconditioned conjugate gradient method converges in +1 steps which is about half the iterations as required by other preconditioners for Toepliz systems that have been suggested in the literature. This idea has a natural extension to non-banded and non-Hermitian Toeplitz matrices, and to block Toeplitz matrices with Toeplitz blocks which arise in many two dimensional applications in signal processing. Convergence results are given for each scheme, as well as numerical experiments illustrating the good convergence properties of the new preconditioner.Partly supported by a travel fund from the Deutsche Forschungsgemeinschaft.Research supported in part by Oak Ridge Associated Universities grant no. 009707.     

Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

Staggered discontinuous Galerkin methods for the incompressible Navier–Stokes equations: Spectral analysis and computational results

The goal of this paper is to create a fruitful bridge between the numerical methods for approximating PDEs in fluid dynamics and the (iterative) numerical methods for dealing with the resulting large linear systems. Among the main objectives are the design of new, efficient iterative solvers and a rigorous analysis of their convergence speed. The link we have in mind is either the structure or the hidden structure that the involved coefficient matrices inherit, both from the continuous PDE and from the approximation scheme; in turn, the resulting structure is used for deducing spectral information, crucial for the conditioning and convergence analysis and for the design of more efficient solvers. As a specific problem, we consider the incompressible Navier–Stokes equations; as a numerical technique, we consider a novel family of high‐order, accurate discontinuous Galerkin methods on staggered meshes, and as tools, we use the theory of Toeplitz matrices generated by a function (in the most general block, the multilevel form) and the more recent theory of generalized locally Toeplitz matrix sequences. We arrive at a somehow complete picture of the spectral features of the underlying matrices, and this information is employed for giving a forecast of the convergence history of the conjugate gradient method, together with a discussion on new and more advanced techniques (involving preconditioning, multigrid, multi‐iterative solvers). Several numerical tests are provided and critically illustrated in order to show the validity and the potential of our analysis.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

Generalized iterative methods for semidefinite linear systems

We consider iterative methods for semidefinite systems Ax = b based on splittings A = B ? C, where B is not necessarily nonsingular. Necessary and sufficient conditions for convergence are obtained. These are then used to obtain convergence results for block SOR, block SSOR, and block JOR methods for matrices with semidefinite block diagonal.