Matrix computations in signal processing and Markov chains.

摘要

In this dissertation, we consider two applications of matrix computations: the use of the rank-revealing URV decomposition in signal processing and a block-GTH algorithm for finding the stationary vector of a Markov chain.;Many subspace tracking and rank estimation problems in signal processing can be solved by using matrix eigendecomposition and singular value decomposition. Unfortunately, both methods have a high computation burden in updating incoming data. We investigate the use of the rank-revealing URV decomposition applied to the ESPRIT algorithm that determines the direction-of-arrival (DOA) of narrow-band signals impinging on an array of sensors.;For subspace tracking problems, we study the perturbation of the estimated invariant subspaces determined by the rank-revealing URV decomposition. An error analysis is given to guide the choice of a tolerance for rank determination. For data sampled by rectangular windowing, we design a new downdating URV algorithm and show its relational stability. Experimental results show that the URV-based algorithms are effective for time-varying DOA estimation and are more efficient than SVD-based algorithms.;The GTH algorithm is a direct method to find the stationary distribution of a finite-state, discrete time, irreducible Markov chain. It is a variant to Gaussian elimination. In order to get more efficient implementation on high performance architectures, we design a block-form of the GTH algorithm. Both block-GTH and GTH compute a UL decomposition by eliminating successive states recursively. However, the block-GTH algorithm can eliminate more than one state per step.;We develop two types of block-GTH algorithms for a variety of computers. We analyze entry-wise rounding error for both of the block-GTH algorithms and the GTH algorithm. We implement the block-GTH algorithms using the level-3 basic linear algebra subroutines from the BLAS collection. Based on the cache memory size, problem size, and columnwise storage organization, we predict an optimal block size for the type II block-GTH algorithm for workstations. For parallel implementation, we implement the type I block-GTH algorithm in an SIMD code that is performed on the CM-5. Numerical experiments are presented to demonstrate the efficiency of the block-GTH algorithm on vector pipeline machines, workstations with cache memory, and parallel processors.