共查询到20条相似文献,搜索用时 31 毫秒
1.
Richard A. Brualdi 《Linear algebra and its applications》2010,433(7):1452-2271
An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries. 相似文献
2.
Robert Grone Charles R. Johnson Eduardo M. Sá Henry Wolkowicz 《Linear algebra and its applications》1984
The question of which partial Hermitian matrices (some entries specified, some free) may be completed to positive definite matrices is addressed. It is shown that if the diagonal entries are specified and principal minors, composed of specified entries, are positive, then, if the undirected graph of the specified entries is chordal, a positive definite completion necessarily exists. Furthermore, if this graph is not chordal, then examples exist without positive definite completions. In case a positive definite completion exists, there is a unique matrix, in the class of all positive definite completions, whose determinant is maximal, and this matrix is the unique one whose inverse has zeros in those positions corresponding to unspecified entries in the original partial Hermitian matrix. Additional observations regarding positive definite completions are made. 相似文献
3.
Zixing
Xin Jianlin Xia Stephen Cauley Venkataramanan Balakrishnan 《Numerical Linear Algebra with Applications》2020,27(3)
In this work, we provide new analysis for a preconditioning technique called structured incomplete factorization (SIF) for symmetric positive definite matrices. In this technique, a scaling and compression strategy is applied to construct SIF preconditioners, where off‐diagonal blocks of the original matrix are first scaled and then approximated by low‐rank forms. Some spectral behaviors after applying the preconditioner are shown. The effectiveness is confirmed with the aid of a type of two‐dimensional and three‐dimensional discretized model problems. We further show that previous studies on the robustness are too conservative. In fact, the practical multilevel version of the preconditioner has a robustness enhancement effect, and is unconditionally robust (or breakdown free) for the model problems regardless of the compression accuracy for the scaled off‐diagonal blocks. The studies give new insights into the SIF preconditioning technique and confirm that it is an effective and reliable way for designing structured preconditioners. The studies also provide useful tools for analyzing other structured preconditioners. Various spectral analysis results can be used to characterize other structured algorithms and study more general problems. 相似文献
4.
This note deals with the computational problem of determining the projection of a given symmetric matrix onto the subspace of symmetric matrices that have a fixed sparsity pattern. This projection is performed with respect to a weighted Frobenius norm involving a metric that is not diagonal. It is shown that the solution to this question is computationally feasible when the metric appearing in the norm is a low rank modification to the identity. Also, generalization to perturbations of higher rank is shown to be increasingly costly in terms of computation. 相似文献
5.
James McTigue 《Linear algebra and its applications》2011,435(9):2259-2271
A partial matrix over a field F is a matrix whose entries are either elements of F or independent indeterminates. A completion of such a partial matrix is obtained by specifying values from F for the indeterminates. We determine the maximum possible number of indeterminates in a partial m×n matrix whose completions all have rank at least equal to a particular k, and we fully describe those examples in which this maximum is attained. Our main theoretical tool, which is developed in Section 2, is a duality relationship between affine spaces of matrices in which ranks are bounded below and affine spaces of matrices in which the (left or right) nullspaces of elements possess a certain covering property. 相似文献
6.
KennethJohnHARRISON 《数学学报(英文版)》2003,19(3):577-590
In a matrix-completion problem the aim is to specifiy the missing entries of a matrix in order to produce a matrix with particular properties. In this paper we survey results concerning matrix-completion problems where we look for completions of various types for partial matrices supported on a given pattern. We see that the existence of completions of the required type often depends on the chordal properties of graphs associated with the pattern. 相似文献
7.
We present an algebraic structured preconditioner for the iterative solution of large sparse linear systems. The preconditioner is based on a multifrontal variant of sparse LU factorization used with nested dissection ordering. Multifrontal factorization amounts to a partial factorization of a sequence of logically dense frontal matrices, and the preconditioner is obtained if structured factorization is used instead. This latter exploits the presence of low numerical rank in some off‐diagonal blocks of the frontal matrices. An algebraic procedure is presented that allows to identify the hierarchy of the off‐diagonal blocks with low numerical rank based on the sparsity of the system matrix. This procedure is motivated by a model problem analysis, yet numerical experiments show that it is successful beyond the model problem scope. Further aspects relevant for the algebraic structured preconditioner are discussed and illustrated with numerical experiments. The preconditioner is also compared with other solvers, including the corresponding direct solver. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
8.
Ho S. Hong 《Linear and Multilinear Algebra》1991,29(3):181-194
Based on two set partitions of the symmetric group Sn expansion theorems by diagonal elements for the permanent and the determinant are derived, for both the generic commuting and noncommuting cases. They are of the same type as the well-known Laplace expansions where either fixed rows or columns of a given matrix are chosen instead of diagonal elements. 相似文献
9.
Zejun Huang 《Linear algebra and its applications》2011,434(8):1956-2271
We characterize the ACI-matrices all of whose completions have the same rank, determine the largest number of indeterminates in such partial matrices of a given size, and determine the partial matrices that attain this largest number. 相似文献
10.
This paper presents some precise structural results concerning combinatorially symmetric, sign symmetric, and sign antisymmetric invertible matrices whose associated diagraphs are trees. In particular given an invertible sign antisymmetric matrix A whose associated digraph is a tree and the fact that A-1 is sign antisymmetric, we are able to completely determine the associated digraph of A-1. 相似文献
11.
We propose an algorithm that transforms a real symplectic matrix with a stable structure to a block diagonal form composed of three main blocks. The two extreme blocks of the same size are associated respectively with the eigenvalues outside and inside the unit circle. Moreover, these eigenvalues are symmetric with respect to the unit circle. The central block is in turn composed of several diagonal blocks whose eigenvalues are on the unit circle and satisfy a modification of the Krein-Gelfand-Lidskii criterion. The proposed algorithm also gives a qualitative criterion for structural stability. 相似文献
12.
L. Yu. Kolotilina 《Journal of Mathematical Sciences》1996,79(3):1043-1047
The paper presents upper bounds for the largest eigenvalue of a block Jacobi scaled symmetric positive-definite matrix which
depend only on such parameters as the block semibandwidth of a matrix and its block size. From these bounds we also derive
upper bounds for the smallest eigenvalue of a symmetric matrix with identity diagonal blocks. Bibliography: 4 titles.
Translated by L. Yu. Kolotilina.
Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 18–25. 相似文献
13.
Based on two set partitions of the symmetric group Sn expansion theorems by diagonal elements for the permanent and the determinant are derived, for both the generic commuting and noncommuting cases. They are of the same type as the well-known Laplace expansions where either fixed rows or columns of a given matrix are chosen instead of diagonal elements. 相似文献
14.
Necessary and sufficient conditions are given on the data for completability of a partial symmetric inverse M-matrix, the graph of whose specified entries is a cycle, and these conditions coincide with those we identify to be necessary in the general (nonsymmetric) case. Graphs for which all partial symmetric inverse M-matrices have symmetric inverse M-matrix completions are identified and these include those that arise in the general (positionally symmetric) case. However, the identification of all such graphs is more subtle than the general case. Finally, we show that our new cycle conditions are sufficient for completability of all partial symmetric inverse M-matrices, the graph of whose specified entries is a block graph. 相似文献
15.
A fast numerical verification method is proposed for evaluating the accuracy of numerical solutions for symmetric saddle point linear systems whose diagonal blocks of the coefficient matrix are semidefinite matrices. The method is based on results of an algebraic analysis of a block diagonal preconditioning. Some numerical experiments are present to illustrate the usefulness of the method. 相似文献
16.
Sumio Yamada 《Geometriae Dedicata》2010,145(1):43-63
On a Teichmüller space, the Weil-Petersson metric is known to be incomplete. Taking metric and geodesic completions result
in two distinct spaces, where the Hopf-Rinow theorem is no longer relevant due to the singular behavior of the Weil-Petersson
metric. We construct a geodesic completion of the Teichmüller space through the formalism of Coxeter complex with the Teichmüller
space as its non-linear non-homogeneous fundamental domain. We then show that the metric and geodesic completions both satisfy
a finite rank property, demonstrating a similarity with the non-compact symmetric spaces of semi-simple Lie groups. 相似文献
17.
A two-way chasing algorithm to reduce a diagonal plus a symmetric semi-separable matrix to a symmetric tridiagonal one and an algorithm to reduce a diagonal plus an unsymmetric semi-separable matrix to a bidiagonal one are considered. Both algorithms are fast and stable, requiring a computational cost of N
2, where N is the order of the considered matrix. 相似文献
18.
Abdo Y. Alfakih Amir Khandani Henry Wolkowicz 《Computational Optimization and Applications》1999,12(1-3):13-30
Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed. 相似文献
19.
Leslie Hogben 《Linear algebra and its applications》2010,432(8):1961-1974
A graph describes the zero-nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303-316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139-144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389-415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126-145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees. 相似文献
20.
Qiang >Ye 《Numerische Mathematik》1995,70(4):507-514
Summary.
A symmetric tridiagonal matrix with a multiple eigenvalue must
have a zero
subdiagonal element and must be a direct sum of two
complementary blocks, both of which have the eigenvalue.
Yet it is well known that a small spectral gap
does not necessarily imply that some
is small, as
is demonstrated by the Wilkinson matrix.
In this note, it is shown that a pair of
close eigenvalues can only arise from two
complementary blocks on the diagonal,
in spite of the fact that the
coupling the
two blocks may not be small.
In particular, some explanatory bounds are derived and a
connection to
the Lanczos algorithm is observed. The nonsymmetric problem
is also included.
Received
April 8, 1992 / Revised version received September 21,
1994 相似文献