On a class of matrices which arise in the numerical solution of Euler equations

Summary We study block matricesA=[A_ij], where every blockA _ij ^k,k is Hermitian andA _ii is positive definite. We call such a matrix a generalized H-matrix if its block comparison matrix is a generalized M-matrix. These matrices arise in the numerical solution of Euler equations in fluid flow computations and in the study of invariant tori of dynamical systems. We discuss properties of these matrices and we give some equivalent conditions for a matrix to be a generalized H-matrix.Research supported by the Graduiertenkolleg mathematik der Universität Bielefeld     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

Commutativity of Almost <Emphasis Type="Italic">F</Emphasis>-algebras

Let A be an Archimedean vector lattice, let be its Dedekind completion and let B be a Dedekind complete vector lattice. If Ψ ₀:A × A→ B is a positive orthosymmetric bimorphism, then there exists a positive bimorphism extension Ψ of Ψ ₀ to × in B which is orthosymmetric. This leads to a new and short proof of the commutativity of the almost f-algebras multiplications.     

The truncatedSVD as a method for regularization

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in cases of ill-conditioned matrices with well-determined numerical rank.This work was carried out while the author visited the Dept. of Computer Science, Stanford University, California, U.S.A., and was supported in part by National Science Foundation Grant Number DCR 8412314, by a Fulbright Supplementary Grant, and by the Danish Space Board.     

Incomplete factorizations of singular linear systems

Recent works have shown that, whenA is a Stieltjes matrix, its so-called modified incomplete factorizations provide effective preconditioning matrices for solvingAx=b by polynomially accelerated iterative methods. We extend here these results to the singular case with the conclusion that the latter techniques are able to solve singular systems at the same speed as regular systems.Research supported by the Fonds National de la Recherche Scientifique (Belgium) — Aspirant.     

LU decompositions of generalized diagonally dominant matrices

Summary Using the simple vehicle ofM-matrices, the existence and stability ofLU decompositions of matricesA which can be scaled to diagonally dominant (possibly singular) matrices are investigated. Bounds on the growth factor for Gaussian elimination onA are derived. Motivation for this study is provided in part by applications to solving homogeneous systems of linear equationsAx=0, arising in Markov queuing networks, input-output models in economics and compartmental systems, whereA or –A is an irreducible, singularM-matrix.This paper extends earlier work by Funderlic and Plemmons and by Varga and Cai.Research sponsored by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract W-7405-eng-26 with the Union Carbide CorporationResearch supported in part by the National Science Foundation under Grant No. MCS 8102114Research supported in part by the U.S. Army Research Office under contract no. DAAG 29-81-k-0132     

Convergence of sequential and asynchronous nonlinear paracontractions

Summary We establish the convergence of sequential and asynchronous iteration schemes for nonlinear paracontracting operators acting in finite dimensional spaces. Applications to the solution of linear systems of equations with convex constraints are outlined. A first generalization of one of our convergence results to an infinite pool of asymptotically paracontracting operators is also presented.Research supported in part by Sonderforschungsbereich 343 Diskrete Strukturen in der MathematikResearch supported in part by NSF Grant DMS-9007030 and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität BielefeldResearch supported in part by U.S. Air Force Grant AFOSR-88-0047, by NSF Grants DMS-8901860 and DMS-9007030, and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität Bielefeld     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Accuracy of TSVD solutions computed from rank-revealing decompositions

Summary. Rank-revealing decompositions are favorable alternatives to the singular value decomposition (SVD) because they are faster to compute and easier to update. Although they do not yield all the information that the SVD does, they yield enough information to solve various problems because they provide accurate bases for the relevant subspaces. In this paper we consider rank-revealing decompositions in computing estimates of the truncated SVD (TSVD) solution to an overdetermined system of linear equations , where is numerically rank deficient. We derive analytical bounds which show how the accuracy of the solution is intimately connected to the quality of the subspaces. Received July 12, 1993 / Revised version received November 14, 1994     

Trigonometric Hermite wavelet approximation for the integral equations of second kind with weakly singular kernel

This paper is concerned with a trigonometric Hermite wavelet Galerkin method for the Fredholm integral equations with weakly singular kernel. The kernel function of this integral equation considered here includes two parts, a weakly singular kernel part and a smooth kernel part. The approximation estimates for the weakly singular kernel function and the smooth part based on the trigonometric Hermite wavelet constructed by E. Quak [Trigonometric wavelets for Hermite interpolation, Math. Comp. 65 (1996) 683–722] are developed. The use of trigonometric Hermite interpolant wavelets for the discretization leads to a circulant block diagonal symmetrical system matrix. It is shown that we only need to compute and store O(N)$\mathrm{O}(N)$ entries for the weakly singular kernel representation matrix with dimensions N²$N^2$ which can reduce the whole computational cost and storage expense. The computational schemes of the resulting matrix elements are provided for the weakly singular kernel function. Furthermore, the convergence analysis is developed for the trigonometric wavelet method in this paper.     

Zur Inversmonotonie diskreter Probleme

Summary This paper describes sufficient conditions for a real square matrixA=(a _ij ) to have a nonnegative inverse. It is not assumed thata _ij 0 forij. We indicate several applications to matricesA that occur in finite-difference and finiteelement methods for boundary-value problems.

---

---

Diese Arbeit enthält Ergebnisse aus der Dissertation des Verfassers, die von Prof. Dr. E. Bohl, Universität Münster, angeregt und unterstützt wurde.     

