Mapped barycentric Chebyshev differentiation matrix method for the solution of regular Sturm-Liouville problems

In this paper, using spectral differentiation matrix and an elimination treatment of boundary conditions, Sturm-Liouville problems (SLPs) are discretized into standard matrix eigenvalue problems. The eigenvalues of the original Sturm-Liouville operator are approximated by the eigenvalues of the corresponding Chebyshev differentiation matrix (CDM). This greatly improves the efficiency of the classical Chebyshev collocation method for SLPs, where a determinant or a generalized matrix eigenvalue problem has to be computed. Furthermore, the state-of-the-art spectral method, which incorporates the barycentric rational interpolation with a conformal map, is used to solve regular SLPs. A much more accurate mapped barycentric Chebyshev differentiation matrix (MBCDM) is obtained to approximate the Sturm-Liouville operator. Compared with many other existing methods, the MBCDM method achieves higher accuracy and efficiency, i.e., it produces fewer outliers. When a large number of eigenvalues need to be computed, the MBCDM method is very competitive. Hundreds of eigenvalues up to more than ten digits accuracy can be computed in several seconds on a personal computer.     

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     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.     

Comparison between the convergence rates of the Chebyshev method and the related (2,2)‐step methods

An optimal Chebyshev method for solving A x = b , where all the eigenvalues of the real and non‐symmetric matrix A are located in the open right half plane, is dependent on an optimal ellips∂Ω^* such that the spectrum of A is contrained in Ω^*, the closed interior of the ellipse. The relationship between the convergence rates of the Chebyshev method and the closely related (2,2)‐step iterative methods are studied. (2,2)‐step iterative methods are faster than an optimal Chebyshev method under certain conditions. A numerical example illustrates such an improvement of a (2,2)‐step iterative method. Copyright © 2000 John Wiley & Sons, Ltd.     

Numerical approximation of the spectra of Phan-Thien Tanner liquids

The linear stability of the linear Phan-Thien Tanner (PTT) fluid model is investigated for plane Poiseuille flow. The PTT model involves parameters that can be used to fit shear and extensional data, which makes it suitable for describing both polymer solutions and melts. The base flow is determined using a Chebyshev-tau method. The linear stability equations are also discretized using Chebyshev approximations to furnish a generalized eigenvalue problem. The spectrum is shown to comprise a continuous part and a discrete part. The theoretical and numerical results are validated for the UCM and Oldroyd-B models, which are special cases of the PTT model, by comparing with results in the literature. It is demonstrated that the linear extensional and elasticity parameters considered. The computational efficiency and accuracy of the numerical method are also investigated.     

Numerical Approximation of the Spectra of Phan-Thien Tanner Liquids

The linear stability of the linear Phan-Thien Tanner (PTT) fluid model is investigated for plane Poiseuille flow. The PTT model involves parameters that can be used to fit shear and extensional data, which makes it suitable for describing both polymer solutions and melts. The base flow is determined using a Chebyshev-tau method. The linear stability equations are also discretized using Chebyshev approximations to furnish a generalized eigenvalue problem. The spectrum is shown to comprise a continuous part and a discrete part. The theoretical and numerical results are validated for the UCM and Oldroyd-B models, which are special cases of the PTT model, by comparing with results in the literature. It is demonstrated that the linear PTT fluid is stable to infinitesimal disturbances with respect to the range of shear-thinning, extensional and elasticity parameters considered. The computational efficiency and accuracy of the numerical method are also investigated.     

Evaluation of Chebyshev pseudospectral methods for third order differential equations

