Página 1 dos resultados de 45 itens digitais encontrados em 0.004 segundos

THE CLASS OF INVERSE M-MATRICES ASSOCIATED TO RANDOM WALKS

Martínez Aguilera, Servet; San Martín, Jaime Ricardo; Dellacherie Lefebvre, Claude Yvon Rog
Fonte: Society for Industrial and Applied Mathematics Publicador: Society for Industrial and Applied Mathematics
Tipo: Artículo de revista
EN
Relevância na Pesquisa
36.13%
Artículo de publicación ISI; Given W = M−1, with M a tridiagonal M-matrix, we show that there are two diagonal matrices D,E and two nonsingular ultrametric matrices U, V such that DWE is the Hadamard product of U and V . If M is symmetric and row diagonally dominant, we can take D = E = I. We relate this problem with potentials associated to random walks and study more closely the class of random walks that lose mass at one or two extremes.

A NEW CLASS OF INVERSE M-MATRICES OF TREE-LIKE TYPE

San Martín Aristegui, Jaime Ricardo; Zhang, Xiao-Dong; Martínez Aguilera, Servet
Fonte: SIAM PUBLICATIONS, 3600 UNIV CITY SCIENCE CENTER, PHILADELPHIA Publicador: SIAM PUBLICATIONS, 3600 UNIV CITY SCIENCE CENTER, PHILADELPHIA
EN
Relevância na Pesquisa
36.13%
Artículo de publicación ISI; In this paper, we use weighted dyadic trees to introduce a new class of nonnegative matrices whose inverses are column diagonally dominant M-matrices.

Relative perturbation theory for diagonally dominant matrices

Dailey, Megan; Martínez Dopico, Froilán C.; Ye, Qiang
Fonte: Society for Industrial and Applied Mathematics Publicador: Society for Industrial and Applied Mathematics
Tipo: info:eu-repo/semantics/publishedVersion; info:eu-repo/semantics/article
Publicado em /10/2014 ENG
Relevância na Pesquisa
96.81%
In this paper, strong relative perturbation bounds are developed for a number of linear algebra problems involving diagonally dominant matrices. The key point is to parameterize diagonally dominant matrices using their off-diagonal entries and diagonally dominant parts and to consider small relative componentwise perturbations of these parameters. This allows us to obtain new relative perturbation bounds for the inverse, the solution to linear systems, the symmetric indefinite eigenvalue problem, the singular value problem, and the nonsymmetric eigenvalue problem. These bounds are much stronger than traditional perturbation results, since they are independent of either the standard condition number or the magnitude of eigenvalues/singular values. Together with previously derived perturbation bounds for the LDU factorization and the symmetric positive definite eigenvalue problem, this paper presents a complete and detailed account of relative structured perturbation theory for diagonally dominant matrices.; This research was partially supported by the Ministerio de Economía y Competitividad of Spain under grant MTM2012-32542.

A new perturbation bound for the LDU factorization of diagonally dominant matrices

Dailey, Megan; Martínez Dopico, Froilán C.; Ye, Qiang
Fonte: Society for Industrial and Applied Mathematics Publicador: Society for Industrial and Applied Mathematics
Tipo: info:eu-repo/semantics/publishedVersion; info:eu-repo/semantics/article
Publicado em /07/2014 ENG
Relevância na Pesquisa
96.81%
This work introduces a new perturbation bound for the L factor of the LDU factorization of (row) diagonally dominant matrices computed via the column diagonal dominance pivoting strategy. This strategy yields L and U factors which are always well-conditioned and, so, the LDU factorization is guaranteed to be a rank-revealing decomposition. The new bound together with those for the D and U factors in [F. M. Dopico and P. Koev, Numer. Math., 119 (2011), pp. 337– 371] establish that if diagonally dominant matrices are parameterized via their diagonally dominant parts and off-diagonal entries, then tiny relative componentwise perturbations of these parameters produce tiny relative normwise variations of L and U and tiny relative entrywise variations of D when column diagonal dominance pivoting is used. These results will allow us to prove in a follow-up work that such perturbations also lead to strong perturbation bounds for many other problems involving diagonally dominant matrices.; Research supported in part by Ministerio de Economía y Competitividad of Spain under grant MTM2012-32542.

The singularity probability of random diagonally-dominant Hermitian matrices

