Dianne O'leary - US grants

9401151 Davis This award provides support for the acquisition of a distributed memory parallel computer together with support hardware for scientific visualization and storage of large image databases. The proposed system will be an experimental facility designed as a testbed for operating system and algorithm development, and will consequently run a wide range of experimental operating systems. The research topics to be explored span a broad range of applied research in high performance computing in three general categories: programming tools for HPC systems, parallel algorithms for scientific computing, and symbolic coding. A key component of the research program is the development of scalable parallel data structure and algorithms for the representation and analysis of global data sets arising from environmental science problems.

This project concerns two topics in numerical linear algebra: the numerical treatment of Markov chains and regularization of ill-posed linear systems. The topics share common features: singular or nearly singular matrices; use of iterative methods for large-scale problems; problems in matrix perturbation; and connections with infinite dimensional problems. The computation of the steady-state vector of a Markov chain as well as other important quantities are being investigated. In particular, algorithms are being developed and analyzed for calculating mean first passage times and for computing the recurrence matrix of M/G/1 type queues. In addition aggregation methods with overlapping blocks and the behavior of chains with sluggish transients are being considered. When ill-posed problems are discretized they result in ill-conditioned linear systems which must be regularized to yield accurate solutions. There are three main goals in this work. The first is to prove the folk theorem that if the components of the data vector with respect to the singular vectors decay sufficiently fast then the conjugate gradient iteration will produce a regularizing set of solutions. The second is to treat problems with errors in the matrix by a regularized total-least-squares approach. The third is to further preconditioning strategies for iterative solution methods.

This work concerns two topics in numerical linear algebra: 1) Regularization of ill-posed linear systems; 2) Solution of large, sparse eigenvalue problems. These topics share common features: a wide range of application problems; the use of iterative methods for large-scale problems; and interesting problems in matrix perturbation theory. When continuous ill-posed problems are discretized they result in ill-conditioned linear systems which must be regularized to yield accurate solutions. This part of the work has several goals. The first is to prove the folk theorem that if the components of the data vector with respect to the singular vectors of the matrix decay sufficiently fast then the conjugate gradient iteration will produce a regularizing set of solution vectors. The second is to compare the numerous formulations of discrete ill-posed problems to see which are most effective. The third is to further develop preconditioners to speed convergence of solution algorithms. The fourth is to improve data-gathering techniques so that the attainable accuracy from imaging is better, thus, for example, revealing smaller tumors or more information about distant stars. Over the past decade many new algorithms for finding clusters of eigenvalues of large matrices have been proposed. Although the effectiveness of some of these algorithms has been demonstrated empirically, analytic results are sparse. Fortunately, a large number of these methods share a common framework, so that it is possible to develop analytic tools that are widely applicable. As a start toward this goal, attention is focused on a new, promising method---singular vector enhancement---that fits in the framework. A preliminary analysis of a special case has already yielded valuable results on the relation of eigenvalues and singular values. The results of this project will impact the solution of ill-posed problems such as medical image enhancement, astronomical data processing, nondestructive testing, and spectroscopy, as well as eigenvalue problems arising in systems modeling (Markov chains), computational chemistry, and structural analysis.

Elman

This project concerns the development, analysis and testing of techniques
of numerical linear and nonlinear algebra for solving systems of equations
arising from discretization of a collection of partial differential equations.
The emphasis will be on preconditioning strategies and their combination
with Krylov subspace iterative methods for linear and nonlinear systems.
These ideas will be applied to several examples of differential equations,
primarily coming from models of fluid dynamics. Our focus will be on two
types of problems, the saddle point problems produced by direct discretization
of the primitive formulation of the incompressible Navier-Stokes equations,
and the convection-diffusion equation. These have been chosen because they
are used in numerous engineering models of fluid flow, and because they contain
challenging mathematical and computational qualities that make them difficult
to solve. In particular, accurate discretization in two and three dimensions
leads to large sparse systems of algebraic equations that are nonsymmetric,
and for the first problem, nonlinear and indefinite. In addition, they have
associated with them fundamental parameters such as Reynolds numbers and
discretization mesh widths that, for the solution of problems of practical
interest, cause many algorithms to converge slowly and require large-scale
systems to attain accuracy. Our goals are to extend and analyze certain
preconditioning techniques designed for saddle point problems. Plans include
demonstration of the effectiveness of these preconditioners for general mixed
finite element discretizations, development of rigorous mathematical techniques
for analyzing convergence, demonstration of their usefulness in realistic
settings involving general meshes and domains, and incorporation of fast
algorithms for the convection-diffusion equation into the solution process.