When the standard Chebyshev collocation method is used to solve a third order differential equation with one Neumann boundary condition and two Dirichlet boundary conditions, the resulting differentiation matrix has spurious positive eigenvalues and extreme eigenvalue already reaching O(N ⁵ for N = 64. Stable time-steps are therefore very small in this case. A matrix operator with better stability properties is obtained by using the modified Chebyshev collocation method, introduced by Kosloff and Tal Ezer [3]. By a correct choice of mapping and implementation of the Neumann boundary condition, the matrix operator has extreme eigenvalue less than O(N ⁴. The pseudospectral and modified pseudospectral methods are implemented for the solution of one-dimensional third-order partial differential equations and the accuracy of the solutions compared with those by finite difference techniques. The comparison verifies the stability analysis and the modified method allows larger time-steps. Moreover, to obtain the accuracy of the pseudospectral method the finite difference methods are substantially more expensive. Also, for the small N tested, N ⩽ 16, the modified pseudospectral method cannot compete with the standard approach. This revised version was published online in August 2006 with corrections to the Cover Date.     

Efficient computation of the exponential operator for large,sparse, symmetric matrices

In this paper we compare Krylov subspace methods with Chebyshev series expansion for approximating the matrix exponential operator on large, sparse, symmetric matrices. Experimental results upon negative‐definite matrices with very large size, arising from (2D and 3D) FE and FD spatial discretization of linear parabolic PDEs, demonstrate that the Chebyshev method can be an effective alternative to Krylov techniques, especially when memory bounds do not allow the storage of all Ritz vectors. We also discuss the sensitivity of Chebyshev convergence to extreme eigenvalue approximation, as well as the reliability of various a priori and a posteriori error estimates for both methods. Copyright © 2000 John Wiley & Sons, Ltd.     

A hybrid iterative method for symmetric indefinite linear systems

Hybrid iterative methods that combine a conjugate direction method with a simpler iteration scheme, such as Chebyshev or Richardson iteration, were first proposed in the 1950s. The ease with which Chebyshev and Richardson iteration can be implemented efficiently on a large variety of computer architectures has in recent years lead to renewed interest in iterative methods that use Chebyshev or Richardson iteration. This paper presents a new hybrid iterative method for the solution of linear systems of equations with a symmetric indefinite matrix. Our method combines the conjugate residual method with Richardson iteration. Special attention is paid to the determination of two real intervals, one on each side of the origin, that contain most of the eigenvalues of the matrix. These intervals are used to compute suitable iteration parameters for Richardson iteration. We also discuss when to switch between the methods. The hybrid scheme typically uses the Richardson method for most iterations, and this reduces the number of arithmetic vector operations significantly compared with the number of arithmetic vector operations required when only the conjugate residual method is used. Computed examples illustrate the competitiveness of the hybrid scheme.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

On the numerical treatment of the eigenparameter dependent boundary conditions

In this paper, we consider the numerical treatment of singular eigenvalue problems supplied with eigenparameter dependent boundary conditions using spectral methods. On the one hand, such boundary conditions hinder the construction of test and trial space functions which could incorporate them and thus providing well-conditioned Galerkin discretization matrices. On the other hand, they can generate surprising behavior of the eigenvectors hardly detected by analytic methods. These singular problems are often indirectly approximated by regular ones. We argue that spectral collocation as well as tau method offer remedies for the first two issues and provide direct and efficient treatment to such problems. On a finite domain, we consider the so-called Petterson-König’s rod eigenvalue problem and on the half line, we take into account the Charney’s baroclinic stability problem and the Fourier eigenvalue problem. One boundary condition in these problems depends on the eigenparameter and additionally, this also could depend on some physical parameters. The Chebyshev collocation based on both, square and rectangular differentiation and a Chebyshev tau method are used to discretize the first problem. All these schemes cast the problems into singular algebraic generalized eigenvalue ones which are solved by the QZ and/or Arnoldi algorithms as well as by some target oriented Jacobi-Davidson methods. Thus, the spurious eigenvalues are completely eliminated. The accuracy of square Chebyshev collocation is roughly estimated and its order of approximation with respect to the eigenvalue of interest is determined. For the problems defined on the half line, we make use of the Laguerre-Gauss-Radau collocation. The method proved to be reliable, accurate, and stable with respect to the order of approximation and the scaling parameter.     

一类块三对角阵特征值的求解及应用

提出了求一类块三对角矩阵A的特征值和特征向量的方法,求得了该类矩阵的特征值和特征向量的表达式,并写出了用迭代法解该类方程组Au=f时迭代矩阵的特征值.     

Analysis of iterative methods for saddle point problems: a unified approach

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

     

An iterative method with error estimators

Iterative methods for the solution of linear systems of equations produce a sequence of approximate solutions. In many applications it is desirable to be able to compute estimates of the norm of the error in the approximate solutions generated and terminate the iterations when the estimates are sufficiently small. This paper presents a new iterative method based on the Lanczos process for the solution of linear systems of equations with a symmetric matrix. The method is designed to allow the computation of estimates of the Euclidean norm of the error in the computed approximate solutions. These estimates are determined by evaluating certain Gauss, anti-Gauss, or Gauss–Radau quadrature rules.     

Estimates of the trace of the inverse of a symmetric matrix using the modified Chebyshev algorithm

In this paper we study how to compute an estimate of the trace of the inverse of a symmetric matrix by using Gauss quadrature and the modified Chebyshev algorithm. As auxiliary polynomials we use the shifted Chebyshev polynomials. Since this can be too costly in computer storage for large matrices we also propose to compute the modified moments with a stochastic approach due to Hutchinson (Commun Stat Simul 18:1059–1076, 1989). In memory of Gene H. Golub.     

Free vibration of non-uniform Euler–Bernoulli beam under various supporting conditions using Chebyshev wavelet collocation method

This paper proposes operational matrix of rth integration of Chebyshev wavelets. A general procedure of this matrix is given. Operational matrix of rth integration is taken as rth power of operational matrix of first integration in literature. But, this study removes this disadvantage of Chebyshev wavelets method. Free vibration problems of non-uniform Euler–Bernoulli beam under various supporting conditions are investigated by using Chebyshev Wavelet Collocation Method. The proposed method is based on the approximation by the truncated Chebyshev wavelet series. A homogeneous system of linear algebraic equations has been obtained by using the Chebyshev collocation points. The determinant of coefficients matrix is equated to the zero for nontrivial solution of homogeneous system of linear algebraic equations. Hence, we can obtain ith natural frequencies of the beam and the coefficients of the approximate solution of Chebyshev wavelet series that satisfied differential equation and boundary conditions. Mode shapes functions corresponding to the natural frequencies can be obtained by normalizing of approximate solutions. The computed results well fit with the analytical and numerical results as in the literature. These calculations demonstrate that the accuracy of the Chebyshev wavelet collocation method is quite good even for small number of grid points.     

Wavelet-like bases for thin-wire integral equations in electromagnetics

In this paper, wavelets are used in solving, by the method of moments, a modified version of the thin-wire electric field integral equation, in frequency domain. The time domain electromagnetic quantities, are obtained by using the inverse discrete fast Fourier transform. The retarded scalar electric and vector magnetic potentials are employed in order to obtain the integral formulation. The discretized model generated by applying the direct method of moments via point-matching procedure, results in a linear system with a dense matrix which have to be solved for each frequency of the Fourier spectrum of the time domain impressed source. Therefore, orthogonal wavelet-like basis transform is used to sparsify the moment matrix. In particular, dyadic and M-band wavelet transforms have been adopted, so generating different sparse matrix structures. This leads to an efficient solution in solving the resulting sparse matrix equation. Moreover, a wavelet preconditioner is used to accelerate the convergence rate of the iterative solver employed. These numerical features are used in analyzing the transient behavior of a lightning protection system. In particular, the transient performance of the earth termination system of a lightning protection system or of the earth electrode of an electric power substation, during its operation is focused. The numerical results, obtained by running a complex structure, are discussed and the features of the used method are underlined.     

Some sixth order zero-finding variants of Chebyshev-Halley methods

A zero-finding technique in which the order of convergence is improved and nonlinear equations are solved more efficiently than they are solved by traditional iterative methods is derived. Composing a modified Chebyshev-Halley method with a variant of this method that just introduces one evaluation of the function the iterative methods presented are obtained. By carrying out this procedure the output numerical results show that the new methods compete in both order and efficiency with the modified Chebyshev-Halley methods.