Preconditioning cubic spline collocation discretizations of elliptic equations

Summary. This work considers the uniformly elliptic operator defined by in (the unit square) with boundary conditions: on and on and its discretization based on Hermite cubic spline spaces and collocation at the Gauss points. Using an interpolatory basis with support on the Gauss points one obtains the matrix . We discuss the condition numbers and the distribution of -singular values of the preconditioned matrices where is the stiffness matrix associated with the finite element discretization of the positive definite uniformly elliptic operator given by in with boundary conditions: on on . The finite element space is either the space of continuous functions which are bilinear on the rectangles determined by Gauss points or the space of continuous functions which are linear on the triangles of the triangulation of using the Gauss points. When we obtain results on the eigenvalues of . In the general case we obtain bounds and clustering results on the -singular values of . These results are related to the results of Manteuffel and Parter [MP], Parter and Wong [PW], and Wong [W] for finite element discretizations as well as the results of Parter and Rothman [PR] for discretizations based on Legendre Spectral Collocation. Received January 1, 1994 / Revised version received February 7, 1995     

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14], it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper is to give a complete convergence proof of the method in [10,14] for this class of generating functions. Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001     

Deflated GMRES for systems with multiple shifts and multiple right-hand sides

We consider solution of multiply shifted systems of nonsymmetric linear equations, possibly also with multiple right-hand sides. First, for a single right-hand side, the matrix is shifted by several multiples of the identity. Such problems arise in a number of applications, including lattice quantum chromodynamics where the matrices are complex and non-Hermitian. Some Krylov iterative methods such as GMRES and BiCGStab have been used to solve multiply shifted systems for about the cost of solving just one system. Restarted GMRES can be improved by deflating eigenvalues for matrices that have a few small eigenvalues. We show that a particular deflated method, GMRES-DR, can be applied to multiply shifted systems.In quantum chromodynamics, it is common to have multiple right-hand sides with multiple shifts for each right-hand side. We develop a method that efficiently solves the multiple right-hand sides by using a deflated version of GMRES and yet keeps costs for all of the multiply shifted systems close to those for one shift. An example is given showing this can be extremely effective with a quantum chromodynamics matrix.     

Eigenvalue estimates for a preconditioned Galerkin matrix arising from mixed finite element discretizations of viscous incompressible flows

The article deals with Galerkin matrices arising with finite element discretizations of the Navier–Stokes system. Usually these matrices are indefinite and nonsymmetric. They have to be preconditioned if a related linear system is to be solved efficiently by an iterative method. We consider preconditioning by a pressure mass matrix. It is shown how upper and lower bounds of the eigenvalues of a preconditioned Galerkin matrix may be found by variational arguments.     

Algorithms for solving Hermite interpolation problems using the Fast Fourier Transform

We present a method for computing the Hermite interpolation polynomial based on equally spaced nodes on the unit circle with an arbitrary number of derivatives in the case of algebraic and Laurent polynomials. It is an adaptation of the method of the Fast Fourier Transform (FFT) for this type of problems with the following characteristics: easy computation, small number of operations and easy implementation.In the second part of the paper we adapt the algorithm for computing the Hermite interpolation polynomial based on the nodes of the Tchebycheff polynomials and we also study Hermite trigonometric interpolation problems.     

Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

Biorthogonal Rational Functions and the Generalized Eigenvalue Problem

We present some general results concerning so-called biorthogonal polynomials of R_II type introduced by M. Ismail and D. Masson. These polynomials give rise to a pair of rational functions which are biorthogonal with respect to a linear functional. It is shown that these rational functions naturally appear as eigenvectors of the generalized eigenvalue problem for two arbitrary tri-diagonal matrices. We study spectral transformations of these functions leading to a rational modification of the linear functional. An analogue of the Christoffel–Darboux formula is obtained.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

Operator adapted spectral element methods I: harmonic and generalized harmonic polynomials

Summary. The paper presents results on the approximation of functions which solve an elliptic differential equation by operator adapted systems of functions. Compared with standard polynomials, these operator adapted systems have superior local approximation properties. First, the case of Laplace's equation and harmonic polynomials as operator adapted functions is analyzed and rates of convergence in a Sobolev space setting are given for the approximation with harmonic polynomials. Special attention is paid to the approximation of singular functions that arise typically in corners. These results for harmonic polynomials are extended to general elliptic equations with analytic coefficients by means of the theory of Bergman and Vekua; the approximation results for Laplace's equation hold true verbatim, if harmonic polynomials are replaced with generalized harmonic polynomials. The Partition of Unity Method is used in a numerical example to construct an operator adapted spectral method for Laplace's equation that is based on approximating with harmonic polynomials locally. Received May 26, 1997 / Revised version received September 21, 1998 / Published online September 7, 1999     

