Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Adaptive Monte Carlo methods for matrix equations with applications

This paper discusses empirical studies with both the adaptive correlated sequential sampling method and the adaptive importance sampling method which can be used in solving matrix and integral equations. Both methods achieve geometric convergence (provided the number of random walks per stage is large enough) in the sense: e_ν≤cλ^ν, where e_ν is the error at stage ν, λ∈(0,1) is a constant, c>0 is also a constant. Thus, both methods converge much faster than the conventional Monte Carlo method. Our extensive numerical test results show that the adaptive importance sampling method converges faster than the adaptive correlated sequential sampling method, even with many fewer random walks per stage for the same problem. The methods can be applied to problems involving large scale matrix equations with non-sparse coefficient matrices. We also provide an application of the adaptive importance sampling method to the numerical solution of integral equations, where the integral equations are converted into matrix equations (with order up to 8192×8192) after discretization. By using Niederreiter’s sequence, instead of a pseudo-random sequence when generating the nodal point set used in discretizing the phase space Γ, we find that the average absolute errors or relative errors at nodal points can be reduced by a factor of more than one hundred.     

A finite element — Capacitance method for elliptic problems on regions partitioned into subregions

Summary A method is given for the solution of linear equations arising in the finite element method applied to a general elliptic problem. This method reduces the original problem to several subproblems (of the same form) considered on subregions, and an auxiliary problem. Very efficient iterative methods with the preconditioning operator and using FFT are developed for the auxiliary problem.     

Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems

Summary A forward error analysis is presented for the Björck-Pereyra algorithms used for solving Vandermonde systems of equations. This analysis applies to the case where the points defining the Vandermonde matrix are nonnegative and are arranged in increasing order. It is shown that for a particular class of Vandermonde problems the error bound obtained depends on the dimensionn and on the machine precision only, being independent of the condition number of the coefficient matrix. By comparing appropriate condition numbers for the Vandermonde problem with the forward error bounds it is shown that the Björck-Pereyra algorithms introduce no more uncertainty into the numerical solution than is caused simply by storing the right-hand side vector on the computer. A technique for computing running a posteriori error bounds is derived. Several numerical experiments are presented, and it is observed that the ordering of the points can greatly affect the solution accuracy.     

Finding minimum height elimination trees for interval graphs in polynomial time

The elimination tree plays an important role in many aspects of sparse matrix factorization. The height of the elimination tree presents a rough, but usually effective, measure of the time needed to perform parallel elimination. Finding orderings that produce low elimination is therefore important. As the problem of finding minimum height elimination tree orderings is NP-hard, it is interesting to concentrate on limited classes of graphs and find minimum height elimination trees for these efficiently. In this paper, we use clique trees to find an efficient algorithm for interval graphs which make an important subclass of chordal graphs. We first illustrate this method through an algorithm that finds minimum height elimination for chordal graphs. This algorithm, although of exponential time complexity, is conceptionally simple and leads to a polynomial-time algorithm for finding minimum height elimination trees for interval graphs.This work was supported by grants from the Norwegian Research Council.     

Error bounds for computed eigenvalues and eigenvectors. II

Summary In this paper, motivated by Symm-Wilkinson's paper [5], we describe a method which finds the rigorous error bounds for a computed eigenvalue ⁽⁰⁾ and a computed eigenvectorx ⁽⁰⁾ of any matrix A. The assumption in a previous paper [6] that ⁽⁰⁾,x ⁽⁰⁾ andA are real is not necessary in this paper. In connection with this method, Symm-Wilkinson's procedure is discussed, too.     

A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes

Summary In this paper we describe how to use Gram-Schmidt factorizations of Daniel et al. [1] to realize the method of [8] for solving linearly constrained linear least squares problems. The main advantage of using these factorizations is that it is relatively easy to take data changes into account, if necessary.The algorithm is compared numerically with two other codes, one of them published by Lawson and Hanson [3]. Further computational tests show the efficiency of the proposed methods, if a few data of the original problem are changed subsequently.This paper was sponsored by Deutsche Forschungsgemeinschaft, Bonn-Bad Godesberg     

Two composition methods for solving certain systems of linear equations

Summary This note is concerned with the following problem: Given a systemA·x=b of linear equations and knowing that certains of its subsystemsA ¹·x ¹=b ¹, ...,A ^m ·x ^m =b ^m can be solved uniquely what can be said about the regularity ofA and how to find the solutionx fromx ¹, ...,x ^m ? This question is of particular interest for establishing methods computing certain linear or quasilinear sequence transformations recursively [7, 13, 15].Work performed under NATO Research Grant 027-81     

Compression of uniform embeddings into Hilbert space

If one tries to embed a metric space uniformly in Hilbert space, how close to quasi-isometric could the embedding be? We answer this question for finite dimensional CAT(0) cube complexes and for hyperbolic groups. In particular, we show that the Hilbert space compression of any hyperbolic group is 1.     

Optimal acceptance rates for Metropolis algorithms: Moving beyond 0.234