The purpose of developing computational algorithms is to enable the
efficient numerical solution of differential equations used in mathematical
modelling. The use of such models is becoming an increasingly important
component in manufacturing and design (for example, of aerospace vehicles,
automobiles, cooling devices for nuclear devices) and in enhancing our
understanding of critical natural phenomena (for example, blood flows and
dispersal of environmental pollutants). Understanding these phenomena
through purely experimental techniques is prohibitively expensive or
impossible, whereas the use of mathematical models introduces a basic
understanding of the physics by providing approximations to quantities
such as flow rates and pressures. This leads to the identification of
promising design features, such as wing shape in airplane manufacturing.
(For example, many of the design decisions for the Boeing 777 jet were made
using computational studies.) Accurate solution of the mathematical models
is only feasible, however, if reliable and fast solution algorithms are
available. The goal of this project is to develop such algorithms.

9970831
O'Leary

This Americas Program award will jointly fund, together with the NSF Division of Mathematical Sciences, the attendance of 10 junior faculty and graduate students from the United States to the Householder Symposium XIV on Numerical Algebra to be held June 14-18, 1999 in Whistler, British Columbia. The activity is being organized by the Householder Program Committee, together with the SIAM Activity Group in Linear Algebra.

This multi-national symposium is held once every three years to review advances in numerical algebra and to foster new collaborative efforts. The meeting brings together theoreticians, numerical analysts, and application researchers from all over the world. Selection of US junior faculty and students will be made by soliciting applications through electronic bulletin board announcements and advertisements in cognizant journals.
***

This proposal concerns new improvements that have the potential to achieve significant speed-up for the fast multipole method (FMM) for use in solving the Helmholtz and other problems used to model phenomena encountered in electromagnetics, acoustics, biology etc. Solving larger problems holds promise for better design on the one hand, and elucidation of new physics/biology on the other. Discretizations of the partial differential equations arising from these equations yield large systems of equations for which both direct and iterative solution techniques are expensive.

The introduction by Rokhlin & Greengard of the FMM generated tremendous interest in the scientific computing community, as it demonstrated a way to generate structure and achieve fast solution of equations without relying on the discretization. Despite its promise, the algorithm has not achieved widespread implementation for many practically important problems that could use the promised speedups. Some researchers have reported that the approximate integrals both make implementation difficult, and in practice they have been shown to introduce stability problems. We have recently derived exact expressions for the translation and rotation of multipole solutions of the Helmholtz equation, which enable fast computation via simple recursions. Further we have obtained very promising results on the properties of the translation operators that enable creation of very tight error bounds. Our translations have the same asymptotic complexity as the standard integral expressions, but with much smaller coefficients. We have also found that the translation operator can be decomposed into the product of sparse recurrence matrices and this can be the basis for a T(p2) algorithm, which we propose to pursue. Based on these expressions, we will develop software for solution of different problems using the FMM. To be useful in pushing ahead the information technology revolution our software will be well documented and published in accessible peer reviewed forums. Such availability will act to improve adoption by large numbers of practitioners.

ABSTRACT
0204084
Gilbert Stewart
University of Maryland College Park

Krylov sequence methods are widely used in the solution of large eigenproblems (e.g., the Lanczos and Arnoldi methods) and the solution of large linear systems (e.g., the conjugate gradient method and GMRES). In their ordinary applications these methods are well understood and have a firm theoretical basis. In more exotic applications, however, the theory and practice are not as advanced. This proposal in concerned with
three of these applications. Residual Krylov methods. The property of being a Krylov sequence is very sensitive to error. A single error toward the beginning of the sequence causes permanent loss of
accuracy in the approximations to eigenvectors in the Krylov subspace. This has the consequence that when shift-and-invert techniques are used to enhance the spectrum of a matrix, the resulting linear systems must be solved to full accuracy at each step of the process. It turns out, however, that if the sequence is extended using the residual for a targeted eigenvector, the sequence converges to that vector even when the shift-and-
invert equations are solved inaccurately. The practical consequences of this observation, which needs new theory to support it, promises to be great.

