The Factorization of Sparse Symmetric Indefinite Matrices

The Harwell multifrontal code MA27 is able to solve symmetricindefinite systems of linear equations such as those that arisefrom least-squares and constrained optimization algorithms,but may sometimes lead to many more arithmetic operations beingneeded to factorize the matrix than is required by other strategies.In this paper, we report on the results of our investigationof this problem. We have concentrated on seeking new strategiesthat preserve the multifrontal principle but follow the sparsitystructure more closely in the case when some of the diagonalentries are zero.     

The Eigenvalues of Very Sparse Random Symmetric Matrices

Let W _n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here is independent of n. We show that the limit of the expected spectral distribution functions of W _n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.     

广义对称矩阵反问题有解的条件

本利用矩阵的奇异值分解讨论了一类广义对矩阵阵反问题，得到了此类矩阵反问题有解的充分必要条件及通解的表达式。     

Use of the Lanczos Method for Finding Complete Sets of Eigenvalues of Large Sparse Symmetric Matrices

A way of using the Lanczos method to find all the eigenvaluesof a large sparse symmetric matrix is described, and some empiricalobservations on the manner in which the method works in practiceare given. The method seems to be accurate, fast, and not verydemanding on storage. A formula for the number of iterationsnecessary to get the eigenvalues is proposed.     

Decomposition of Matrices into Involutory Matrices and Symmetric Matrices

