Tech Reports in Computer Science and Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/5
The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu
Browse
69 results
Search Results
Item Analysis of the Residual Arnoldi Method(2007-10-15) Lee, Che-Rung; Stewart, G. W.The Arnoldi method generates a nested squences of orthonormal bases $U_{1},U_{2}, \ldots$ by orthonormalizing $Au_{k}$ against $U_{k}$. Frequently these bases contain increasingly accurate approximations of eigenparis from the periphery of the spectrum of $A$. However, the convergence of these approximations stagnates if $u_{k}$ is contaminated by error. It has been observed that if one chooses a Rayleigh--Ritz approximation $(\mu_{k}, z_{k})$ to a chosen target eigenpair $(\lambda, x)$ and orthonormalizes the residual $Az_{k - }\mu_{k} z_{k}$, the approximations to $x$ (but not the other eigenvectors) continue to converge, even when the residual is contaminated by error. The same is true of the shift-invert variant of Arnoldi's method. In this paper we give a mathematical analysis of these new methods.Item A Residual Inverse Power Method(2007-02) Stewart, G. W.The inverse power method involves solving shifted equations of the form $(A -\sigma I)v = u$. This paper describes a variant method in which shifted equations may be solved to a fixed reduced accuracy without affecting convergence. The idea is to alter the right-hand side to produce a correction step to be added to the current approximations. The digits of this step divide into two parts: leading digits that correct the solution and trailing garbage. Hence the step can be be evaluated to a reduced accuracy corresponding to the correcting digits. The cost is an additional multiplication by $A$ at each step to generate the right-hand side. Analysis and experiments show that the method is suitable for normal and mildly nonnormal problems.Item EIGENTEST: A Test Matrix Generator for Large-Scale Eigenproblems(2006-02-13T19:44:17Z) Lee, Che Rung; Stewart, G. W.Eigentest is a package that produces real test matrices with known eigensystems. A test matrix, called an eigenmat, is generated in a factored form, in which the user can specify the eigenvalues and has some control over the condition of the eigenvalues and eigenvectors. An eigenmat A of order n requires only O(n) storage for its representation. Auxiliary programs permit the computation of (A - sI)*b, (A - sI)'*b, inv(A - sI)*b, and inv(A - sI)*b in O(n) operations. A special routine computes specified eigenvectors of an eigenmat and the condition of its eigenvalue. Thus eigenmats are suitable for testing algorithms based on Krylov sequences, as well as others based on matrix-vector products. This paper introduces the eigenmat and describes implementations in Fortran~77, Fortran~95, C, and Matlab.Item The Gram-Schmidt Algorithm and Its Variations(2006-01-13T21:08:09Z) Stewart, G. W.The Gram--Schmidt algorithm is a widely used method for orthogonalizing a sequence of vectors. It comes in two forms: classical Gram--Schmidt and modified Gram--Schmidt, each of whose operations can be ordered in different ways. This expository paper gives a systematic treatment of this confusing variety of algorithms. It also treats the numerical issue of loss of orthogonality and reorthogonalization as well as the implementation of column pivoting.Item Error Analysis of the Quasi-Gram--Schmidt Algorithm(2004-04-19) Stewart, G. W.Let the $n{\times}p$ $(n\geq p)$ matrix $X$ have the QR~factorization $X = QR$, where $R$ is an upper triangular matrix of order $p$ and $Q$ is orthonormal. This widely used decomposition has the drawback that $Q$ is not generally sparse even when $X$ is. One cure is to discard $Q$ retaining only $X$ and $R$. Products like $a = Q\trp y = R\itp X\trp y$ can then be formed by computing $b = X\trp y$ and solving the system $R\trp a = b$. This approach can be used to modify the Gram--Schmidt algorithm for computing $Q$ and $R$ to compute $R$ without forming $Q$ or altering $X$. Unfortunately, this quasi-Gram--Schmidt algorithm can produce inaccurate results. In this paper it is shown that with reorthogonalization the inaccuracies are bounded under certain natural conditions. (UMIACS-TR-2004-17)Item An Elsner-Like Perturbation Theorem for Generalized Eigenvalues(2003-12-18) Stewart, G. W.In 1985 Elsner established a general bound on the distance between an eigenvalue of a matrix and the closest eigenvalue of a perturbation of that matrix. In this note, we show that a similar result holds for the generalized eigenvalue problem. UMIACS-TR-2003-116Item Building an Old-Fashioned Sparse Solver(2003-09-25) Stewart, G. W.A sparse matrix is a matrix with very few nonzero elements. Many applications in diverse fields give rise to linear systems of the form $Ax = b$, where $A$ is sparse. The problem in solving these systems is to take advantage of the preponderance of zero elements to reduce both memory use and comutation time. The purpose of this paper is to introduce students (and perhaps their teachers) to sparse matrix technology. It is impossible to treat all the techniques developed since the subject started in the 1960's. Instead, this paper constructs a sparse solver for positive definite systems that would have been state of the art around 1980, emphasizing equally theory and computational practice. It is hoped that a mastery of this material will allow the reader to study the subject independently. (UMIACS-TR-2003-95)Item Memory Leaks in Derived Types Revisited(2003-09-02) Stewart, G. W.In a note in the {\it Fortran Forum\/}, Markus describes a technique for avoiding memory leaks with derived types. In this note, we show by a simple example that this technique does not work when the object in question is a parameter in nested subprogram invocations. A fix is proposed and illustrated with code from MATRAN, a Fortran~95 package for performing matrix manipulations. (UMIACS-TR-2003-90)Item A Fortran 95 Matrix Wrapper(2003-09-02) Stewart, G. W.{\Matran} is an wrapper written in Fortran~95 that implements matrix operations and computes matrix decompositions using {\lapack} and the {\blas}. This document describes a preliminary release of {\matran}, which treats only real matrices. Its purpose is to get outside comments and suggestions before the package jells. Consequently, this documentation is slanted toward the experienced programmer familiar with both matrix computations and Fortran~90/95. User oriented documentation will accompany the final release. (UMIACS-TR-2003-89)Item On the Method of Pure Truncation for Approximating Stationary Probabilities(2003-08-01) Stewart, G. W.This paper is concerned with approximating the leading components of the stationary vector of a semi-infinite discrete markov chain. The most widely treated method extracts a leading principal submatrix from the matrix of transition probabilities, adjusts its elements so that it becomes stochastic, and takes the stationary vector of the result as the approximation. In this paper, the consequences of taking the normalized Perron vector of the unadjusted matrix as the approximation are explored. Error bounds are derived, and it is shown that the adjusted and unadjusted methods are approximations to one another. (UMIACS-TR-2003-65)