Kassel, Adrien
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/03/2014
Relevância na Pesquisa
46.39%
In this note we describe the singular locus of diagonally-dominant Hermitian matrices with nonnegative diagonal entries over the reals, the complex numbers, and the quaternions. This yields explicit expressions for the probability that such matrices, chosen at random, are singular. For instance, in the case of the identity $n \times n$ matrix perturbed by a symmetric, zero-diagonal, $\{\pm 1/(n-1)\}$-Bernoulli matrix, this probability turns out to be equal to $2^{-(n-1)(n-2)/2}$. As a corollary, we find that the probability for a $n\times n$ symmetric $\{\pm 1\}$-Bernoulli matrix to have eigenvalue $n$ is $2^{-(n^2-n+2)/2}$.

Conditions for separability in generalized Laplacian matrices and nonnegative matrices as density matrices

Wu, Chai Wah
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/08/2005
Relevância na Pesquisa
36.22%
Recently, Laplacian matrices of graphs are studied as density matrices in quantum mechanics. We continue this study and give conditions for separability of generalized Laplacian matrices of weighted graphs with unit trace. In particular, we show that the Peres-Horodecki positive partial transpose separability condition is necessary and sufficient for separability in ${\mathbb C}^2\otimes {\mathbb C}^q$. In addition, we present a sufficient condition for separability of generalized Laplacian matrices and diagonally dominant nonnegative matrices.; Comment: 10 pages, 1 figure

Accurate Computations of Eigenvalues of Extremely Ill-conditioned Matrices and Differential Operators

Ye, Qiang
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/12/2015
Relevância na Pesquisa
46.57%
This paper is concerned with computations of a few smaller eigenvalues (in absolute value) of a large extremely ill-conditioned matrix. It is shown that smaller eigenvalues can be accurately computed for a diagonally dominant matrix or a product of diagonally dominant matrices by combining a standard iterative method with the accurate inversion algorithms that have been developed for such matrices. Applications to the finite difference discretization of differential operators are discussed. In particular, a new discretization is derived for the 1-dimensional biharmonic operator that can be written as a product of diagonally dominant matrices. Numerical examples are presented to demonstrate the accuracy achieved by the new algorithms.

Characterization of diagonally dominant H-matrices

Moraca, Nenad
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/10/2015
Relevância na Pesquisa
46.57%
We first show that sufficient conditions for a diagonally dominant matrix to be a nonsingular one (and also an H-matrix), obtained independently by Shivakumar and Chew in 1974, and Farid in 1995, are equivalent. Then we simplify the characterization of diagonally dominant H-matrices obtained by Huang in 1995, and using it prove that the Shivakumar-Chew-Farid sufficient condition for a diagonally dominant matrix to be an H-matrix, is also necessary.; Comment: 7 pages, 0 figures This manuscript is part of my Diploma Thesis defended in 2006

Convergence on Gauss-Seidel iterative methods for linear systems with general H-matrices

Zhang, Cheng-yi; Ye, Dan; Zhong, Cong-lei; Luo, Shuanghua
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/10/2014
Relevância na Pesquisa
46.72%
It is well known that as a famous type of iterative methods in numerical linear algebra, Gauss-Seidel iterative methods are convergent for linear systems with strictly or irreducibly diagonally dominant matrices, invertible $H-$matrices (generalized strictly diagonally dominant matrices) and Hermitian positive definite matrices. But, the same is not necessarily true for linear systems with nonstrictly diagonally dominant matrices and general $H-$matrices. This paper firstly proposes some necessary and sufficient conditions for convergence on Gauss-Seidel iterative methods to establish several new theoretical results on linear systems with nonstrictly diagonally dominant matrices and general $H-$matrices. Then, the convergence results on preconditioned Gauss-Seidel (PGS) iterative methods for general $H-$matrices are presented. Finally, some numerical examples are given to demonstrate the results obtained in this paper.

Retaining positive definiteness in thresholded matrices

Guillot, Dominique; Rajaratnam, Bala
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/08/2011
Relevância na Pesquisa
46.22%
Positive definite (p.d.) matrices arise naturally in many areas within mathematics and also feature extensively in scientific applications. In modern high-dimensional applications, a common approach to finding sparse positive definite matrices is to threshold their small off-diagonal elements. This thresholding, sometimes referred to as hard-thresholding, sets small elements to zero. Thresholding has the attractive property that the resulting matrices are sparse, and are thus easier to interpret and work with. In many applications, it is often required, and thus implicitly assumed, that thresholded matrices retain positive definiteness. In this paper we formally investigate the algebraic properties of p.d. matrices which are thresholded. We demonstrate that for positive definiteness to be preserved, the pattern of elements to be set to zero has to necessarily correspond to a graph which is a union of disconnected complete components. This result rigorously demonstrates that, except in special cases, positive definiteness can be easily lost. We then proceed to demonstrate that the class of diagonally dominant matrices is not maximal in terms of retaining positive definiteness when thresholded. Consequently, we derive characterizations of matrices which retain positive definiteness when thresholded with respect to important classes of graphs. In particular...