A note on conjugate gradient convergence – Part III

Summary. In this paper we again consider the rate of convergence of the conjugate gradient method. We start with a general analysis of the conjugate gradient method for uniformly bounded solutions vectors and matrices whose eigenvalues are uniformly bounded and positive. We show that in such cases a fixed finite number of iterations of the method gives some fixed amount of improvement as the the size of the matrix tends to infinity. Then we specialize to the finite element (or finite difference) scheme for the problem . We show that for some classes of function we see this same effect. For other functions we show that the gain made by performing a fixed number of iterations of the method tends to zero as the size of the matrix tends to infinity. Received July 9, 1998 / Published online March 16, 2000     

ON HERMITE MATRIX POLYNOMIALS AND HERMITE MATRIX FUNCTIONS

In this paper properties of Hermite matrix polynomials and Hermite matrix functions are studied. The concept ot total set with respect to a matrix functional is introduced and the total property of the Hermite matrix polynomials is proved. Asymptotic behaviour of Hermite matrix polynomials is studied and the relationship of Hermite matrix functions with certain matrix differential equations is developed. A new expression of the matrix exponential for a wide class of matrices in terms of Hermite matrix polynomials is proposed.     

Biorthogonal Laurent Polynomials,Toplitz Determinants,Minimal Toda Orbits and Isomonodromic Tau Functions

We consider the class of biorthogonal polynomials that are used to solve the inverse spectral problem associated to elementary co-adjoint orbits of the Borel group of upper triangular matrices; these orbits are the phase space of generalized integrable lattices of Toda type. Such polynomials naturally interpolate between the theory of orthogonal polynomials on the line and orthogonal polynomials on the unit circle and tie together the theory of Toda, relativistic Toda, Ablowitz-Ladik and Volterra lattices. We establish corresponding Christoffel-Darboux formulae. For all these classes of polynomials a 2 × 2 system of Differential-Difference-Deformation equations is analyzed in the most general setting of pseudo-measures with arbitrary rational logarithmic derivative. They provide particular classes of isomonodromic deformations of rational connections on the Riemann sphere. The corresponding isomonodromic tau function is explicitly related to the shifted Toplitz determinants of the moments of the pseudo-measure. In particular, the results imply that any (shifted) Toplitz (Hankel) determinant of a symbol (measure) with arbitrary rational logarithmic derivative is an isomonodromic tau function.     

紧致交换矩阵半群

通过将矩阵同时对角化或同时上三角化的方法,给出有关紧致Abel矩阵半群以及紧致Hermite矩阵半群中矩阵的特征值的一些很好的刻画,证明了由可逆的Hermite矩阵构成的紧致矩阵半群中每个矩阵的特征值都是±1,Hermite矩阵单半群相似于对角矩阵半群,紧致交换矩阵半群的谱半径不超过1,等等.     

Interlacing of the zeros of contiguous hypergeometric functions

It is well-known that hypergeometric functions satisfy first order difference-differential equations (DDEs) with rational coefficients, relating the first derivative of hypergeometric functions with functions of contiguous parameters (with parameters differing by integer numbers). However, maybe it is not so well known that the continuity of the coefficients of these DDEs implies that the real zeros of such contiguous functions are interlaced. Using this property, we explore interlacing properties of hypergeometric and confluent hypergeometric functions (Bessel functions and Hermite, Laguerre and Jacobi polynomials as particular cases).     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

Random block matrices generalizing the classical Jacobi and Laguerre ensembles

In this paper we consider random block matrices which generalize the classical Laguerre ensemble and the Jacobi ensemble. We show that the random eigenvalues of the matrices can be uniformly approximated by the zeros of matrix orthogonal polynomials and obtain a rate for the maximum difference between the eigenvalues and the zeros. This relation between the random block matrices and matrix orthogonal polynomials allows a derivation of the asymptotic spectral distribution of the matrices.     

Some conditional expectation identities for the multivariate normal

We give formulas for the conditional expectations of a product of multivariate Hermite polynomials with multivariate normal arguments. These results are extended to include conditional expectations of a product of linear combination of multivariate normals. A unified approach is given that covers both Hermite and modified Hermite polynomials, as well as polynomials associated with a matrix whose eigenvalues may be both positive and negative.     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented