Ein quadratisch konvergentes Verfahren zur Eigenwertbestimmung bei unsymmetrischen Matrizen I

Summary J. C. F. Francis proposes for the determination of eigenvalues of an arbitrary matrix theQR-transformation which is a unitary analogue of theLR-transformation. In this process the current approximation matrix is always factorized into a unitary and a triangular matrix and the 2 factors are multiplied together in reverse order; this yields the next approximant. The present paper shows how this process may be extended to a process which transforms a given matrix with quadratic convergence orthogonally toWintner-Murnaghan's normal form. The process is formulated in the real domain.     

A parallel interior point algorithm for linear programming on a network of transputers

Interior Point algorithms have become a very successful tool for solving large-scale linear programming problems. The Dual Affine algorithm is one of the Interior Point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel Dual Affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorisation, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequentialFortran 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.     

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.     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

Numerical linear algorithms and group theory

Most methods for solving linear systems Ax=b are founded on the ability to split up the matrix A in the form of a product A=G·R with G belonging to a subgroup of the general linear group Gl(n,R) and R being a regular upper triangular matrix. In the same way, the calculation of the eigenvalues of a matrix by the use of an algorithm of the Rutishauser type is based on a G·R decomposition for the matrix. Our aim in this article will be to show the importance of the notion of splitting up, to set out the conditions under which it may be used and to show how it enables us to generate new algorithms.     

保持交换环上两类矩阵运算的映射

主要针对交换环上两类矩阵的保持问题进行展开:(1)刻画了交换环上全矩阵空间和上三角形矩阵空间的保持反对合矩阵映射的形式.(2)研究了交换环上n阶上三角形矩阵空间的保持伴随矩阵映射的形式.     

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.     

非负矩阵的一些算法

本文利用有限图论和齐次有限马尔可夫链理论的有关命题和算法得到了不同于[1]、[3]的算法:(1)有限阶非负矩阵可约性的判别、有限阶可约矩阵化为主对角线上都为不可约子块的分块三角阵的算法;(2)有限阶不可约矩阵的Frobenius表示的算法.对上述二算法本文还分别给出了直观简便的图示法.     

Globally hypoelliptic triangularizable systems of periodic pseudo-differential operators

This paper presents an investigation on the global hypoellipticity problem for a class of systems of pseudo-differential operators on the torus. The approach consists in establishing conditions on the matrix symbol of the system such that it can be transformed into a suitable triangular form involving a nilpotent upper triangular matrix. Hence, the global hypoellipticity is studied by analyzing the behavior of the eigenvalues and their averages.     

Derived Equivalences of Upper Triangular Differential Graded Algebras

This paper generalises a result for upper triangular matrix rings to the situation of upper triangular matrix differential graded algebras. An upper triangular matrix DGA has the form (R, S, M) where R and S are differential graded algebras and M is a DG-left-R-right-S-bimodule. We show that under certain conditions on the DG-module M and with the existance of a DG-R-module X, from which we can build the derived category D(R), that there exists a derived equivalence between the upper triangular matrix DGAs (R, S, M) and (S, M′, R′), where the DG-bimodule M′ is obtained from M and X and R′ is the endomorphism differential graded algebra of a K-projective resolution of X.     

Riesz points of upper triangular operator matrices

Two results are proved which concern Riesz points of upper triangular operator matrices. Applications are made to questions involving when Weyl's Theorem holds for an upper triangular operator matrix.

     

A block Cholesky-LU-based QR factorization for rectangular matrices

The Householder method provides a stable algorithm to compute the full QR factorization of a general matrix. The standard version of the algorithm uses a sequence of orthogonal reflections to transform the matrix into upper triangular form column by column. In order to exploit (level 3 BLAS or structured matrix) computational advantages for block-partitioned algorithms, we develop a block algorithm for the QR factorization. It is based on a well-known block version of the Householder method which recursively divides a matrix columnwise into two smaller matrices. However, instead of continuing the recursion down to single matrix columns, we introduce a novel way to compute the QR factors in implicit Householder representation for a larger block of several matrix columns, that is, we start the recursion at a block level instead of a single column. Numerical experiments illustrate to what extent the novel approach trades some of the stability of Householder's method for the computational efficiency of block methods.     