Researchers at the University of Maryland plan to build a high-performance computing and visualization cluster taking advantage of synergies afforded by coupling central processing units (CPUs), graphics processing units (GPUs), displays, and storage. The infrastructure will be used to support a broad program of computing research that will revolve around understanding, augmenting, and leveraging the power of heterogeneous vector computing enabled by GPU co-processors. The driving force here is the availability of cheap, powerful, and programmable graphics processing units (GPUs) through their commercialization in interactive 3D graphics applications, including interactive games. The CPU-GPU coupled cluster will enable the pursuit of several new research directions in computing, as well as enable a better understanding and fast solutions to several existing interdisciplinary problems through a visualization-assisted computational steering environment. In addition, it will foster research to cast several problems into a better spot on the price-performance curve.

Intellectual Impact: The proposed research that will use this cluster falls into several broad interdisciplinary computing areas. The researchers plan to explore visualization of large datasets and algorithms for parallel rendering. In high-performance scientific computing we plan to develop and analyze efficient algorithms for use with complex systems when uncertainty is included in models. The researchers plan to use the cluster for several applications in computational biology, including computational modeling and visualization of proteins, conformational steering in protein structure prediction, folding, and drug design, large-scale phylogeny visualization, and sequence alignment.

The researchers also plan to use the cluster for applications in real-time computer vision, real-time 3D virtual audio, and for efficient compilation of signal processing algorithms.

Broader Impact: An important aspect of this research is to ensure a high impact of the cluster towards educational and outreach goals. The investigators plan to enrich their current coursework with research results obtained on the cluster. The coupled cluster with a large-area high-resolution display screen will serve as a valuable resource to present, interactively explore, evaluate, and validate the ongoing research in visualization, vision, scientific computing, human-computer interfaces, and computational biology with active participation of graduate as well as undergraduate students.

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.

The underlying problem considered here is the solution of a discretization of an integral equation of the first kind. Even with complete information, the problem is ill-posed, in the sense that small changes in the data can make arbitrarily large changes in the solution. Unfortunately, complete information is not available in applications such as medical imaging (CAT, MRI), astronomical imaging, spectroscopy, or non-destructive testing for cracks in a structure, and the problem becomes a discretized version of the ill-posed problem. Solution algorithms regularize the problem, replacing the ill-posed problem by one that is well-posed in order to compute a solution. The basic idea behind all regularization methods is to impose additional constraints on the model in order to make the problem well-posed. There are two very different kinds of constraints, which are typically not well differentiated: data constraints that are guaranteed to hold with 100% certainty, and bias constraints, arising from what the observer expects to see. If the observer is wrong about the bias constraints, then the solution algorithm might produce a solution that is is quite believable but very misleading. This work focuses on three major open questions in the solution to ill-posed problems: development of diagnostics to validate candidate solutions and identify bias; development of improved algorithms that produce validated solutions through discovery of new filtering methods, reliable choice of parameters, better understanding of Krylov methods, and unification of algorithms for data least squares, least squares, and total least squares problems; and computation of confidence bounds for the solutions, making use of data constraints (e.g., nonnegativity).

The broader impact of the work arises from its potential to produce more reliable images for medical applications (CAT, MRI, etc.), astronomy, spectroscopy, locating oil reservoirs, testing structures for hidden cracks, and other applications. The techniques involve effective use of extra information known about the image (for example, that each pixel value is nonnegative) in order to constrain the solution image. The focus is on improved methods and on more precise knowledge of the solution through the construction of statistical confidence intervals. The work also has great value in education. A graduate course in advanced numerical linear algebra will be offered that will include a section on discrete ill-posed problems. This work will be presented at Maryland's SPIRAL summer program for undergraduate students from Historically Black Colleges and Universities, since it provides a visually-appealing and easily-explained introduction to ill-posed problems.