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

## THE CLASS OF INVERSE M-MATRICES ASSOCIATED TO RANDOM WALKS

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.

Link permanente para citações:

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

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.

Link permanente para citações:

## Relative perturbation theory for diagonally dominant matrices

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%

#Accurate computations#Diagonally dominant matrices#Diagonally dominant parts#Eigenvalues#Inverses#Linear systems#Relative perturbation theory#Singular values#Eigenvalues and eigenfunctions#Inverse problems#Matrix algebra

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.

Link permanente para citações:

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

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%

#Accurate computations#column diagonal dominance pivoting#diagonally dominant matrices#LDU factorization#rank-revealing decomposition#relative perturbation theory#diagonally dominant parts#Matemáticas

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.

Link permanente para citações:

## The singularity probability of random diagonally-dominant Hermitian matrices

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}$.

Link permanente para citações:

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

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

Link permanente para citações:

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

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.

Link permanente para citações:

## Characterization of diagonally dominant H-matrices

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

Link permanente para citações:

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

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.

Link permanente para citações:

## Retaining positive definiteness in thresholded matrices

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...

Link permanente para citações:

## Weakly chained matrices and impulse control

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

Link permanente para citações:

## A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations

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}$).

Link permanente para citações:

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

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)

Link permanente para citações:

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

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.

Link permanente para citações:

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

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

Link permanente para citações:

## Bounds on determinants of perturbed diagonal matrices

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.13%

#Mathematics - Numerical Analysis#Mathematics - Combinatorics#65F40 (Primary) 05B20, 15A15, 15A42, 15B34 (Secondary)

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...

Link permanente para citações:

## Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.13%

#Computer Science - Distributed, Parallel, and Cluster Computing#Computer Science - Data Structures and Algorithms#Computer Science - Numerical Analysis#Mathematics - Numerical Analysis

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...

Link permanente para citações:

## On Sketching Quadratic Forms

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...

Link permanente para citações:

## Inverses of symmetric, diagonally dominant positive matrices and applications

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

Link permanente para citações:

## On the Stability of P-Matrices

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.

Link permanente para citações: