URL: ftp://thales.cs.umd.edu/pub/reports/rdlsp.dvi Author: G. H. Golub, V. Klema, and G. W. Stewart Title: "Rank Degeneracy and Least Squares Problems" Reference: CS TR 456, 1976 Abstract: This paper is concerned with least squares problems when the least squares matrix $A$ is near a matrix that is not of full rank. A definition of numerical rank is given. It is shown that under certain conditions when $A$ has numerical rank $r$ there is a distinguished $r$ dimensional subspace of the column space of $A$ that is insensitive to how it is approximated by $r$ independent columns of $A$. The consequences of this fact for the least squares problem are examined. Algorithms are described for approximating the stable part of the column space of $A$. [The dvi file is from a LaTeX version of the original.] URL: ftp://thales.cs.umd.edu/pub/reports/tsisnumc.dvi Author: G. W. Stewart, W. J. Stewart, and D. F. McAllister Title: "A Two-Stage Iteration for Solving Nearly Uncoupled Markov Chains" Reference: CS TR 1348, April 1984 Abstract: This paper is concerned with an iteration for determining the steady-state probability vector of a nearly uncoupled Markov Chain. The states of these chains can be partitioned into aggregates with low probabilities of transitions between aggregates. The iteration consists of alternating block Gauss--Seidel iterations with Rayleigh--Ritz refinements. Under natural regularity conditions, the composite iteration reduces the error by a factor proportional to the size of the coupling between aggregates, so that the more loosely the chain is coupled, the faster the convergence. URL: ftp://thales.cs.umd.edu/pub/reports/htev.dvi Author: Nancy David and G. W. Stewart Title: "Hypothesis Testing with Errors in the Variables" Reference: CS TR 1735, November 1986 Abstract: In this paper we give reason to hope that errors in regression variables are not as harmful as one might expect. Specifically, we will show that although the errors can change the values of the quantities one computes in a regression analysis, under certain conditions they leave the distributions of the quantities approximately unchanged. URL: ftp://thales.cs.umd.edu/pub/reports/imsli.dvi Author: G. W. Stewart Title: "An Iterative Method for Solving Linear Inequalities" Reference: CS TR TR-1833, April 1987 Abstract: This paper describes and analyzes a method for finding nontrivial solutions of the inequality $Ax \geq 0$, where $A$ is an $m \times n$ matrix of rank $n$. The method is based on the observation that a certain function $f$ has a unique minimum if and only if the inequality {\it fails to have} a nontrivial solution. Moreover, if there is a solution, an attempt to minimize $f$ will produce a sequence that will diverge in a direction that converges to a solution of the inequality. The technique can also be used to solve inhomogeneous inequalities and hence linear programming problems, although no claims are made about competitiveness with existing methods. URL: ftp://thales.cs.umd.edu/pub/reports/iscp.dvi Author: G. W. Stewart Title: "Invariant Subspaces and Capital Punishment (A Participatory Paper)" Reference: CS TR 1923, September 1987 Abstract: The notion of invariant subspaces is useful in a number of theoretical and practical applications. In this paper we give an elementary treatment of invariant subspaces that stresses their connection with simple eigenvalues and their eigenvectors. URL: ftp://thales.cs.umd.edu/pub/reports/cdllm.dvi Author: G. W. Stewart Title: "Continuity in Degenerate Log-linear Models" Reference: Unpublished manuscript, September 1987 Abstract: Degeneracy in a log-linear model occurs when a configuration of zero counts causes the likelihood function to fail to attain its supremum. This problem is sometimes treated computationally by replacing the offending zero counts with suitably small numbers. However, to justify this procedure it must be shown that the estimates of the nonzero cells are not greatly altered. In this paper we establish a such a continuity theorem. URL: ftp://thales.cs.umd.edu/pub/reports/spt.dvi Author: G. W. Stewart Title: "Stochastic Perturbation Theory" Reference: UMIACS-TR-88-76, CS-TR-2129, October 1988 Appeared in SIAM Review 32 (1990) 576--610. Related-Resources: Fig. 2.1, Fig. 2.2 Abstract: In this paper classical matrix perturbation theory is approached from a probabilistic point of view. The perturbed quantity is approximated by a first order perturbation expansion, in which the perturbation is assumed to be random. This permits the computation of statistics estimating the variation in the perturbed quantity. Up to the higher order terms that are ignored in the expansion, these statistics tend to be more realistic than perturbation bounds obtained in terms of norms. The technique is applied to a number of problems in matrix perturbation theory, including least squares and the eigenvalue problem. URL: ftp://thales.cs.umd.edu/pub/reports/cmclmps.dvi Author: G. W. Stewart Title: "Communication and Matrix Computations on Large Message Passing Systems" Reference: UMIACS-TR-88-81, CS-TR-2135, October 1988, Revised January, 1990 Appeared in Parallel Computing \bf 16 (1990) 27--40. Related-Resources: Fig. 4.1, Fig. 4.2, Fig. 4.3 Abstract: This paper is concerned with the consequences for matrix computations of having a rather large number of general purpose processors, say ten or twenty thousand, connected in a network in such a way that a processor can communicate only with its immediate neighbors. Certain communication tasks associated with most matrix algorithms are defined and formulas developed for the time required to perform them under several communication regimes. The results are compared with the times for a nominal $n^3$ floating point operations. The results suggest that it is possible to use a large number of processors to solve matrix problems at a relatively fine granularity, provided fine grain communication is available. URL: ftp://thales.cs.umd.edu/pub/reports/ptlsev.dvi Author: G. W. Stewart Title: "Perturbation Theory and Least Squares with Errors in the Variables" Reference: To appear in the proceedings of the AMS Workshop on Measurement Error Models, Humboldt, 1989. Related-Resources: Fig. 8.1 Fig. 8.1 Abstract: In this note we examine what matrix perturbation theory has to say about ordinary least squares estimation when the regression matrix is contaminated by random errors. The conclusion is that there is a regime in which the errors can have important, even overwhelming effects yet do not affect the validity of ordinary least squares procedures. The boundary of this regime is indicated by a diagnostic number which can be calculated from the data. URL: ftp://thales.cs.umd.edu/pub/reports/tsrbehm.dvi Author: G. W. Stewart Title: "Two Simple Residual Bounds for the Eigenvalues of Hermitian Matrices" Reference: UMIACS-TR 89-123, CS-TR 2364, December 1989 Appeared in SIAM J. Mat. Anal. Appl. 12 (1991) 205--208. Abstract: Let $A$ be Hermitian and let the orthonormal columns of $X$ span an approximate invariant subspace of $X$. Then the residual $R = AX-XM$ $(M=X\ctp AX)$ will be small. The theorems of this paper bound the distance of the spectrum of $M$ from the spectrum of $A$ in terms of appropriate norms of $R$. URL: ftp://thales.cs.umd.edu/pub/reports/snumc.dvi Author: G. W. Stewart Title: "On the Sensitivity of Nearly Uncoupled Markov Chains" Reference: UMIACS TR 90-18, CS TR 2406, February 1990 Appeared in Numerical Solutions of Markov Chains, W. J. Stewart ed., Dekker, New York, 1990. Abstract: Nearly uncoupled Markov chains (aka nearly completely decomposable Markov chains) arise in a variety of applications, where they model loosely coupled systems. In such systems it may be difficult to determine the transitions probabilities with high accuracy. This paper investigates the sensitivity of the limiting distribution of the chain to perturbations in the transition probabilities. The conclusion is that nearly uncoupled Markov chains are quite sensitive to such perturbations but the perturbation of the limiting distribution is not arbitrary. URL: ftp://thales.cs.umd.edu/pub/reports/egmcnme.dvi Author: G. W. Stewart and G. Zhang Title: "Eigenvalues of Graded Matrices and the Condition Numbers of a Multiple Eigenvalue" Reference: UMIACS TR 90-31, CS TR 2420, February 1990 Appeared in Numerische Mathematik 58 (1991) 703--712. Abstract: This paper concerns two closely related topics: the behavior of the eigenvalues of graded matrices and the perturbation of a nondefective multiple eigenvalue. We will show that the eigenvalues of a graded matrix tend to share the graded structure of the matrix and give precise conditions insuring that this tendency is realized. These results are then applied to show that the secants of the canonical angles between the left and right invariant subspaces of a multiple eigenvalue tend to characterize its behavior when its matrix is slightly perturbed. URL: ftp://thales.cs.umd.edu/pub/reports/uast.dvi Author: G. W. Stewart Title: "An Updating Algorithm for Subspace Tracking" Reference: UMIACS-TR-90-86, CS-TR 2494, July 1990, Revised January 1991 To appear in IEEE Transactions on Acoustics, Speech and Signal Processing Related-Resources: Fortran program Abstract: In certain signal processing applications it is required to compute the null space of a matrix whose rows are samples of a signal. The usual tool for doing this is the singular value decomposition. However, the singular value decomposition has the drawback that it requires $O(p^3)$ operations to recompute when a new sample arrives. In this paper, we show that a different decomposition, called the URV, decomposition is equally effective in exhibiting the null space and can be updated in $O(p^2)$ time. The updating technique can be run on a linear array of $p$ processors in $O(p)$ time. URL: ftp://thales.cs.umd.edu/pub/reports/icccs.dvi Author: G. W. Stewart Title: "Incremental Condition Calculation and Column Selection" Reference: UMIACS TR 90-87, CS TR 2495, July 1990 Related-Resources: Fig. 4.1 Abstract: This paper describes a method for calculating the condition number of a matrix in the Frobenius norm that can be used to select columns in the course of computing a QR~decomposition. When the number of rows of the matrix is much greater than the number of columns, the additional overhead is negligible. Limited numerical experiments suggest that the method is quite good at finding gaps in the singular values of the matrix. URL: ftp://thales.cs.umd.edu/pub/reports/dmsnumc.dvi Author: G. W. Stewart and G. Zhang Title: "On a Direct Method for the Solution of Nearly Uncoupled Markov Chains" Reference: UMIACS TR 90-95, CS TR 2504, July 1990 Appeared in Numerische Mathematik 59 (1991) 1--12. Abstract: This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting as well as corrections of small pivots by sums of off-diagonal elements in the pivoting columns is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associate with the aggregate and the coupling respectively. URL: ftp://thales.cs.umd.edu/pub/reports/ptsvd.dvi Author: G. W. Stewart Title: "Perturbation Theory for the Singular Value Decomposition" Reference: UMIACS-TR-90-124, CS-TR 2539, September 1990 Appeared in SVD and Signal Processing, II, R. J. Vacarro ed., Elsevier, Amsterdam, 1991. Abstract: The singular value decomposition has a number of applications in digital signal processing. However, the the decomposition must be computed from a matrix consisting of both signal and noise. It is therefore important to be able to assess the effects of the noise on the singular values and singular vectors\,---\,a problem in classical perturbation theory. In this paper we survey the perturbation theory of the singular value decomposition. URL: ftp://thales.cs.umd.edu/pub/reports/arrruf.dvi Author: G. W. Stewart Title: "On an Algorithm for Refining a Rank-Revealing URV~Factorization and a Perturbation Theorem for Singular Values" Reference: UMIACS-TR-91-38, CS-TR 2626, March 1991 Abstract: In this note we consider an iterative algorithm for moving a triangular matrix toward diagonality. The method is shown to converge under conditions that are likely to be met in practice. A result of the convergence proof in a new perturbation theorem for singular values. URL: ftp://thales.cs.umd.edu/pub/reports/urrud.dvi Author: G. W. Stewart Title: "Updating A Rank-Revealing ULV~Decomposition" Reference: UMIACS-TR-91-39, CS-TR 2627, March 1991 To appear in SIAM J. Matrix Anal. Appl. Abstract: A ULV~decomposition of a matrix $A$ of order $n$ is a decomposition of the form $A = ULV\ctp$, where $U$ and $V$ are orthogonal matrices and $L$ is a lower triangular matrix. When $A$ is approximately of rank $k$, the decomposition is rank revealing if the last $n-k$ rows of $L$ are small. This paper presents algorithms for updating a rank-revealing ULV~decomposition. The algorithms run in $O(n^2)$ time, and can be implemented on a linear array of processors to run in $O(n)$ time. URL: ftp://thales.cs.umd.edu/pub/reports/bqrasvd.dvi Author: R. Mathias, G. W. Stewart Title: "A Block QR~Algorithm and the Singular Value Decomposition" Reference: Revision May 1992 To appear in Linear Algebra and its Applications Abstract: In this note we consider an iterative algorithm for moving a triangular matrix toward diagonality. The algorithm is related to algorithms for refining rank-revealing triangular decompositions and in a variant form to the QR~algorithm. It is shown to converge if there is a sufficient gap in the singular values of the matrix, and the analysis provides a new approximation theorem for singular values and singular subspaces. URL: ftp://thales.cs.umd.edu/pub/reports/daeurrud.dvi Author: G. Adams, M. F. Griffin, and G. W. Stewart Title: "Direction-of-Arrival Estimation Using the Rank-Revealing URV Decomposition" Reference: UMIACS-TR 91-46, CS-TR-2640, March 1991 Appeared in Proceedings of ACASSP-91. Related-Resources: Fig. 1, Fig. 2, Fig. 3, Fig. 4, Fig. 5 Abstract: An algorithm for updating the null space of a matrix is described. The algorithm is based on a new decomposition, called the URV decomposition, which can be updated in $O(N^2)$ and serves as an intermediary between the QR decomposition and the singular value decomposition. The URV decomposition is applied to a high-resolution direction of arrival problem based on the MUSIC algorithm. A virtue of the updating algorithm is the running estimate of rank. URL: ftp://thales.cs.umd.edu/pub/reports/lls.dvi Author: G. W. Stewart Title: "Lanczos and Linear Systems" Reference: UMIACS-TR-91-47, CS-TR 2641, March 1991 Abstract: Lanczos's major contributions to the numerical solution of linear equations are contained in two papers: ``An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators'' and ``Solutions of Linear Equations by Minimized Iterations,'' the second of which contains the method of conjugate gradients. In this note we retrace Lanczos's journey from Krylov sequences to conjugate gradients. URL: ftp://thales.cs.umd.edu/pub/reports/eaqruew.dvi Author: G. W. Stewart Title: "Error Analysis of QR~Updating with Exponential Windowing" Reference: UMIACS-TR-91-79, CS-TR 2685, May 1991 Abstract: E xponential windowing is a widely used technique for suppressing the effects of old data as new data is added to a matrix. Specifically, given an $n\times p$ matrix $X_n$ and a ``forgetting factor'' $\beta\in(0,1)$, one works with the matrix $\dia(\beta^{n-1},\beta^{n-2},\ldots,1)X_n$. In this paper we examine an updating algorithm for computing the QR~factorization of $\dia(\beta^{n-1},\beta^{n-2},\ldots,1)X_n$ and show that it is unconditionally stable in the presence of rounding errors. URL: ftp://thales.cs.umd.edu/pub/reports/ptrmp.dvi Author: G. W. Stewart Title: "Perturbation Theory for Rectangular Matrix Pencils" Reference: UMIACS-TR-91-105, CS-TR 2721, July 1991 Revised, March 1993 Abstract: The theory of eigenvalues and eigenvectors of rectangular matrix pencils is complicated by the fact that arbitrarily small perturbations of the pencil can cause them disappear. However, there are applications in which the properties of the pencil ensure the existence of eigenvalues and eigenvectors. In this paper it is shown how to develop a perturbation theory for such pencils. URL: ftp://thales.cs.umd.edu/pub/reports/lepso.dvi Author: P. Schweitzer G. W. Stewart Title: "The Laurent Expansion of Pencils that are Singular at the Origin" Reference: UMIACS-TR-91-164, CS-TR-2809, December 1991 Abstract: This paper gives two new proofs of a theorem of Langenhop on the Laurent expansion of a matrix pencil that is singular at the origin. The second, based on a decomposition of Van Dooren, leads to a computational algorithm. URL: ftp://thales.cs.umd.edu/pub/reports/darrurvd.dvi Author: E. C. Boman, M. F. Griffen, and G. W. Stewart Title: "Direction of Arrival and the Rank-Revealing URV Decomposition" Reference: UMIACS-TR-91-166, CS-TR-2813, December 1991 Abstract: In many practical direction-of-arrival (DOA) problems the number of sources and their directions from an antenna array do not remain stationary. Hence a practical DOA algorithm must be able to track changes with a minimal number of snapshots. In this paper we describe DOA algorithms, based on a new decomposition, that are not expensive to compute or difficult to update. The algorithms are compared with algorithms based on the singular value decomposition (SVD). URL: ftp://thales.cs.umd.edu/pub/reports/geptmc.dvi Author: G. W. Stewart Title: "Gaussian Elimination, Perturbation Theory and Markov Chains" Reference: UMIACS-TR-92-23, CS-TR-2847, January, 1992 Abstract: The purpose of this paper is to describe the special problems that emerge when Gaussian elimination is used to determinin the steady-state vector of a Markov chain. URL: ftp://thales.cs.umd.edu/pub/reports/pmcnts.dvi Author: G. W. Stewart Title: "On the Perturbation of Markov Chains with Nearly Transient States" To Appear in Numerische Mathematik Reference: UMIACS-TR-92-14, CS-TR-2835, January 1992 Abstract: Let $A$ be an irreducible stochastic matrix of the form \[ A = \bmx{cc} A_{11} & E_{12} \\ A_{21} & A_{22} \emx. \] If $E_{22}$ were zero, the states corresponding to $A_{22}$ would be transient in the sense that if the steady state vector $y\trp$ is partitioned conformally in the form $(y_1\trp \; y_2\trp)$ then $y_2\trp = 0$. If $E_{22}$ is small, then $y_2\trp$ will be small, and the states are said to be nearly transient. It this paper it is shown that small relative perturbations in $A_{11}$, $A_{21}$, and $A_{22}$, though potentially larger than $y_2\trp$, induce only small relative perturbations in $y_2\trp$. URL: ftp://thales.cs.umd.edu/pub/reports/plcqf.dvi Author: G. W. Stewart Title: "On the Perturbation of LU, Cholesky, and QR Factorizations" Reference: UMIACS-TR-92-24, CS-TR-2848, February 1992 To appear in SIMAX Abstract: In this paper error bounds are derived for a first order expansion of the LU~factorization of a perturbation of the identity. The results are applied to obtain perturbation expansions of the LU, Cholesky, and QR~factorizations. URL: ftp://thales.cs.umd.edu/pub/reports/ehsvd.dvi Author: G. W. Stewart Title: "On the Early History of the Singular Value Decomposition" Reference: UMIACS-TR-92-31, CS-TR-2855, March 1992 Abstract: This paper surveys the contributions of five mathematicians\,---\,Eugenio Beltrami (1835--1899), Camille Jordan (1838--1921), James Joseph Sylvester (1814--1897), Erhard Schmidt (1876--1959), and Hermann Weyl (1885--1955)\,---\,who were responsible for establishing the existence of the singular value decomposition and developing its theory. URL: ftp://thales.cs.umd.edu/pub/reports/nwsleamls.dvi Author: C. G. Jacobi (Translated by G. W. Stewart) Title: On a New Way of Solving the Linear Equations that Arise in the Method of Least Squares Reference: UMIACS TR-92-42, CS-TR-2877 Abstract: This report contains a translation of a paper of C. G. J. Jacobi, ``Ueber eine neue Aufl\"osungsart der bei der Methode der kleinsten Quadrate vorkommenden line\"aren Gleichungen,'' which appeared in {\it Astronomische Nachrichten\/} {\bf 22} (1845). In the paper Jacobi shows how to use rotations to increase the diagonal dominance of symmetric linear systems, which he then solves by what we today call the point Jacobi method. This preconditioner is none other than Jacobi's method for diagonalizing a symmetric matrix. Although Jacobi points out his method can be used to find eigenvalues, he reserves a fuller exposition for a later paper [Journal f\"ur die reine und angewandte Mathematik, {\bf 30} (1846), 51--s94], which is now generally cited as the source of the method. A variant for unsymmetric equations is also considered. URL: ftp://thales.cs.umd.edu/pub/reports/so.dvi Author: Alan Edelman and G. W. Stewart Title: "Scaling for Orthogonality" Reference: UMIACS-TR-92-43, CS-TR-2878, April 1992 Abstract: In updating algorthms where orthogonal transformations are accumulated, it is important to preserve the orthogonality of the product in the presence of rounding error. Moonen, Van~Dooren, and Vandewalle have pointed out that simply normalizing the columns of the product tends to preserve orthogonality\,---\,though not, as DeGroat points out, to working precision. In this note we give an analysis of the phenomenon. URL: ftp://thales.cs.umd.edu/pub/reports/uurvdp.dvi Author: G. W. Stewart Title: "Updating URV Decompositions in Parallel" Reference: UMIACS-TR-92-44, CS-TR-2880, April 1992 Abstract: A URV~decomposition of a matrix is a factorization of the matrix into the product of a unitary matrix (U), an upper triangular matrix (R), and another unitary matrix (V). In an earlier paper [UMIACS-TR-90-86] it was shown how to update a URV~decomposition in such a way that it reveals the effective rank of the matrix. It was also argued that the updating procedure could be implemented in parallel on a linear array of processors; however, no specific algorithms were given. This paper gives a detailed implementation of the updating procedure. URL: ftp://thales.cs.umd.edu/pub/reports/ngse.dvi Author: G. W. Stewart Title: "Note on a Generalized Sylvester Equation" Reference: UMIACS-TR-92-59, CS-TR-2906, April 1992 Abstract: In this note we show how to compute the minimum-norm, least squares solution of the generalized Sylvester equation \[ AX + YB = C, \] URL: ftp://thales.cs.umd.edu/pub/reports/srrit.dvi Author: Z. Bai and G. W. Stewart Title: SRRIT\,---\,A FORTRAN Subroutine to Calculate the Dominant Invariant Subspace of a Nonsymmetric Matrix Reference: UMIACS TR--92--61, CS TR--2908, May, 1992 Abstract: {\sl SRRIT} is a FORTRAN program to calculate an approximate orthonormal basis for a dominant invariant subspace of a real matrix $A$ by the method of simultaneous iteration \cite{stewart76a}. Specifically, given an integer $m$, {\sl SRRIT} attempts to compute a matrix $Q$ with $m$ orthonormal columns and real quasi-triangular matrix $T$ of order $m$ such that the equation \[ AQ = QT \] is satisfied up to a tolerance specified by the user. The eigenvalues of $T$ are approximations to the $m$ largest eigenvalues of $A$, and the columns of $Q$ span the invariant subspace corresponding to those eigenvalues. {\sl SRRIT} references $A$ only through a user provided subroutine to form the product $AQ$; hence it is suitable for large sparse problems. URL: ftp://thales.cs.umd.edu/pub/reports/drpe.dvi Author: G. W. Stewart Title: Determining Rank in the Presence of Error Reference: UMIACS TR--92--108, CS TR--2972, October 1992 Abstract: The problem of determining rank in the presence of error occurs in a number of applications. The usual approach is to compute a rank-revealing decomposition and make a decision about the rank by examining the small elements of the decomposition. In this paper we look at three commonly use decompositions: the singular value decomposition, the pivoted QR decomposition, and the URV decomposition. URL: ftp://thales.cs.umd.edu/pub/reports/sbhs.dvi Author: G. W. Stewart Title: On the Solution of Block Hessenberg Systems Reference: UMIACS TR--92--109, CS TR--2973, October 1992 Abstract: This paper describes a divide-and-conquer strategy for solving block Hessenberg systems. For dense matrices the method is a little more efficient than Gaussian elimination; however, because it works almost entirely with the original blocks, it is be much more efficient for sparse matrices or matrices whose blocks can be generated on the fly. For Toeplitz matrices, the algorithm can be combined with the fast Fourier transform to give a new superfast algorithm. URL: ftp://thales.cs.umd.edu/pub/reports/imase.dvi Author: E. Schroeder Translated by G. W. Stewart Title: On Infinitely Many Algorithms for Solving Equations Reference: UMIACS TR--92--121, CS TR--2990, November 1992 Abstract: This report contains a translation of ``Ueber unendlich viele Algorithmen zur Aufl\"osung der Gleichungen,'' a paper by E. Schr\"oder which appeared in {\it Mathematische Annalen\/} in 1870. URL: ftp://thales.cs.umd.edu/pub/reports/cmi.dvi Author: G. W. Stewart Title: On the Convergence of Multipoint Iterations Reference: UMIACS TR--93--10, CS TR--3030, February 1993 Abstract: This note gives a new convergence proof for iterations based on multipoint formulas. It rests on the very general assumption that if the desired fixed point appears as an argument in the formula then the the formula returns the fixed point. URL: ftp://thales.cs.umd.edu/pub/reports/ssud.dvi Author: G. W. Stewart Title: On the Stability of Sequential Updates and Downdates Reference: UMIACS TR-94-30, CS-TR-3238, Abstract: The updating and downdating of QR~decompositions has important applications in a number of areas. There is essentially one standard updating algorithm, based on plane rotations, which is backwards stable. Three downdating algorithms have been treated in the literature: the LINPACK algorithm, the method of hyperbolic transformations, and Chambers' algorithm. Although none of these algorithms is backwards stable, the first and third satisfy a relational stability condition. In this paper, it is shown that relational stability extends to a sequence of updates and downdates. In consequence, other things being equal, if the final decomposition in the sequence is well conditioned, it will be accurately computed, even though intermediate decompositions may be almost completely inaccurate. These results are also applied to the two-sided orthogonal decompositions, such as the URV decomposition. URL: ftp://thales.cs.umd.edu/pub/reports/gqrdpm.dvi Author: G. W. Stewart Title: On Graded QR Decompositions of Products of Matrices Reference: UMIACS TR-94-53, CS-TR-3263, Abstract: This paper is concerned with the singular values and vectors of a product $M_{m}=A_{1}A_{2}\cdots A_{m}$ of matrices of order $n$. The chief difficulty with computing them from directly from $M_{m}$ is that with increasing $m$ the ratio of the small to the large singular values of $M_{m}$ may fall below the rounding unit, so that the former are computed inaccurately. The solution proposed here is to compute recursively the factorization $M_{m} = QRP\trp$, where $Q$ is orthogonal, $R$ is a graded upper triangular, and $P\trp$ is a permutation. URL: ftp://thales.cs.umd.edu/pub/reports/bhess.dvi Author: G. W. Stewart Title: Implementing an Algorithm for Solving Block Hessenberg Systems Reference: UMIACS TR-94-70, CS-TR-3295, Related-Resources: Postscript file and programs Abstract: This paper describes the implementation of a recursive descent method for solving block Hessenberg systems. Although the algorithm is conceptually simple, its implementation in C (a natural choice of language given the recursive nature of the algorithm and its data) is nontrivial. Particularly important is the balance between ease of use, computational efficiency, and flexibility. URL: ftp://thales.cs.umd.edu/reports/mcst.dvi Author: G. W. Stewart Title: On Markov Chains with Sluggish Transients Reference: UMIACS TR-94-77, CS-TR-3306, Abstract: In this note it is shown how to construct a Markov chain whose subdominant eigenvalue does not predict the decay of its transient. URL: ftp://thales.cs.umd.edu/reports/gsge.dvi Author: G. W. Stewart Title: Gauss, Statistics, and Gaussian Elimination Reference: UMIACS TR-94-78, CS-TR-3307 Abstract: This report gives a historical survey of Gauss's work on the solution of linear systems.