Optimization of the Relaxation Parameter for S.S.O.R. and A.D.I. Preconditioning

We present and compare several approaches for the optimization of the relaxation parameter both for A.D.I. and S.S.O.R. basic iteration and preconditioning conjugate gradient method. For each kind of preconditioning a detailed link between estimates of the spectral radius of the iteration matrix and of the condition number resulting from preconditioning is proposed. It allows to choose the best approach in order to obtain the optimal relaxation parameter and the corresponding optimal estimates either of the spectral radius of the iteration matrix and of the resulting condition mumber of the S.S.O.R. and A.D.I. preconditioning.     

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.     

Construction of Matrices with Prescribed Singular Values and Eigenvalues

Two issues concerning the construction of square matrices with prescribe singular values an eigenvalues are addressed. First, a necessary and sufficient condition for the existence of an n × n complex matrix with n given nonnegative numbers as singular values an m ( n) given complex numbers to be m of the eigenvalues is determined. This extends the classical result of Weyl and Horn treating the case when m = n. Second, an algorithm is given to generate a triangular matrix with prescribe singular values an eigenvalues. Unlike earlier algorithms, the eigenvalues can be arranged in any prescribe order on the diagonal. A slight modification of this algorithm allows one to construct a real matrix with specified real an complex conjugate eigenvalues an specified singular values. The construction is done by multiplication by diagonal unitary matrices, permutation matrices and rotation matrices. It is numerically stable and may be useful in developing test software for numerical linear algebra packages.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

On the analysis of the unsymmetric successive overrelaxation method when applied top-cyclic matrices

Summary A Determinantal Invariance, associated with consistently ordered weakly cyclic matrices, is given. The DI is then used to obtain a new functional equation which relates the eigenvalues of a particular block Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix. This functional equation as well as the theory of nonnegative matrices and regular splittings are used to obtain convergence and divergence regions of the USSOR method.     

On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k × k (already reduced) sub-block will have the Lanczos–Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k × k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.     

The Singularity/Nonsingularity Problem for Matrices Satisfying Diagonal Dominance Conditions in Terms of Directed Graphs

The paper considers the singularity/nonsingularity problem for matrices satisfying certain conditions of diagonal dominance. The conditions considered extend the classical diagonal dominance conditions and involve the directed graph of the matrix in question. Furthermore, in the case of the so-called mixed diagonal dominance, the corresponding conditions are allowed to involve both row and column sums for an arbitrary finite set of matrices diagonally conjugated to the original matrix. Conditions sufficient for the nonsingularity of quasi-irreducible matrices strictly diagonally dominant in certain senses are established, as well as necessary and sufficient conditions of singularity/nonsingularity for weakly diagonally dominant matrices in the irreducible case. The results obtained are used to describe inclusion regions for eigenvalues of arbitrary matrices. In particular, a direct extension of the Gerschgorin (r = 1) and Ostrowski-Brauer (r = 2) theorems to r ≥ 3 is presented. Bibliography: 18 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 40–83.     

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     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

H‐self‐adjoint matrices. Application to radiosity

In computer graphics, in the radiosity context, a linear system Φx=b must be solved and there exists a diagonal positive matrix H such that H Φ is symmetric. In this article, we extend this property to complex matrices: we are interested in matrices which lead to Hermitian matrices under premultiplication by a Hermitian positive‐definite matrix H. We shall prove that these matrices are self‐adjoint with respect to a particular innerproduct defined on ?ⁿ. As a result, like Hermitian matrices, they have real eigenvalues and they are diagonalizable. We shall also show how to extend the Courant–Fisher theorem to this class of matrices. Finally, we shall give a new preconditioning matrix which really improves the convergence speed of the conjugate gradient method used for solving the radiosity problem. Copyright © 2002 John Wiley & Sons, Ltd.     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

Computable eigenvalue bounds for rank-k perturbations

We investigate lower bounds for the eigenvalues of perturbations of matrices. In the footsteps of Weyl and Ipsen & Nadler, we develop approximating matrices whose eigenvalues are lower bounds for the eigenvalues of the perturbed matrix. The number of available eigenvalues and eigenvectors of the original matrix determines how close those approximations can be, and, if the perturbation is of low rank, such bounds are relatively inexpensive to obtain. Moreover, because the process need not be restricted to the eigenvalues of perturbed matrices, lower bounds for eigenvalues of bordered diagonal matrices as well as for singular values of rank-k perturbations and other updates of n×m matrices are given.     

Domains of divergence of the USSOR method applied onp-cyclic matrices

Summary Using a recently derived classical type general functional equation, relating the eigenvalues of a weakly cyclic Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix, we obtain bounds for the convergence of the USSOR method, when applied to systems with ap-cyclic coefficient matrix.     

Parallel linear system solvers for Runge-Kutta methods

If the nonlinear systems arising in implicit Runge-Kutta methods like the Radau IIA methods are iterated by (modified) Newton, then we have to solve linear systems whose matrix of coefficients is of the form I-A hJ with A the Runge-Kutta matrix and J an approximation to the Jacobian of the righthand side function of the system of differential equations. For larger systems of differential equations, the solution of these linear systems by a direct linear solver is very costly, mainly because of the LU-decompositions. We try to reduce these costs by solving the linear systems by a second (inner) iteration process. This inner iteration process is such that each inner iteration again requires the solution of a linear system. However, the matrix of coefficients in these new linear systems is of the form I - B hJ where B is similar to a diagonal matrix with positive diagonal entries. Hence, after performing a similarity transformation, the linear systems are decoupled into s subsystems, so that the costs of the LU-decomposition are reduced to the costs of s LU-decompositions of dimension d. Since these LU-decompositions can be computed in parallel, the effective LU-costs on a parallel computer system are reduced by a factor s ³ . It will be shown that matrices B can be constructed such that the inner iterations converge whenever A and J have their eigenvalues in the positive and nonpositive halfplane, respectively. The theoretical results will be illustrated by a few numerical examples. A parallel implementation on the four-processor Cray-C98/4256 shows a speed-up ranging from at least 2.4 until at least 3.1 with respect to RADAU5 applied in one-processor mode.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Pseudospectra of rectangular matrices

Pseudospectra of rectangular matrices vary continuously withthe matrix entries, a feature that eigenvalues of these matricesdo not have. Some properties of eigenvalues and pseudospectraof rectangular matrices are explored, and an efficient algorithmfor the computation of pseudospectra is proposed. Applicationsare given in (square) eigenvalue computation (Lanczos iteration),square pseudospectra approximation (Arnoldi iteration), controltheory (nearest uncontrollable system) and game theory.     

EXPLICIT BOUNDS OF EIGENVALUES FOR STIFFNESS MATRICES BY QUADRATIC HIERARCHICAL BASIS METHOD)

The bounds for the eigenvalues of the stiffness matrices in the finite element discretiza-tion corresponding to Lu:=-u″with zero boundary conditions by quadratic hierarchical basic are shown explicitly.The condition numberof the resulting system behaves like O(1/h)where h is the mesh size.We also analyze a main diagonal preconditioner of the stiffness matrix which reduces the condition number of the preconditioned system to O(1).     

The solution of the additive eigenvalue problem of matrices

It is required to determine a diagonal matrix X such that the symmetric matrix A+X has preassigned eigenvalues (the additive problem). An iteration process is described that is based on the use of two-dimensional rotations, and convergence problems are analyzed.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 48, pp. 12–17, 1974.     

Modulus‐based matrix splitting iteration methods for linear complementarity problems

For the large sparse linear complementarity problems, by reformulating them as implicit fixed‐point equations based on splittings of the system matrices, we establish a class of modulus‐based matrix splitting iteration methods and prove their convergence when the system matrices are positive‐definite matrices and H₊‐matrices. These results naturally present convergence conditions for the symmetric positive‐definite matrices and the M‐matrices. Numerical results show that the modulus‐based relaxation methods are superior to the projected relaxation methods as well as the modified modulus method in computing efficiency. Copyright © 2009 John Wiley & Sons, Ltd.     

紧致交换矩阵半群

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