Bezoutian矩阵的一致逼近形式

借助闭区间上的连续函数可以用Bernstein 多项式一致逼近这一事实,将多项式对所生成的经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵推广到C [0,1]上函数对所对应的情形,给出了 Bezoutian 矩阵一致逼近形式的定义,并且得到如下结论：给出了经典 Bezoutian 矩阵的 Barnett 型分解公式和三角分解公式的一致逼近形式;提供了经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵的一致逼近形式的两类算法;得到了上述两种矩阵的一致逼近形式中元素间的两个恒等关系式。最后,利用数值实例对恒等关系式进行验证,结果表明两类算法是有效的。     

The canonical structure of a pencil of degenerate matrix functions

In this paper we study global properties of a pencil of identically degenerate matrix functions with a compact domain of definition. Matrix functions are assumed to have a constant rank and all roots of the characteristic equation of the matrix pencil are assumed to have a constant multiplicity at each point in the domain of definition. We obtain sufficient conditions for the smooth orthogonal similarity of matrix functions to the upper triangular form and sufficient conditions for the smooth equivalence of the pencil of matrix functions to its canonical form. We illustrate the obtained results with simple examples.     

Algorithms over partially ordered sets

We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.     

特征值问题的预变换方法(I): 杨辉三角阵变换与二阶PDE 特征多项式

本文提出一类求解特征值问题的下三角预变换方法, 目标是通过相似变换后矩阵下三角元素平方和明显减少、且变换后的特征值及其特征向量较易求解, 使变换后的对角线可作为全体特征值很好的一组初值, 其作用如同对于解方程组找到好的预条件子, 加速迭代收敛. 以二阶PDE 数值计算为例,对于以Laplace 方程为代表的特征波向量组及正交多项式组有广泛的应用前景.
杨辉三角是我国古代数学家的一项重要成就. 本文引入杨辉三角矩阵作为预变换子, 给出一般矩阵用杨辉三角矩阵作为左、右预变换子时变为上三角矩阵的充要条件, 给出了元素为行指标二次多项式的两个矩阵类(三对角线阵与五对角线阵) 中特征值何时保持二次多项式的充要条件, 并应用于构造新的二元PDE 正交多项式.     

Polynomial functions on upper triangular matrix algebras

There are two kinds of polynomial functions on matrix algebras over commutative rings: those induced by polynomials with coefficients in the algebra itself and those induced by polynomials with scalar coefficients. In the case of algebras of upper triangular matrices over a commutative ring, we characterize the former in terms of the latter (which are easier to handle because of substitution homomorphism). We conclude that the set of integer-valued polynomials with matrix coefficients on an algebra of upper triangular matrices is a ring, and that the set of null-polynomials with matrix coefficients on an algebra of upper triangular matrices is an ideal.     

Inherited LU-factorizations of matrices

Various types of LU-factorizations for nonsingular matrices, where L is a lower triangular matrix and U is an upper triangular matrix, are defined and characterized. These types of LU-factorizations are extended to the general m × n case. The more general conditions are considered in the light of the structures of [C.R. Johnson, D.D. Olesky, P. Van den Driessche, Inherited matrix entries: LU factorizations, SIAM J. Matrix Anal. Appl. 10 (1989) 99-104]. Applications to graphs and adjacency matrices are investigated. Conditions for the product of a lower and an upper triangular matrix to be the zero matrix are also obtained.     

Perturbation and error analyses for block downdating of a Cholesky decomposition

A new perturbation result is presented for the problem of block downdating a Cholesky decompositionX ^T X = R ^T R. Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations. An error analysis is also given for block downdating using Corrected Seminormal Equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations. We classify the problems for which the CSNE downdating method produces a downdated upper triangular matrix which is comparable in accuracy to the upper triangular factor obtained from the QR decomposition by Householder transformations on the data matrix with the row block deleted.Dedicated to Ji-guang Sun in honour of his 60th birthdayThe work of the second author was supported in part by the National Science Foundation grant CCR-9209726.