Scientific Computing Group
Numerical analysis and scientific computing have a long history in our department, dating from the work of Werner Rheinboldt and colleagues in the 1970s on the numerical solution of nonlinear equations. The group has always had close ties with numerical analysts in the Mathematics Department, and our students are drawn from the Applied Mathematics and Scientific Computing Program as well as the Computer Science Department. Alumni include Xiaobai Sun (Duke), Robert van de Geijn (Texas), Yuan-Jye Jason Wu (Boeing), and Tamara Kolda (Sandia). Four faculty members currently work in the area of numerical analysis and scientific computing:
Our research ranges from answering basic questions about numerical algorithms, to applying numerical techniques to a diverse set of applications. We give brief summaries of some of our work below.
Matrix Eigenvalue Problems Eigenvalue analysis is used, for example, to determine resonant frequencies of musical instruments, stability of control systems for automobile braking, and flight characteristics of airplanes. Our work has produced fundamental understanding of the effects of perturbations on the eigenvalues and eigenvectors of matrices. Most recently, our focus has been on development of Eigentest, a test matrix generator for large-scale eigenproblems, and a residual Arnoldi method for solving these problems.
Solution of Large Linear Systems of Equations In one study of numerical software, it was determined that 90% of the subroutine calls accessed solvers for linear systems of equations. This is an important problem in its own right, but also a component of algorithms for more complex problems such as solving nonlinear equations and partial differential equations, so efficiency is key. We study iterative methods such as GMRES and the conjugate gradient algorithm for solving large linear systems. In particular, we develop preconditioning techniques to speed the solution of certain problems arising in the solution of differential equations.
The Fast Multipole Algorithm and Applications The motivation for fast multipole algorithms is to develop an efficient algorithm for computing the potential function for a set of charged particles. Dense matrices derived from point distributions of data arise commonly in applications. The fast multipole method can be used to speed up matrix vector products and iterative solvers involving matrices with such structure. We are exploring the application of fast multipole algorithms to diverse problems including the biharmonic equation, Laplace equation, the Helmholtz equation, radial basis function fitting, Maxwells equations, and to various kernels that arise in computational machine learning (Gaussian, logistic function, the logit kernel). Research is also focused on developing different data structures, other than the standard ones used in the FMM, and on the development of preconditioners that can be easily implemented in the context of the FMM.
Optimization Numerical optimization methods are used to find the fastest, or least expensive, or most lowest energy solutions to problems in areas ranging from finance to protein folding. Some of our research focuses on the efficient use of linear algebra in optimization; some exploits structure in the optimization problem in order to devise more efficient algorithms. Recent work concerns the solution of conic convex optimization problems.
The Solution of the Convection-Diffusion Equation Models of convection and diffusion are among the most widespread in science and engineering, with applications such as semiconductor modeling and transport of pollutants or heated fluids. Discretization and numerical solution of such problems is complicated by the presence of steep gradients (boundary layers) in parts of the solution. We have developed efficient solution strategies based on multigrid and have analyzed the effects of stabilizing discretization strategies on accuracy an on performance of numerical solution algorithms.
Solution of Ill-Posed Problems & Image Deblurring In ill-posed problems, small changes in the data can cause arbitrarily large changes in the results. Although it would be nice to avoid such problems, they have important applications in medicine (computerized tomography), remote sensing (determining whether a nuclear reactor has a crack), and astronomy (image processing). Our work has focused on studying the characteristics of solutions produced by various regularization methods, especially iterative methods for large problems. We have proposed efficient numerical algorithms for image deblurring.
Solution Algorithms for Models of Incompressible Flows The Navier-Stokes equations are of fundamental importance for modeling of incompressible flows. Discretization leads to a coupled system of nonlinear algebraic equations for velocities and pressures. By taking advantage of the special structure of the discrete problem and building on algorithmic advances achieved for individual scalar subproblems, we have developed new solution algorithms that are generally applicable to steady-state and evolutionary problems and display convergence rates largely insensitive to fundamental problem parameters such as discretization mesh size and Reynolds number. Ongoing research in this direction includes the extension of these ideas to solve the eigenvalue probRamanilems that arise from stability analysis of steady-state solutions.
Computing with Uncertainty Traditional methods of mathematical modeling depend on the assumption that components of models such as diffusion coefficients or boundary conditions are known. In practice, however, such quantities may not be known with certainty and instead they may be represented as random functions, that is, a random variable for each point in the physical domain. An approach for performing computational studies of models of this type is the stochastic finite element method, which is a generalization of finite element discretization for deterministic problems designed to handle problems posed with uncertainty. We have explored this methodology to model elliptic partial differential equations when some terms in the problem are not known with certainty, and we have developed efficient algorithms for solving the associated discrete problems.
Information Retrieval In spite of the fact that more than 600,000 medical papers are published annually, physicians are expected to be familiar with current literature ranging from the common cold to cancer. Researchers in a variety of fields face similar challenges. The aim of our research in information retrieval is to develop tools, based on linear algebra and optimization, that retrieve documents that are relevant to a users query and provide contextual summaries of these documents.
Medical and Biological Applications The structure of a protein provides critical information in determining its function. Our recent work includes development of a new algorithm for determining the shape of a protein and a fast screening algorithm for finding proteins whose structure is expected to be similar to one presented for classification.
Quantum Computing Quantum computers may offer a way to solve certain problems that are larger and more complex than any that can be solved on conventional computers. One way to view a quantum computer is as a machine that multiplies a vector by a unitary matrix. Our work in this area focuses on several questions relevant to the decomposition of the unitary matrix into quantum "gates" that can actually be made to work.
Scientific Computing on Graphics/Game Architectures Architectures such as Graphical Processing Units (GPUs) or Cell Processors are application specific and have seen a tremendous improvement in their capabilities over the past decade, while at the same time being relatively inexpensive. While their primary use is for graphics and gaming, our research attempts to use them in an heterogeneous environment including these processors and CPUs to speed up algorithms in linear algebra, interior point methods, image processing, audio processing, and the fast multipole method.