Weakly chained matrices and impulse control

Azimzadeh, Parsiad; Forsyth, Peter A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/10/2015
Relevância na Pesquisa
46.39%
This work is motivated by numerical solutions to Hamilton-Jacobi-Bellman quasi-variational inequalities (HJBQVIs) associated with combined stochastic and impulse control problems. In particular, we consider (i) direct control, (ii) penalized, and (iii) explicit control schemes applied to the HJBQVI problem. Scheme (i) takes the form of a Bellman problem involving an operator which is not necessarily contractive. We consider the well-posedness of the Bellman problem and give sufficient conditions for convergence of the corresponding policy iteration. To do so, we use weakly chained diagonally dominant matrices, which give a graph-theoretic characterization of weakly diagonally dominant M-matrices. We compare schemes (i)--(iii) under the following examples: (a) optimal control of the exchange rate, (b) optimal consumption with fixed and proportional transaction costs, and (c) pricing guaranteed minimum withdrawal benefits in variable annuities. Perhaps controversially, we find that one should abstain from using scheme (i).; Comment: 22 pages, 4 figures

A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations

Tutunov, Rasul; Ammar, Haitham Bou; Jadbabaie, Ali
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/02/2015
Relevância na Pesquisa
46.24%
In this paper, we propose a fast distributed solver for linear equations given by symmetric diagonally dominant M-Matrices. Our approach is based on a distributed implementation of the parallel solver of Spielman and Peng by considering a specific approximated inverse chain which can be computed efficiently in a distributed fashion. Representing the system of equations by a graph $\mathbb{G}$, the proposed distributed algorithm is capable of attaining $\epsilon$-close solutions (for arbitrary $\epsilon$) in time proportional to $n^{3}$ (number of nodes in $\mathbb{G}$), ${\alpha}$ (upper bound on the size of the R-Hop neighborhood), and $\frac{{W}_{max}}{{W}_{min}}$ (maximum and minimum weight of edges in $\mathbb{G}$).

Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time

Hunter, Timothy; Alaoui, Ahmed El; Bayen, Alexandre
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/08/2014
Relevância na Pesquisa
66.39%
We present new algorithms for computing the log-determinant of symmetric, diagonally dominant matrices. Existing algorithms run with cubic complexity with respect to the size of the matrix in the worst case. Our algorithm computes an approximation of the log-determinant in time near-linear with respect to the number of non-zero entries and with high probability. This algorithm builds upon the utra-sparsifiers introduced by Spielman and Teng for Laplacian matrices and ultimately uses their refined versions introduced by Koutis, Miller and Peng in the context of solving linear systems. We also present simpler algorithms that compute upper and lower bounds and that may be of more immediate practical interest.; Comment: Submitted to the SIAM Journal on Computing (SICOMP)

On the positive stability of $P^2$-matrices

Kushel, Olga Y.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.16%
In this paper, we study the positive stability of $P$-matrices. We prove that a $P$-matrix A is positively stable if A is a $Q^2$-matrix and there is at least one nested sequence of principal submatrices of A each of which is also a $Q^2$-matrix. This result generalizes the result by Carlson which shows the positive stability of sign-symmetric $P$-matrices and the result by Tang, Simsek, Ozdaglar and Acemoglu which shows the positive stability of strictly row (column) square diagonally dominant for every order of minors $P$-matrices.

Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners

Boman, Erik; Hendrickson, Bruce; Vavasis, Stephen
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.24%
We consider linear systems arising from the use of the finite element method for solving scalar linear elliptic problems. Our main result is that these linear systems, which are symmetric and positive semidefinite, are well approximated by symmetric diagonally dominant matrices. Our framework for defining matrix approximation is support theory. Significant graph theoretic work has already been developed in the support framework for preconditioners in the diagonally dominant case, and in particular it is known that such systems can be solved with iterative methods in nearly linear time. Thus, our approximation result implies that these graph theoretic techniques can also solve a class of finite element problems in nearly linear time. We show that the support number bounds, which control the number of iterations in the preconditioned iterative solver, depend on mesh quality measures but not on the problem size or shape of the domain.; Comment: Added ref to Chen & Toledo in Section 9 Added description of how to form RHS; added ref to Wang and Sarin

Bounds on determinants of perturbed diagonal matrices