Let \Omega be a field, and let F denote the Frobenius matrix: $[F = \left( {\begin{array}{*{20}{c}} 0&{ - {\alpha _n}}\{{E_{n - 1}}}&\alpha \end{array}} \right)\]$ where \alpha is an n-1 dimentional vector over Q, and E_n- 1 is identity matrix over \Omega. Theorem 1. There hold two elementary decompositions of Frobenius matrix: (i) F=SJB, where S, J are two symmetric matrices, and B is an involutory matrix; (ii) F=CQD, where O is an involutory matrix, Q is an orthogonal matrix over \Omega, and D is a diagonal matrix. We use the decomposition (i) to deduce the following two theorems: Theorem 2. Every square matrix over \Omega is a product of twe symmetric matrices and one involutory matrix. Theorem 3. Every square matrix over \Omega is a product of not more than four symmetric matrices. By using the decomposition (ii), we easily verify the following Theorem 4(Wonenburger-Djokovic') . The necessary and sufficient condition that a square matrix A may be decomposed as a product of two involutory matrices is that A is nonsingular and similar to its inverse A^-1 over Q (See [2, 3]). We also use the decomosition (ii) to obtain Theorem 5. Every unimodular matrix is similar to the matrix CQB, where C, B are two involutory matrices, and Q is an orthogonal matrix over Q. As a consequence of Theorem 5. we deduce immediately the following Theorem 6 (Gustafson-Halmos-Radjavi). Every unimodular matrix may be decomposed as a product of not more than four involutory matrices (See [1] ). Finally, we use the decomposition (ii) to derive the following Thoerem 7. If the unimodular matrix A possesses one invariant factor which is not constant polynomial, or the determinant of the unimodular matrix A is I and A possesses two invariant factors with the same degree (>0), then A may be decomposed as a product of three involutory matrices. All of the proofs of the above theorems are constructive.     

一类对称正交对称矩阵反问题的最小二乘解

1 引言 本文记号R~(n×m),OR~(n×n),A~+,I_k,SR~(n×n),rank(A),||·||,A*B,BSR~(n×n)和ASR~(n×n)参见[1].若无特殊声明文中的P为一给定的矩阵且满足P∈OR~(n×n)和P=P~T. 定义1 设A=(α_(ij))∈R~(n×n).若A满足A=A~T,(PA)~T=PA则称A为n阶对称正交对称矩阵;所有n阶对称正交对称矩阵的全体记为SR_P~n.若A∈R~(n×n)满足A~T=A,(PA)~T=-PA,则称A为n阶对称正交反对称矩阵;所有n阶对称正交反对     

Symmetric Weighing Matrices Constructed using Group Matrices

A weighing matrix of order n and weight m² is a square matrix M of order n with entries from {-1,0,+1} such that MM^T=m²I where I is the identity matrix of order n. If M is a group matrix constructed using a group of order n, M is called a group weighing matrix. Recently, group weighing matrices were studied intensively, especially when the groups are cyclic and abelian. In this paper, we study the abelian group weighing matrices that are symmetric, i.e.M^T=M. Some new examples are found. Also we obtain a few exponent bounds on abelian groups that admit symmetric group weighing matrices. In particular, we prove that there is no symmetric abelian group weighing matrices of order 2p^r and weight p² where p is a prime and p≥ 5.Communicated by: K.T. Arasu     

对称正交反对称矩阵反问题

设P为一给定的对称正交矩阵, 记SAR\+n\-P={A∈R\+\{n×n\}|A\+T=A,(PA)\+T=-PA}. 该文考虑下列问题问题Ⅰ〓给定X∈R\+\{n×m, Λ=diag(λ\-1,λ\-2,…, λ\-m)∈R\+\{m×m\}, 求A∈SAR\+n\-P使AX=XΛ,问题Ⅱ〓给定X,B∈R\+\{n×m, 求A∈SAR\+n\-P使  ‖AX-B‖=min.问题Ⅲ设[AKA～]∈R\+\{n×n\},求A\+*∈S\-E使 ‖[AKA～]-A\+*‖=inf[DD(X]A∈S\-E[DD)]‖[AKA～]-A‖, 其中S\-E为问题Ⅱ的解集合, ‖·‖表示Frobenius范数.该文得到了问题Ⅰ有解的充要条件及解集合的表达式, 给出了解集合S\-E的通式和逼近解A\+*的具体表达式.     

The Significant Order of Symmetric Tridiagonal Matrices

It is demonstrated that an eigenvalue of a symmetric tridiagonalmatrix as calculated by the Sturm sequence bisection procedure,is determined in general by a leading principal partition ofthe whole matrix. The order of this leading principal partitionis called the significant order of the matrix. The significantorder depends upon the specific eigenvalue being calculated,and upon the working precision of the computer. This numericalphenomenon may be employed to accelerate the bisection procedure.In applications it either indicates the adequacy or otherwiseof the working precision for finite matrices, or in the caseof theoretically infinite matrices, the effective truncationorder for the precision employed.     

双对称本原矩阵k-点指数的极矩阵

一个n阶本原矩阵A的k-点指数是A的最小幂指数,使得在这个幂中,存在着k个全1行．最近我们得到了n阶双对称本原矩阵的k-点指数的上确界．本文将在此基础上,以伴随图的形式给出其极矩阵的完全刻划．     

Algebraic Graph Theory for Sparse Flexibility Matrices

An efficient algorithm is presented for the formation of suboptimal cycle bases of graphs corresponding to sparse cycle adjacency matrices, leading to the formation of highly sparse flexibility matrices. The algorithm presented employs concepts from algebraic graph theory together with a Greedy-type algorithm to select cycles with small overlaps and uses a simple graph-theoretical method for controlling the independence of the selected cycles.     

Picard Iterations for Diffusions on Symmetric Matrices

Matrix-valued stochastic processes have been of significant importance in areas such as physics, engineering and mathematical finance. One of the first models studied has been the so-called Wishart process, which is described as the solution of a stochastic differential equation in the space of matrices. In this paper, we analyze natural extensions of this model and prove the existence and uniqueness of the solution. We do this by carrying out a Picard iteration technique in the space of symmetric matrices. This approach takes into account the operator character of the matrices, which helps to corroborate how the Lipchitz conditions also arise naturally in this context.     

双对称本原矩阵κ-点指数的极矩阵

一个n阶本原矩阵A的κ-点指数是A的最小幂指数,使得在这个幂中,存在着κ个全1行.最近我们得到了n阶双对称本原矩阵的κ-点指数的上确界.本文将在此基础上,以伴随图的形式给出其极矩阵的完全刻划.     

On Sparse Parity Check Matrices

We consider the extremal problem to determine the maximal number of columns of a 0-1 matrix with rows and at most ones in each column such that each columns are linearly independent modulo . For fixed integers and , we shall prove the probabilistic lower bound = ; for a power of , we prove the upper bound which matches the lower bound for infinitely many values of . We give some explicit constructions.     

对称中心本原矩阵的指数集

This paper first establishes a distance inequality of the associated diagraph of a central symmetric primitive matrix, then characters the exponent set of central symmetric primitive matrices, and proves that the exponent set of central symmetric primitive matrices of order n is {1, 2,… ,n-1}. There is no gap in it.     

Overlapping Domain Decomposition Algorithms for General Sparse Matrices

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver.     

一类对称正交反对称矩阵反问题的最佳逼近

讨论了一类对称正交反对称反问题的最佳逼近.利用对称正交反对称矩阵的特殊性质,给出了矩阵方程AX=B有对称正交反对称解的充要条件以及解的一般表达式;证明最佳逼近解的存在惟一性并给出其表达式;最后给出计算任意矩阵的最佳逼近解的数值方法及算例.     

The Limiting Spectral Measure for Ensembles of Symmetric Block Circulant Matrices

Given an ensemble of N×N random matrices, a natural question to ask is whether or not the empirical spectral measures of typical matrices converge to a limiting spectral measure as N→∞. While this has been proved for many thin patterned ensembles sitting inside all real symmetric matrices, frequently there is no nice closed form expression for the limiting measure. Further, current theorems provide few pictures of transitions between ensembles. We consider the ensemble of symmetric m-block circulant matrices with entries i.i.d.r.v. These matrices have toroidal diagonals periodic of period m. We view m as a “dial” we can “turn” from the thin ensemble of symmetric circulant matrices, whose limiting eigenvalue density is a Gaussian, to all real symmetric matrices, whose limiting eigenvalue density is a semi-circle. The limiting eigenvalue densities f _m show a visually stunning convergence to the semi-circle as m→∞, which we prove. In contrast to most studies of patterned matrix ensembles, our paper gives explicit closed form expressions for the densities. We prove that f _m is the product of a Gaussian and a certain even polynomial of degree 2m?2; the formula is the same as that for the m×m Gaussian Unitary Ensemble (GUE). The proof is by derivation of the moments from the eigenvalue trace formula. The new feature, which allows us to obtain closed form expressions, is converting the central combinatorial problem in the moment calculation into an equivalent counting problem in algebraic topology. We end with a generalization of the m-block circulant pattern, dropping the assumption that the m random variables be distinct. We prove that the limiting spectral distribution exists and is determined by the pattern of the independent elements within an m-period, depending not only on the frequency at which each element appears, but also on the way the elements are arranged.     

Incremental Norm Estimation for Dense and Sparse Matrices

We present an incremental approach to 2-norm estimation for triangular matrices. Our investigation covers both dense and sparse matrices which can arise for example from a QR, a Cholesky or a LU factorization. If the explicit inverse of a triangular factor is available, as in the case of an implicit version of the LU factorization, we can relate our results to incremental condition estimation (ICE). Incremental norm estimation (INE) extends directly from the dense to the sparse case without needing the modifications that are necessary for the sparse version of ICE. INE can be applied to complement ICE, since the product of the two estimates gives an estimate for the matrix condition number. Furthermore, when applied to matrix inverses, INE can be used as the basis of a rank-revealing factorization.