Computations with Unitary Matrices

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Project Abstract 0514213 G. W. Stewart and Dianne P. O'Leary U of Maryland College Park This work considers several computational problems associated with unitary and real orthogonal matrices. The intellectual merit of the work lies in the mathematical and algorithmic ideas. First, the investigators seek a unified view of the least squares family of solutions to data fitting problems. The purpose is to improve algorithms for solving such problems and to advance the understanding of the relationship among the various data models. The investigators have derived a common framework for least squares, data least squares, total least squares, and regularized least squares, for problems with single or multiple sets of observations. Using this, they will study the existence and uniqueness of solutions and the behavior of the solutions as parameters are varied. Efficient algorithms will be derived, both for small problems and for problems too big to be solved directly. In addition, problems that use norms other than least squares will be investigated. Second, the investigators will study sparse QR factorizations of sparse matrices into the product of an orthogonal matrix and a right-triangular matrix. The usual QR factorization is quite storage intensive, since Q typically has many more nonzeros than the original matrix. Recently one of the investigators developed an algorithm that represents the QR factors in terms of the data in the original matrix, along with a small dense matrix, thus preserving sparsity. By terminating the algorithm early, an approximate factorization can be formed to any given tolerance. The investigators will produce quality software implementations of this algorithm and test its performance on data from a variety of applications. Third, the investigators will study several unitary matrix problems arising in quantum computing. The first set of problems comes from computing quantifiers for entanglement; in particular, the goal is to compute the concurrence capacity for various operators of practical interest, including the Quantum Baker's map, by localizing the eigenvalues of certain unitary matrices or by solving an optimization problem. The second set is motivated by adiabatic quantum computing and involves perturbation analysis on various homotopies between matrices in order to understand their behavior and prove a stability property for them. Finally, the investigators will develop software for updating orthogonal matrix factorizations when rows or columns are added or deleted, either singly or in blocks (in collaboration with the LAPACK project). The broader impact of the work arises from its applications in other problem areas and in its value to education. The mathematical and computational results obtained under the first topic will impact data fitting in science and engineering. The second topic has application to problems as diverse as astronomical image compression and medical information retrieval. The third might influence the design of practical quantum computers. The fourth has application, for example, to data assimilation in signal processing. Outreach activities will include working with women and minority graduate students and developing projects for computational science education based on the research. Two students will be supported under this grant. The research will continue to be incorporated as appropriate into computational science courses and published as computational science educational projects. They will also influence a textbook on computational science to be begun next year.