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.