A skew-symmetric iterative method for solving a steady convection–diffusion–reaction equation with an indefinite reaction coefficient

An iterative product-type triangular skew-symmetric method (PTSM) is used to solve systems of linear algebraic equations (SLAEs) obtained by approximation with a central-difference scheme of a first-type boundary value problem for convection–diffusion–reaction and standard grid ordering. Sufficient conditions for non-negative definiteness of the SLAE matrix resulting from this approximation are obtained for the indefinite reaction coefficient. This property provides convergence of a wide class of iterative methods (in particular, the PTSM). In test problems, agreement of the theory with computational experiments is shown, and a comparison of the PTSM and SSOR is done.     

Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method

We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.     

Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems

Summary A variety of iterative methods considered in [3] are applied to linear algebraic systems of the formAu=b, where the matrixA is consistently ordered [12] and the iteration matrix of the Jacobi method is skew-symmetric. The related theory of convergence is developed and the optimum values of the involved parameters for each considered scheme are determined. It reveals that under the aforementioned assumptions the Extrapolated Successive Underrelaxation method attains a rate of convergence which is clearly superior over the Successive Underrelaxation method [5] when the Jacobi iteration matrix is non-singular.     

On the preconditioning of matrices with skew-symmetric splittings

The rates of convergence of iterative methods with standard preconditioning techniques usually degrade when the skew-symmetric part S of the matrix is relatively large. In this paper, we address the issue of preconditioning matrices with such large skew-symmetric parts. The main idea of the preconditioner is to split the matrix into its symmetric and skew-symmetric parts and to invert the (shifted) skew-symmetric matrix. Successful use of the method requires the solution of a linear system with matrix I+S. An efficient method is developed using the normal equations, preconditioned by an incomplete orthogonal factorization.Numerical experiments on various systems arising in physics show that the reduction in terms of iteration count compensates for the additional work per iteration when compared to standard preconditioners.     

Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

Sine transform based preconditioning techniques for space fractional diffusion equations

We study the preconditioned iterative methods for the linear systems arising from the numerical solution of the multi-dimensional space fractional diffusion equations. A sine transform based preconditioning technique is developed according to the symmetric and skew-symmetric splitting of the Toeplitz factor in the resulting coefficient matrix. Theoretical analyses show that the upper bound of relative residual norm of the GMRES method when applied to the preconditioned linear system is mesh-independent which implies the linear convergence. Numerical experiments are carried out to illustrate the correctness of the theoretical results and the effectiveness of the proposed preconditioning technique.     

Numerical Stability in the Presence of Variable Coefficients

The main concern of this paper is with the stable discretisation of linear partial differential equations of evolution with time-varying coefficients. We commence by demonstrating that an approximation of the first derivative by a skew-symmetric matrix is fundamental in ensuring stability for many differential equations of evolution. This motivates our detailed study of skew-symmetric differentiation matrices for univariate finite-difference methods. We prove that, in order to sustain a skew-symmetric differentiation matrix of order \(p\ge 2\), a grid must satisfy \(2p-3\) polynomial conditions. Moreover, once it satisfies these conditions, it supports a banded skew-symmetric differentiation matrix of this order and of the bandwidth \(2p-1\), which can be derived in a constructive manner. Some applications require not just skew-symmetry, but also that the growth in the elements of the differentiation matrix is at most linear in the number of unknowns. This is always true for our tridiagonal matrices of order 2 but need not be true otherwise, a subject which we explore further. Another subject which we examine is the existence and practical construction of grids that support skew-symmetric differentiation matrices of a given order. We resolve this issue completely for order-two methods. We conclude the paper with a list of open problems and their discussion.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

求矩阵方程组的反对称最小二乘解的递推算法

讨论了矩阵方程组A_1XB_1=D_1,A_2XB_2=D_2反对称最小二乘解的递推算法,该算法不仅能够用于计算反对称最小二乘解,而且在选取特殊的初始矩阵时,算法能够求出矩阵方程组的极小范数反对称最小二乘解,以及对给定的矩阵进行最佳逼近的反对称解.     

On some algebraic problems in connection with general elgenvalue algorithms

Two real matrices A,B are S-congruent if there is a nonsingular upper triangular matrix R such that A = R^TBR. This congruence relation is studied in the set of all nonsingular symmetric and that of all skew-symmetric matrices. Invariants and systems of representation are give. The results are applied to the question of decomposability of a matrix in a product of an isometry and an upper triangular matrix, a problem crucial in eigenvalue algorithms.     

Shifted skew-symmetric iteration methods for nonsymmetric linear complementarity problems