Recent optimal scaling theory has produced a condition for the asymptotically optimal acceptance rate of Metropolis algorithms to be the well-known 0.234 when applied to certain multi-dimensional target distributions. These d$d$-dimensional target distributions are formed of independent components, each of which is scaled according to its own function of d$d$. We show that when the condition is not met the limiting process of the algorithm is altered, yielding an asymptotically optimal acceptance rate which might drastically differ from the usual 0.234. Specifically, we prove that as d→∞$d\to \infty$ the sequence of stochastic processes formed by say the i^∗$i^{\ast }$th component of each Markov chain usually converges to a Langevin diffusion process with a new speed measure υ$\upsilon$, except in particular cases where it converges to a one-dimensional Metropolis algorithm with acceptance rule α^∗${\alpha }^{\ast }$. We also discuss the use of inhomogeneous proposals, which might prove to be essential in specific cases.     

Random Matchings in Regular Graphs

d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996     

A Normal Law for Matchings

Dedicated to the memory of Paul Erdős, both for his pioneering discovery of normality in unexpected places, and for his questions, some of which led (eventually) to the present work.   For a simple graph G, let be the size of a matching drawn uniformly at random from the set of all matchings of G. Motivated by work of C. Godsil [11], we give, for a sequence and , several necessary and sufficient conditions for asymptotic normality of the distribution of , for instance

Rehabilitation of the Gauss-Jordan algorithm

Summary In this paper a Gauss-Jordan algorithm with column interchanges is presented and analysed. We show that, in contrast with Gaussian elimination, the Gauss-Jordan algorithm has essentially differing properties when using column interchanges instead of row interchanges for improving the numerical stability. For solutions obtained by Gauss-Jordan with column interchanges, a more satisfactory bound for the residual norm can be given. The analysis gives theoretical evidence that the algorithm yields numerical solutions as good as those obtained by Gaussian elimination and that, in most practical situations, the residuals are equally small. This is confirmed by numerical experiments. Moreover, timing experiments on a Cyber 205 vector computer show that the algorithm presented has good vectorisation properties.     

Depths and Cohen–Macaulay properties of path ideals

Given a tree T on n vertices, there is an associated ideal I   of R[_x1,…,_xn]$R[x_1,\dots ,x_n]$ generated by all paths of a fixed length ? of T  . We classify all trees for which R/I$R/I$ is Cohen–Macaulay, and we show that an ideal I whose generators correspond to any collection of subtrees of T satisfies the König property. Since the edge ideal of a simplicial tree has this form, this generalizes a result of Faridi. Moreover, every square-free monomial ideal can be represented (non-uniquely) as a subtree ideal of a graph, so this construction provides a new combinatorial tool for studying square-free monomial ideals.     

Perturbation results for nearly uncoupled Markov chains with applications to iterative methods

Summary The standard perturbation theory for linear equations states that nearly uncoupled Markov chains (NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that shows that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping, criteria, iterative aggregation/disaggregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to Grassman, Taksar and Heyman was recently shown by O'Cinneide to achieve such bounds.Supported by the National Science Foundation under grant CCR-9000526 and its renewal, grant CCR-9201692. This research was done in part, during the author's visit to the Institute for Mathematics and its Applications, 514 Vincent Hall, 206 Church St. S.E., University of Minnesota, Minneapolis, MN 55455, USA     

The general Neville-Aitken-algorithm and some applications

Summary In this note we will present the most general linear form of a Neville-Aitken-algorithm for interpolation of functions by linear combinations of functions forming a ebyev-system. Some applications are given. Expecially we will give simple new proofs of the recurrence formula for generalized divided differences [5] and of the author's generalization of the classical Neville-Aitkena-algorithm[8]applying to complete ebyev-systems. Another application of the general Neville-Aitken-algorithm deals with systems of linear equations. Also a numerical example is given.     

Fehleranalyse für die Gauß-Elimination zur Berechnung der Lösung minimaler Länge

Summary Presented is a realistic, elementwise analysis for the rounding errors of a generalization of Gauss elimination for solving the linear best least squares problem without pivoting. The bounds are suitable to determine the class of well-posed problems to the given method. A mixed error analysis is given and then the effects of errors in the input data are studied. Numerical examples demonstrate the efficiency.

     

Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type

Let C be a clutter with a perfect matching e₁,…,e_g of König type and let Δ_C be the Stanley-Reisner complex of the edge ideal of C. If all c-minors of C have a free vertex and C is unmixed, we show that Δ_C is pure shellable. We are able to describe, in combinatorial and algebraic terms, when Δ_C is pure. If C has no cycles of length 3 or 4, then it is shown that Δ_C is pure if and only if Δ_C is pure shellable (in this case e_i has a free vertex for all i), and that Δ_C is pure if and only if for any two edges f₁,f₂ of C and for any e_i, one has that f₁∩e_i⊂f₂∩e_i or f₂∩e_i⊂f₁∩e_i. It is also shown that this ordering condition implies that Δ_C is pure shellable, without any assumption on the cycles of C. Then we prove that complete admissible uniform clutters and their Alexander duals are unmixed. In addition, the edge ideals of complete admissible uniform clutters are facet ideals of shellable simplicial complexes, they are Cohen-Macaulay, and they have linear resolutions. Furthermore if C is admissible and complete, then C is unmixed. We characterize certain conditions that occur in a Cohen-Macaulay criterion for bipartite graphs of Herzog and Hibi, and extend some results of Faridi-on the structure of unmixed simplicial trees-to clutters with the König property without 3-cycles or 4-cycles.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

A contribution to the theory of condition

Summary In this paper the use of the condition number of a problem, as defined by Rice in 1966, is discussed. For the eigenvalue, eigenvector, and linear least squares problems either condition numbers according to various norms are determined or lower and upper bounds for them are derived.