Search

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

We present a randomized algorithm that on input a symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ nonzero entries and an $n$-vector $b$ produces an ${\tilde{x}} $ such that $\|{\tilde{x}} - A^{\dagger} {b} \|_{A} \leq \epsilon \|A^{\dagger} {b}\|_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon))$ for some constant $c$. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya in 1990. For any symmetric, weakly diagonally dominant matrix $A$ with nonpositive off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a preconditioner $B$ of $A$ with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero off-diagonal entries such that the finite generalized condition number $\kappa_{f} (A,B)$ is at most $k$, for some other constant $c$. I...

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 $DW\! E$ is the Hadamard product of $U$ and $V$. If $M$ is symmetric and row diagonally dominant, we can take $D=E=\mathbb{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.

This paper proves that the two-sided Jacobi method computes the eigenvalues of the indefinite symmetric matrix to high relative accuracy, provided that the initial matrix is scaled diagonally dominant. It proves sharp eigenvalue perturbation bounds coming from a single Jacobi step and from the whole sweep defined by the serial pivot strategies.

The truncated SPIKE algorithm is a parallel solver for linear systems which are banded and strictly diagonally dominant by rows. There are machines for which the current implementation of the algorithm is faster and scales better than the corresponding solver in ScaLAPACK (PDDBTRF/PDDBTRS). In this paper we prove that the SPIKE matrix is strictly diagonally dominant by rows with a degree no less than the original matrix. We establish tight upper bounds on the decay rate of the spikes as well as the truncation error. We analyze the error of the method and present the results of some numerical experiments which show that the accuracy of the truncated SPIKE algorithm is comparable to LAPACK and ScaLAPACK.

We present a new preconditioner for linear systems arising from finite-element discretizations of scalar elliptic partial differential equations (PDE's). The solver splits the collection $\{K_{e}\}$ of element matrices into a subset of matrices that are approximable by diagonally dominant matrices and a subset of matrices that are not approximable. The approximable $K_{e}$'s are approximated by diagonally dominant matrices $L_{e}$'s that are assembled to form a global diagonally dominant matrix $L$. A combinatorial graph algorithm then approximates $L$ by another diagonally dominant matrix $M$ that is easier to factor. Finally, $M$ is added to the inapproximable elements to form the preconditioner, which is then factored. When all the element matrices are approximable, which is often the case, the preconditioner is provably efficient. Approximating element matrices by diagonally dominant ones is not a new idea, but we present a new approximation method which is both efficient and provably good. The splitting idea is simple and natural in the context of combinatorial preconditioners, but hard to exploit in other preconditioning paradigms. Experimental results show that on problems in which some of the $K_{e}$'s are ill conditioned, our new preconditioner is more effective than an algebraic multigrid solver, than an incomplete-factorization preconditioner, and than a direct solver.

For a symmetric positive semidefinite diagonally dominant matrix, if its off-diagonal entries and its diagonally dominant parts for all rows (which are defined for a row as the diagonal entry subtracted by the sum of absolute values of off-diagonal entries in that row) are known to a certain relative accuracy, we show that its eigenvalues are known to the same relative accuracy. Specifically, we prove that if such a matrix is perturbed in a way that each off-diagonal entry and each diagonally dominant part have relative errors bounded by some $\epsilon$, then all its eigenvalues have relative errors bounded by $\epsilon$. The result is extended to the generalized eigenvalue problem.

We consider the Gersgorin disc separation from the origin for (doubly) diagonally dominant matrices and their Schur complements, showing that the separation of the Schur complement of a (doubly) diagonally dominant matrix is greater than that of the original grand matrix. As application we discuss the localization of eigenvalues and present some upper and lower bounds for the determinant of diagonally dominant matrices.

In this paper, we use weighted dyadic trees to introduce a new class of nonnegative matrices whose inverses are column diagonally dominant M-matrices.

Discrete maximum principles for linear equation systems are discussed. A novel maximum principle for linear difference schemes is established. Sufficient conditions for an arbitrary linear scheme to satisfy the maximum principle are provided. Easily verifiable sufficient as well as necessary and sufficient conditions of nonsingularity for a diagonally dominant matrix, be it reducible or irreducible, are derived. Necessary and sufficient conditions for the validity of the maximum principle for explicit difference schemes are developed. The notion of submonotonicity for linear difference schemes as well as the notions of linear monotonicity and linear submonotonicity for nonlinear difference schemes are introduced and associated criteria developed. The developed approaches are demonstrated by examples of known linear and nonlinear difference schemes associated, in general, with the numerical analysis of systems of partial differential equations.

An iterative method for identifying generalized diagonally dominant matrices\break (GDDMs, or H-matrices) was given in [B. Li et al., Linear Algebra Appl., 271 (1998), pp. 179--190], where the method is divergent when the matrix is not a GDDM. In this paper, we present an improved version. The new method is always convergent and needs fewer iterations than the earlier one. Some interesting features of the new method are presented. Spectral radii of nonnegative matrices with a constant diagonal entry also can be computed by our method.

It is known that the norm of the solution to a weighted linear least-squares problem is uniformly bounded for the set of diagonally dominant symmetric positive definite weight matrices. This result is extended to weight matrices that are nonnegative linear combinations of symmetric positive semidefinite matrices. Further, results are given concerning the strong connection between the boundedness of weighted projection onto a subspace and the projection onto its complementary subspace using the inverse weight matrix. In particular, explicit bounds are given for the Euclidean norm of the projections. These results are applied to the Newton equations arising in a primal-dual interior method for convex quadratic programming and boundedness is shown for the corresponding projection operator.

A dual reordering strategy based on both threshold and graph reorderings is introduced to construct robust incomplete LU (ILU) factorization of indefinite matrices. The ILU matrix is constructed as a preconditioner for the original matrix to be used in a preconditioned iterative scheme. The matrix is first divided into two parts according to a threshold parameter to control diagonal dominance. The first part with large diagonal dominance is reordered using a graph-based strategy, followed by an ILU factorization. A partial ILU factorization is applied to the second part to yield an approximate Schur complement matrix. The whole process is repeated on the Schur complement matrix and continues for a few times to yield a multilevel ILU factorization. Analyses are conducted to show how the Schur complement approach removes small diagonal elements of indefinite matrices and how the stability of the LU factor affects the quality of the preconditioner. Numerical results are used to compare the new preconditioning strategy with two popular ILU preconditioning techniques and a multilevel block ILU threshold preconditioner.

Special ultrametric matrices are, in a sense, extremal matrices in the boundary of the set of ultrametric matrices introduced by Martinez, Michon, and San Martin [ SIAM J. Matrix Anal. Appl., 15 (1994), pp. 98--106]. We show a simple construction of these matrices, if of order n, from nonnegatively edge-weighted trees on n vertices, or, equivalently, from nonnegatively edge-weighted paths. A general ultrametric matrix is then the sum of a nonnegative diagonal matrix and a special ultrametric matrix, with certain conditions fulfilled. The rank of a special ultrametric matrix is also recognized and it is shown that its Moore--Penrose inverse is a generalized diagonally dominant M-matrix. Some results on the nonsymmetric case are included.

It is well known that the inverse C = [ci,j] of an irreducible nonsingular symmetric tridiagonal matrix is given by two sequences of real numbers, {ui} and {vi}, such that ci,j = u i vj for $i \leq j$. A similar result holds for nonsymmetric matrices A. There the inverse can be described by four sequences {ui},{vi}, {xi},$ and {vi} with u ivi = xiyi. Here we characterize certain properties of A, i.e., being an M-matrix or positive definite, in terms of the ui, vi,xi, and yi. We also establish a relation of zero row sums and zero column sums of A and pairwise constant ui,vi, xi, and yi. Moreover, we consider decay rates for the entries of the inverse of tridiagonal and block tridiagonal (banded) matrices. For diagonally dominant matrices we show that the entries of the inverse strictly decay along a row or column. We give a sharp decay result for tridiagonal irreducible M-matrices and tridiagonal positive definite matrices. We also give a decay rate for arbitrary banded M-matrices.

We present one more algorithm to compute the condition number (for inversion) of an n X n tridiagonal matrix J in O(n) time. Previous O(n) algorithms for this task given by Higham [SIAM J. Sci. Statist. Comput., 7 (1986), pp. 150--165] are based on the tempting compact representation of the upper (lower) triangle of J-1 as the upper (lower) triangle of a rank-one matrix. However they suffer from severe overflow and underflow problems, especially on diagonally dominant matrices. Our new algorithm avoids these problems and is as efficient as the earlier algorithms.

Componentwise error analysis for a parallel partitioning algorithm for tridiagonal systems is presented. Bounds on the equivalent perturbations are obtained, depending on three constants. Then bounds on the forward error are presented as well, depending on two types of condition numbers. Estimates on the first constant come directly from the roundoff error analysis of the tridiagonal Gaussian elimination [N. Higham, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 521--530]. In the present paper, the second and third constants are bounded for some special classes of matrices, i.e., diagonally dominant (row or column), symmetric positive definite, M-matrices, and totally nonnegative. One of the features of the analysis is that the exact forward and backward errors are bounded, not just their first order approximations, with respect to the machine precision. In all the bounds, the linear terms are given separately to show that the terms of higher order are small enough.

The solution of the unconstrained weighted linear least-squares problem is known to be a convex combination of the basic solutions formed by the nonsingular subsystems if the weight matrix is diagonal and positive definite. In particular, this implies that the norm of this solution is uniformly bounded for any diagonal and positive definite weight matrix. In addition, the solution set is known to be the relative interior of a finite set of polytopes if the weight matrix varies over the set of positive definite diagonal matrices. In this paper, these results are reviewed and generalized to the set of weight matrices that are symmetric, positive semidefinite, and diagonally dominant and that give unique solution to the least-squares problem. This is done by means of a particular symmetric diagonal decomposition of the weight matrix, giving a finite number of diagonally weighted problems but in a space of higher dimension. Extensions to equality-constrained weighted linear least-squares problems are given. A discussion of why the boundedness properties do not hold for general symmetric positive definite weight matrices is given. The motivation for this research is from interior methods for optimization.

Let $A$ be a real weakly diagonally dominant $M$-matrix. We establish upper and lower bounds for the minimal eigenvalue of $A$, for its corresponding eigenvector, and for the entries of the inverse of $A$. Our results are applied to find meaningful two-sided bounds for both the $\ell_{1}$-norm and the weighted Perron-norm of the solution $x(t)$ to the linear differential system $\dot{x}=-Ax$, $x(0)=x_{0}>0$. These systems occur in a number of applications, including compartmental analysis and RC electrical circuits. A detailed analysis of a model for the transient behaviour of digital circuits is given to illustrate the theory.

Many interior methods for constrained optimization obtain a search direction as the solution of a symmetric linear system that becomes increasingly ill-conditioned as the solution is approached. In some cases, this ill-conditioning is characterized by a subset of the diagonal elements becoming large in magnitude. It has been shown that in this situation the solution can be computed accurately regardless of the size of the diagonal elements. In this paper we discuss the formulation of several interior methods that use symmetric diagonally ill-conditioned systems. It is shown that diagonal ill-conditioning may be characterized by the property of strict $t$-diagonal dominance, which generalizes the idea of diagonal dominance to matrices whose diagonals are substantially larger in magnitude than the off-diagonals. A perturbation analysis is presented that characterizes the sensitivity of $t$-diagonally dominant systems under a certain class of structured perturbations. Finally, we give a rounding-error analysis of the symmetric indefinite factorization when applied to $t$-diagonally dominant systems. This analysis resolves the (until now) open question of whether the class of perturbations used in the sensitivity analysis is representative of the rounding error made during the numerical solution of the barrier equations.

The partition method for the parallel solution of tridiagonal linear systems is discussed and the coefficients of the reduced global system derived. It is shown that if the full system is diagonally dominant then the reduced system retains this property. This has important implications for the stability of calculations in this reduced system and eliminates the need for global pivoting with its expensive communication overhead.

The solution of linear, tridiagonal systems having real, symmetric, diagonally dominant coefficient matrices with constant diagonals is considered. Details of cyclic reduction to solve such systems are discussed. It is proved that the sequence of the diagonal elements produced by the reduction phase of cyclic reduction converges quadratically. This fact is exploited to reduce the number of steps of the reduction phase (special cyclic reduction). An estimate of the rate of convergence of the diagonal elements will be proved, which can be used to determine the number of steps of the reduction phase. Several possibilities to compute the diagonal elements are discussed and compared.

It is well known that every $n \times n$ Stieltjes matrix has an inverse that is an $n \times n$ nonsingular symmetric matrix with nonnegative entries, and it is also easily seen that the converse of this statement fails in general to be true for $n > 2$. In the preceding paper by Martinez, Michon, and San Martin [SIAM J. Matrix Anal. Appl., 15 (1994), pp. 98--106], such a converse result is in fact shown to be true for the new class of strictly ultrametric matrices. A simpler proof of this basic result is given here, using more familiar tools from linear algebra.

The main subject of this paper is the interval Gaussian algorithm, which produces an interval Vector $[ x ]^G $ analogously to its well-known counterpart in classical numerical analysis. Criteria are derived to guarantee the existence of $[ x ]^G $ if the $n \times n$ interval matrix $[ A ]$ is degenerate to a point matrix or if its comparison matrix $\langle [ A ] \rangle$ is irreducible and diagonally dominant. While in the first case all classical criteria of feasibility apply, the second case yields to a criterion which seems to be new. A way to construct matrices such that $[ x ]^G $ does not exist, although it does for each matrix $\tilde A \in [ A ]$, is also indicated.

If $\hat x$ is the computed solution to a tridiagonal system $Ax = b$ obtained by Gaussian elimination, what is the “best” bound available for the error $x - \hat x$ and how can it be computed efficiently? This question is answered using backward error analysis, perturbation theory, and properties of the $LU$ factorization of A. For three practically important classes of tridiagonal matrix, those that are symmetric positive definite, totally nonnegative, or M-matrices, it is shown that $(A + E)\hat x = b$ where the backward error matrix E is small componentwise relative to A. For these classes of matrices the appropriate forward error bound involves Skeel’s condition number cond $(A,x)$, which, it is shown, can be computed exactly in $O(n)$ operations. For diagonally dominant tridiagonal A the same type of backward error result holds, and the author obtains a useful upper bound for cond $(A,x)$ that can be computed in $O(n)$ operations. Error bounds and their computation for general tridiagonal matrices a...

A Hungarian scaling is a diagonal scaling of a matrix that is typically applied along with a permutation to a sparse linear system before calling a direct or iterative solver. A matrix that has been Hungarian scaled and reordered has all entries of modulus less than or equal to 1 and entries of modulus 1 on the diagonal. An important fact that has been overlooked by the previous research into Hungarian scaling of linear systems is that a given matrix typically has a range of possible Hungarian scalings and direct or iterative solvers may behave quite differently under each of these scalings. Since standard algorithms for computing Hungarian scalings return only one scaling, it is natural to ask whether a superior performing scaling can be obtained by searching within the set of all possible Hungarian scalings. To this end we propose a method for computing a Hungarian scaling that is optimal from the point of view of diagonal dominance. Our method uses max-balancing, which minimizes the largest off-diagonal entries in the matrix. Numerical experiments illustrate the increased diagonal dominance produced by max-balanced Hungarian scaling as well as the reduced need for row interchanges in Gaussian elimination with partial pivoting and the improved stability of LU factorizations without pivoting. We additionally find that applying the max-balancing scaling before computing incomplete LU preconditioners improves the convergence rate of certain iterative methods.