We present a shifted skew-symmetric iteration method for solving the nonsymmetric positive definite or positive semidefinite linear complementarity problems. This method is based on the symmetric and skew-symmetric splitting of the system matrix, which has been adopted to establish efficient splitting iteration methods for solving the nonsymmetric systems of linear equations. Global convergence of the method is proved, and the corresponding inexact splitting iteration scheme is established and analyzed in detail. Numerical results show that the new methods are feasible and effective for solving large sparse and nonsymmetric linear complementarity problems.     

Skew-Hermitian Triangular Splitting Iteration Methods for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts

By further generalizing the skew-symmetric triangular splitting iteration method studied by Krukier, Chikina and Belokon (Applied Numerical Mathematics, 41 (2002), pp. 89–105), in this paper, we present a new iteration scheme, called the modified skew-Hermitian triangular splitting iteration method, for solving the strongly non-Hermitian systems of linear equations with positive definite coefficient matrices. We discuss the convergence property and the optimal parameters of this new method in depth. Moreover, when it is applied to precondition the Krylov subspace methods like GMRES, the preconditioning property of the modified skew-Hermitian triangular splitting iteration is analyzed in detail. Numerical results show that, as both solver and preconditioner, the modified skew-Hermitian triangular splitting iteration method is very effective for solving large sparse positive definite systems of linear equations of strong skew-Hermitian parts.     

A shift-splitting hierarchical identification method for solving Lyapunov matrix equations

In the present paper, we propose a hierarchical identification method (SSHI) for solving Lyapunov matrix equations, which is based on the symmetry and skew-symmetry splitting of the coefficient matrix. We prove that the iterative algorithm consistently converges to the true solution for any initial values with some conditions, and illustrate that the rate of convergence of the iterative solution can be enhanced by choosing the convergence factors appropriately. Furthermore, we show that the method adopted can be easily extended to study iterative solutions of other matrix equations, such as Sylvester matrix equations. Finally, we test the algorithms and show their effectiveness using numerical examples.     

Iterative solutions to coupled Sylvester-transpose matrix equations

This note studies the iterative solutions to the coupled Sylvester-transpose matrix equation with a unique solution. By using the hierarchical identification principle, an iterative algorithm is presented for solving this class of coupled matrix equations. It is proved that the iterative solution consistently converges to the exact solution for any initial values. Meanwhile, sufficient conditions are derived to guarantee that the iterative solutions given by the proposed algorithm converge to the exact solution for any initial matrices. Finally, a numerical example is given to illustrate the efficiency of the proposed approach.     

Exponentials of skew-symmetric matrices and logarithms of orthogonal matrices

Two widely used methods for computing matrix exponentials and matrix logarithms are, respectively, the scaling and squaring and the inverse scaling and squaring. Both methods become effective when combined with Padé approximation. This paper deals with the computation of exponentials of skew-symmetric matrices and logarithms of orthogonal matrices. Our main goal is to improve these two methods by exploiting the special structure of skew-symmetric and orthogonal matrices. Geometric features of the matrix exponential and logarithm and extensions to the special Euclidean group of rigid motions are also addressed.     

A note on Hermitian splitting induced relaxation methods for convection-diffusion equations

The solution of the linear system Ax = b by iterative methods requires a splitting of the coefficient matrix in the form A = M − N where M is usually chosen to be a diagonal or a triangular matrix. In this article we study relaxation methods induced by the Hermitian and skew-Hermitian splittings for the solution of the linear system arising from a compact fourth order approximation to the one dimensional convection-diffusion equation and compare the convergence rates of these relaxation methods to that of the widely used successive overrelaxation (SOR) method. Optimal convergence parameters are derived for each method and numerical experiments are given to supplement the theoretical estimates. For certain values of the diffusion parameter, a relaxation method based on the Hermitian splitting converges faster than SOR. For two-dimensional problems a block form of the iterative algorithm is presented. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 581–591, 1998     

Existence of solutions of the classical yang- baxter equation for a real lie Algebra

We characterize finite-dimensional Lie algebras over the real numbers for which the classical Yang-Baxter equation has a non-trivial skew-symmetric solution (resp. a non-trivial solution with invariant symmetric part). Equivalently, we obtain a characterization of those finite-dimensional real Lie algebras which admit a non-trivial (quasi-) triangular Lie bialgebra structure.     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

Multigrid method for solving convection-diffusion problems with dominant convection

A modification of the multigrid method for the solution of linear algebraic equation systems with a strongly nonsymmetric matrix obtained after difference approximation of the convection-diffusion equation with dominant convection is proposed. Specially created triangular iterative methods have been used as the smoothers of the multigrid method. Some theoretical and numerical results are presented.