An efficient rank detection procedure for modifying the ULV decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The problem of adding and deleting rows from the ULVD (called updating and downdating, respectively) is considered. The ULVD can be updated and downdated much faster than the SVD, hence its utility. When updating or downdating the ULVD, it is necessary to compute its numerical rank. In this paper, we propose an efficient algorithm which almost always maintains rank-revealing structure of the decomposition after an update or downdate without standard condition estimation. Moreover, we can monitor the accuracy of the information provided by the ULVD as compared to the SVD by tracking exact Frobenius norms of the two small blocks of the lower triangular factor in the decomposition.     

Perturbation analysis of the orthogonal procrustes problem

Given two arbitrary real matricesA andB of the same size, the orthogonal Procrustes problem is to find an orthogonal matrixM such that the Frobenius norm MA – B is minimized. This paper treats the common case when the orthogonal matrixM is required to have a positive determinant. The stability of the problem is studied and supremum results for the perturbation bounds are derived.     

A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues

Summary. We prove that the 2-norm distance from an matrix A to the matrices that have a multiple eigenvalue is equal to where the singular values are ordered nonincreasingly. Therefore, the 2-norm distance from A to the set of matrices with multiple eigenvalues is Received February 19, 1998 / Revised version received July 15, 1998 / Published online: July 7, 1999     

Fast low-rank modifications of the thin singular value decomposition

This paper develops an identity for additive modifications of a singular value decomposition (SVD) to reflect updates, downdates, shifts, and edits of the data matrix. This sets the stage for fast and memory-efficient sequential algorithms for tracking singular values and subspaces. In conjunction with a fast solution for the pseudo-inverse of a submatrix of an orthogonal matrix, we develop a scheme for computing a thin SVD of streaming data in a single pass with linear time complexity: A rank-r thin SVD of a p × q matrix can be computed in O(pqr) time for .     

Fast inversion algorithms of Toeplitz-plus-Hankel matrices

Summary The paper deals with the problems of fast inversion of matricesA=T+H, whereT is Toeplitz andH is Hankel. Several algorithms are presented and compared, among them algorithms working for arbitrary strongly nonsingular matricesA=T+H.     

Computing the CS and the generalized singular value decompositions

Summary If the columns of a matrix are orthonormal and it is partitioned into a 2-by-1 block matrix, then the singular value decompositions of the blocks are related. This is the essence of the CS decomposition. The computation of these related SVD's requires some care. Stewart has given an algorithm that uses the LINPACK SVD algorithm together with a Jacobitype clean-up operation on a cross-product matrix. Our technique is equally stable and fast but avoids the cross product matrix. The simplicity of our technique makes it more amenable to parallel computation on systolic-type computer architectures. These developments are of interest because a good way to compute the generalized singular value decomposition of a matrix pair (A, B) is to compute the CS decomposition of a certain orthogonal column matrix related toA andB.The research associated with this paper was partially supported by the Office of Naval Research contract N00014-83-K-0640, USA     

Approximate factorizations with S/P consistently ordered M-factors

The behaviour of PCG methods for solving a finite difference or finite element positive definite linear systemAx=b with a (pre)conditioning matrixB=U ^TP^–1 U (whereU is upper triangular andP=diag(U)) obtained from a modified incomplete factorization, isunpredictable in the present status of knowledge whenever the upper triangular factor is not strictly diagonally dominant and 2P –D, whereD=diag(A), is not symmetric positive definite. The origin of this rather surprising shortcoming of the theory is that all upper bounds on the associated spectral condition number (B ^–1 A) obtained so far require either the strict diagonal dominance of the upper triangular factor or the strict positive definiteness of 2P –D. It is our purpose here to improve the theory in this respect by showing that, when the triangular factors are S/P consistently orderedM-matrices, nonstrict diagonal dominance is generally a sufficient requirement, without additional condition on 2P –D. As a consequence, the new analysis does not require diagonal perturbations (otherwise needed to keep control of the diagonal dominance ofU or of the positive definiteness of 2P –D). Further, the bounds obtained here on (B ^–1 A) are independent of the lower spectral bound ofD ^–1 A meaning that quasi-singular problems can be solved at the same speed as regular ones, an unexpected result.     

Scaled total least squares fundamentals

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the vector c and/or the matrix B such that the corrected system is compatible. In ordinary least squares (LS) the correction is restricted to c, while in data least squares (DLS) it is restricted to B. In scaled total least squares (STLS) [22], corrections to both c and B are allowed, and their relative sizes depend on a real positive parameter . STLS unifies several formulations since it becomes total least squares (TLS) when , and in the limit corresponds to LS when , and DLS when . This paper analyzes a particularly useful formulation of the STLS problem. The analysis is based on a new assumption that guarantees existence and uniqueness of meaningful STLS solutions for all parameters . It makes the whole STLS theory consistent. Our theory reveals the necessary and sufficient condition for preserving the smallest singular value of a matrix while appending (or deleting) a column. This condition represents a basic matrix theory result for updating the singular value decomposition, as well as the rank-one modification of the Hermitian eigenproblem. The paper allows complex data, and the equivalences in the limit of STLS with DLS and LS are proven for such data. It is shown how any linear system can be reduced to a minimally dimensioned core system satisfying our assumption. Consequently, our theory and algorithms can be applied to fully general systems. The basics of practical algorithms for both the STLS and DLS problems are indicated for either dense or large sparse systems. Our assumption and its consequences are compared with earlier approaches. Received June 2, 1999 / Revised version received July 3, 2000 / Published online July 25, 2001