块AOR迭代法的收敛性

本文推广了解线性方程组的AOR迭代法,给出了块AOR迭代法(BAOR迭代法).文中引进了块M-矩阵,块H-矩阵,块严格对角优势矩阵,块Hermite正定矩阵,块相容次序矩阵和广义块相容次序矩阵等概念.在线性方程组的系数矩阵分别具有上述性质的假设下,讨论了BAOR迭代法的敛散性.     

幂幺矩阵的充要条件

研究幂幺矩阵的充要条件,利用矩阵的秩和齐次线性方程组解空间的维数.将m=2时幂幺矩阵的充要条件推广到一般幂幺矩阵的充要条件,得出了幂幺矩阵可对角化的结果,并将幂幺矩阵的充要条件平行地推广到幂幺线性变换.     

Preconditioning indefinite discretization matrices

Summary The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can also be used for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case.     

Vandermonde方程Hilbert方程及Vandermonde矩阵Hilbert矩阵逆的快速与并行算法

1.引言 众所周知,在并行数值代数研究中,降低矩阵求逆与线性方程组求解并行步是一个相当困难的问题。1976年Csanky证明了上述两问题均可在O(log~2n)并行步内完成,所用处理机台数为O(n~4)。然而能否找到时间步为O(logn)的并行算法,长期以来是人们极为关注的问题之一。对于特殊矩阵及方程的研究更是如此。目前除几个极其特殊的     

Fast transforms for tridiagonal linear equations

In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern ²×n ² in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.     

Methods of stabilizing or destabilizing a switched linear system

This paper shows that the stability or nonstability of switched systems does not depend on the eigenvalues of the matrices. The result is obtained by giving examples of no stable (resp. no unstable) switched linear systems consisting of stable (resp. unstable) matrices. Moreover, for the first time all kinds of eigenvalues are considered, as well as two general results for establishing the stability or nonstability of switched linear systems are presented.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

m次幂等矩阵的等价条件

利用矩阵的秩和齐次线性方程组解空间的维数,给出了m(m≥2)次幂等矩阵的一些等价条件,推广了2,3次幂等矩阵的相应结果.此外,所获结果还给推广到了m次幂等线性变换中.     

New features of stability of linear systems of differential equations with constant coefficients

We consider stability of linear systems of differential equations with constant real coefficients whose matrices are off-diagonally non-negative. The results are applied to arbitrary linear systems of differential equations with constant complex coefficients.     

Applications of statistical condition estimation to the solution of linear systems

This paper discusses some applications of statistical condition estimation (SCE) to the problem of solving linear systems. Specifically, triangular and bidiagonal matrices are studied in some detail as typical of structured matrices. Such a structure, when properly respected, leads to condition estimates that are much less conservative compared with traditional non‐statistical methods of condition estimation. Some examples of linear systems and Sylvester equations are presented. Vandermonde and Cauchy matrices are also studied as representative of linear systems with large condition numbers that can nonetheless be solved accurately. SCE reflects this. Moreover, SCE when applied to solving very large linear systems by iterative solvers, including conjugate gradient and multigrid methods, performs equally well and various examples are given to illustrate the performance. SCE for solving large linear systems with direct methods, such as methods for semi‐separable structures, are also investigated. In all cases, the advantages of using SCE are manifold: ease of use, efficiency, and reliability. Copyright © 2008 John Wiley & Sons, Ltd.     

On the boundedness of outer polyhedral estimates for reachable sets of linear systems

New properties of outer polyhedral (parallelepipedal) estimates for reachable sets of linear differential systems are studied. For systems with a stable matrix, it is determined what the orientation matrices are for which the estimates possessing the generalized semigroup property are bounded/unbounded on an infinite time interval. In particular, criteria are found (formulated in terms of the eigenvalues of the system’s matrix and the properties of bounding sets) that guarantee for previously mentioned tangent estimates and estimates with a constant orientation matrix that either there are initial orientation matrices for which the corresponding estimate tubes are bounded or all these tubes are unbounded. For linear stationary systems, a system of ordinary differential equations and algebraic relations is derived that determines estimates with constant orientation matrices for reachable sets that have no generalized semigroup property but are tangent and also bounded if the matrix of the system is stable.     

CHARACTERISTIC MATRICES AND SIMILARITY OF TIME-VARYING LINEAR DIFFERENTIAL SYSTEMS

1IntroductionLineardial'~rentialsystemsa.rethesimplestmod(}lsinmotiolls,tijoyarcwidelyusedincontroltheory,Inechanlcsandengineel'illg.Invest;igationsoiltileasymptoticpropertiesoftinea,rSystclllshay')oss(3ntialsense.Fbi'tilelin(3arsy'stemswithconstantcoeffi…     

Low-rank perturbations of normal and conjugate-normal matrices and their condensed forms under unitary similarities and congruences

Two theorems are proved on the condensed forms with respect to unitary similarity and congruence transformations. They provide a theoretical basis for constructing economical iterative methods for systems of linear equations whose matrices are low-rank perturbations of normal and conjugate-normal matrices.     

A kind of nonnegative matrices and its application on the stability of discrete dynamical systems

In this paper we introduce a new kind of nonnegative matrices which is called (sp) matrices. We show that the zero solutions of a class of linear discrete dynamical systems are asymptotically stable if and only if the coefficient matrices are (sp) matrices. To determine that a matrix is (sp) matrix or not is very simple, we need only to verify that some elements of the coefficient matrices are zero or not. According to the result above, we obtain the conditions for the stability of several classes of discrete dynamical systems.     

Block ILU-preconditioners for problems of filtration of a multicomponent mixture in a porous medium

ILU class preconditioners (ILU(0), ILU(1), ILUT) employed for iterative algorithms for asymmetric linear systems with sparse matrices are considered. Test matrices used in this study originate from discretization of systems of partial differential equations describing a multicomponent fluid flow in porous media. New algorithms for block storage of matrices and block based ILU-factorization are described. This new integrated approach was tested on a wide range of matrices resulted from actual hydrodynamic simulations of oil fields in Western Siberia and had demonstrated significant reduction of computational time.     

On some class of periodic-discrete homogeneous difference equations via Fibonacci sequences

The intent of this paper is to solve the homogeneous linear difference equations with periodic coefficients. For this purpose, we turn our study in solving a class of discrete-time linear systems, in the algebra of square matrices. The tools used repose predominately on the combinatorial properties of the generalized Fibonacci sequences in the algebra of square matrices. Some explicit solutions are established and special cases are discussed. Illustrative examples are given.     

Almost periodic homogeneous linear difference systems without almost periodic solutions

Almost periodic homogeneous linear difference systems are considered. It is supposed that the coefficient matrices belong to a group. The aim was to find such groups that the systems having no non-trivial almost periodic solution form a dense subset of the set of all considered systems. A closer examination of the used methods reveals that the problem can be treated in such a generality that the entries of coefficient matrices are allowed to belong to any complete metric field. The concepts of transformable and strongly transformable groups of matrices are introduced, and these concepts enable us to derive efficient conditions for determining what matrix groups have the required property.     

The width and integer optimization on simplices with bounded minors of the constraint matrices

In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.     

On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.