Brent, Richard P.; Osborn, Judy-anne H.; Smith, Warren D.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.13%
We give upper and lower bounds on the determinant of a perturbation of the identity matrix or, more generally, a perturbation of a nonsingular diagonal matrix. The matrices considered are, in general, diagonally dominant. The lower bounds are best possible, and in several cases they are stronger than well-known bounds due to Ostrowski and other authors. If $A = I-E$ is an $n \times n$ matrix and the elements of $E$ are bounded in absolute value by $\varepsilon \le 1/n$, then a lower bound of Ostrowski (1938) is $\det(A) \ge 1-n\varepsilon$. We show that if, in addition, the diagonal elements of $E$ are zero, then a best-possible lower bound is \[\det(A) \ge (1-(n-1)\varepsilon)\,(1+\varepsilon)^{n-1}.\] Corresponding upper bounds are respectively \[\det(A) \le (1 + 2\varepsilon + n\varepsilon^2)^{n/2}\] and \[\det(A) \le (1 + (n-1)\varepsilon^2)^{n/2}.\] The first upper bound is stronger than Ostrowski's bound (for $\varepsilon < 1/n$) $\det(A) \le (1 - n\varepsilon)^{-1}$. The second upper bound generalises Hadamard's inequality, which is the case $\varepsilon = 1$. A necessary and sufficient condition for our upper bounds to be best possible for matrices of order $n$ and all positive $\varepsilon$ is the existence of a skew-Hadamard matrix of order $n$.; Comment: 18 pages...

Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization

Avron, Haim; Druinsky, Alex; Gupta, Anshul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.13%
Asynchronous methods for solving systems of linear equations have been researched since Chazan and Miranker's pioneering 1969 paper on chaotic relaxation. The underlying idea of asynchronous methods is to avoid processor idle time by allowing the processors to continue to make progress even if not all progress made by other processors has been communicated to them. Historically, the applicability of asynchronous methods for solving linear equations was limited to certain restricted classes of matrices, such as diagonally dominant matrices. Furthermore, analysis of these methods focused on proving convergence in the limit. Comparison of the asynchronous convergence rate with its synchronous counterpart and its scaling with the number of processors were seldom studied, and are still not well understood. In this paper, we propose a randomized shared-memory asynchronous method for general symmetric positive definite matrices. We rigorously analyze the convergence rate and prove that it is linear, and is close to that of the method's synchronous counterpart if the processor count is not excessive relative to the size and sparsity of the matrix. We also present an algorithm for unsymmetric systems and overdetermined least-squares. Our work presents a significant improvement in the applicability of asynchronous linear solvers as well as in their convergence analysis...

On Sketching Quadratic Forms

Andoni, Alexandr; Chen, Jiecao; Krauthgamer, Robert; Qin, Bo; Woodruff, David P.; Zhang, Qin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/11/2015
Relevância na Pesquisa
36.13%
We undertake a systematic study of sketching a quadratic form: given an $n \times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can produce (without further access to $A$) a multiplicative $(1+\epsilon)$-approximation to $x^T A x$ for any desired query $x \in \mathbb{R}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $\Theta(\epsilon^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query $x$, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all $x$'s simultaneously, again there are no non-trivial sketches.) We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting $O(\epsilon^{-2} n)$ edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. $\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" $x\in \{0...

Inverses of symmetric, diagonally dominant positive matrices and applications

Hillar, Christopher J.; Lin, Shaowei; Wibisono, Andre
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.62%
We prove tight bounds for the $\infty$-norm of the inverse of symmetric, diagonally dominant positive matrices. We also prove a new lower-bound form of Hadamard's inequality for the determinant of diagonally dominant positive matrices and an improved upper bound for diagonally balanced positive matrices. Applications of our results include numerical stability for linear systems, bounds on inverses of differentiable functions, and consistency of the maximum likelihood equations for maximum entropy graph distributions.; Comment: 18 pages

On the Stability of P-Matrices

Tang, A.; Simsek, Alp; Ozdaglar, Asuman; Acemoglu, Daron
Fonte: California Institute of Technology Publicador: California Institute of Technology
Tipo: Report or Paper; PeerReviewed Formato: application/pdf
Publicado em 09/11/2006
Relevância na Pesquisa
36.43%
We establish two sufficient conditions for the stability of a $P$-matrix. First, we show that a $P$-matrix is positive stable if its skew-symmetric component is sufficiently smaller (in matrix norm) than its symmetric component. This result generalizes the fact that symmetric $P$-matrices are positive stable, and is analogous to a result by Carlson which shows that sign symmetric $P$-matrices are positive stable. Second, we show that a $P$-matrix is positive stable if it is strictly row (column) square diagonally dominant for every order of minors. This result generalizes the fact that strictly row diagonally dominant$P$-matrices are stable. We compare our sufficient conditions with the sign symmetric condition and demonstrate that these conditions do not imply each other.