Kentucky-Austria International Cooperative Research
Numerical Methods
Algebraic Multigrid
Borzi, Douglas, Haase, Langer, ZulehnerResearch Issues. Algebraic Multigrid Methods (AMG) are well established in thecomputational community for solving large sparse systems of equations. The original ideaby Ruge and Stueben consists of creating a hierarchy of coarser systems (meshes) from thegiven fine system (mesh) and applying a standard multilevel algorithm on that sequence ofsystems (meshes). This approach works well for symmetric positive definite systems and M-matrices. Much effort has been spent to widen the range of matrices and applications thatAMG can be successfully applied to. There are AMG approaches that promise to solve mostproblems (non M-matrices, non-symmetric, indefinite) occurring in practical applications,but the concepts therein are general and can be outperformed by standard and much lesscomplicated solvers for the special applications.
Related Research. Langer and Haase are the PIs for the AMG project funded by theAustrian Science Fund FWF. Therein, the AMG code PEBBLES has been developed withmore than 30 licensees worldwide and it is used in several practical applications. The codeis fast, parallelized, and is rather easy to adapt to new types of matrices and operators.Douglas is working on a theory for AMG applied to nonsymmetric matrices. That theory will widen the range of of applications where AMG can be used robustly.
Research Approach. We will investigate AMG for nonsymmetric and coupled systems of equations. The theoretical basis will show us how to choose the coarser meshes with respect to operator specifications. The validation of stability conditions on the coarser systems is of great importance in this case. The implementation of these algorithms will be done inparallel as well as in a cache aware manner to ensure that our code will be faster than anyother similar code available. Additionally, we will develop AMG for dense matrices arisingfrom boundary element discretization. Such matrices require a good strategy for sparseningthe given matrix in order to get efficient AMG solvers.
Domain Decomposition Methods and Parallelization
Douglas, Haase, LangerResearch Issues. There exists a whole bunch of parallel solvers for systems of equations.The total is dramatically reduced if one takes only into account just multigrid and AMGsolvers. Although still a considerable number of parallel solvers are available, most of themare not used at all in practical applications. The reasons for this are that either the class ofproblems is not practically relevant, the software is not easy enough to use, or the softwareis simply too slow.
Domain decomposition (DD) methods are the basic techniques for the constructionof parallel PDE solvers. The proposers have contributed to this topic during the last 15years. However, domain decomposition methods provide not only the techniques for parallelizing PDE solvers, but also for coupling different physics and even different discretization methods. Beside the use of DD techniques for parallelization, the latter topic will be a basic research issues.
Related Research. On the basis of data decomposition techniques borrowed from DDmethods the Linz group developed parallel AMG solvers and implemented these solvers inthe AMG package PEBBLES. In particular, Haase developed and implemented a theoreticalframework that allows a precise forecast which matrices and operations can be done fullyin parallel and how the communication points have to be organized for the rest of thecomputations. This strategy led to an easy parallelization of the AMG code PEBBLESand a medical source reconstruction application. Both applications have very good parallel performance.
Research Approach. We will apply Haase's parallelization strategy to our serial codes.This will be important since we want all of our codes to run efficiently on parallel computersor on a GRID. For some applications of interest, preserving a nonlinear operator's nullspace in an easy to parallelize context is essential to convincing anyone else to use ourapproach. We will also investigate how this approach can be applied to dense matrices andpatch smoothers rather than just sparse matrix problems.
Possibly the most successful DD method is the Finite Element Tearing andInterconnecting (FETI) method that was introduced by by Farhat and Roux in 1991. On the one hand, the FETI methods are now well established in hard practical applications. On the other side there is rigorous analysis of the convergence properties of FETI methods that has been developed by several author during the last four years. Langer and Steinbach have recently introduced the Boundary Element Tearing and Interconnecting (BETI) methods as boundary element counterparts of the FETI methods. In some practical important applications such as far field computations, handling of singularities and moving parts, BETI methods have some advantages over their finite element counterparts. This claim is especially true for the sparse versions of the BETI preconditioners methods. Moreover, there is a unified framework for coupling, handling, and analyzing both methods. In particular, the FETI methods can benefit from preconditioning components constructed by boundary element techniques. Moreover, sometimes it can be very useful to couple finite and boundary element methods. We will develop a FETI-BETI solver for coupled finite and and boundary element equations in different applications (potential equation, elasticity, Maxwell equations, and Stokes).
Saddle Point Problems
Douglas, Haase, Langer, ZulehnerResearch Issues. Mixed variational problems or saddle point problems result, for example, from mixed formulations of second order elliptic equations, elasticity problems, fluid mechanics problems, or Lagrange multiplier methods. Discretizing such systems leads to large systems of equations which are generically indefinite.
Roughly speaking, only one sort of variables, the primal variables, appear in a primal problem. In a mixed problem two types of variables can be distinguished: the primal variables and the dual variables. In principle, there are two different approaches for mixed problems to take advantage of the multigrid idea.
One way is to use an outer iteration, typically a Uzawa iteration, in which the new iterates for the primal and the dual variables are computed separately by solving appropriate separated problems. In order to be efficient, good preconditioners are needed for the separated problems. Multigrid methods applied to the separated problems as an inner iteration can be used to construct these efficient preconditioners. The construction of these methods rely on structural information of the separated problems.
The other way is to use multigrid methods as an outer iteration combined with appropriate smoothers (as a sort of inner iteration). Particularly simple to implement are smoothers which are based on the solutions of small local problems in a Jacobi or Gauss-Seidel manner (or by Schwarz methods).
No structural information is needed for the construction of the method, so it is a veryflexible technique. It has been widely used in practice and has shown good convergence results. However, very little is known so far about convergence and smoothing properties of the underlying iterative method. Important research issues are how to set up the local subproblems and how this effects the convergence of the multigrid methods.
Related Research. Concerning the nonsymmetric case, the smoothing property is an important part of the multigrid convergence analysis. Concerning indefinite problems, a general convergence theory was developed for Uzawa outer iterations, Efficient Uzawa smoothers for indefinite problems and smoothing properties for a class of Schwarz methods for indefinite problems have been investigated.
Research Approach. In numerical experiments so-called kernel-preserving shown very promising behavior. The construction as well as the analysis of these methods is partially understood for dual variables in discontinuous finite element spaces if a so-called kernel- preserving prolongation is used. We will investigate the construction of these methods as well as their analysis for prolongations that are more efficient but not kernel-preserving and for continuous finite element spaces. This would greatly enlarged the range of applicability of the strategies.
So far, saddle point problems, i.e., indefinite problems with two groups of variables(previously called primal and dual), were considered. Important applications require the extension to indefinite problems with three or even more groups of variables. Typical example are FETI methods for saddle point problems, BETI methods, or optimal design problems. Here we will investigate the possibilities to extend Uzawa outer iterations as well as Schwarz based smoothers to this more general class of indefinite problems.
Eigenvalues
Borzi, Douglas, Haase, LodderResearch Issues. Near-infrared (Near-IR) imaging provides a new reliable method for nondestructively mapping spatially lesions of arterial tissue and/or blood chemical constituents. Such data is expected to some day permit physicians to predict heart attacks up to a year in advance when preventive treatment is still possible. By means of a fiber- optic probe, hyperspectral data are recorded and processed to produce a very large matrix that contains space-frequency information characterizing the material under observation. It has been shown that an essential information content for postprocessing is the (complex) eigenvalue spectra of the matrix described above. To extract this information and make it available in real time, new, much faster algorithms must be developed that are suitable for supercomputing environments.
Related Research. A near-IR imaging system and parallel vector supercomputer have been used with a fiber-optic probe to produce chemical maps of the intimal surface ofliving arteries. Hyperspectral information was collected and assembled into color pictures of the lipoprotein and apolipoprotein composition of atheromas using a 3-D cellular automaton- based algorithm that operated in parallel. The nonparametric mathematics developed to identify and quantify the constituents of each voxel in the artery wall avoided the matrix factorizations that generate excess error in other pattern recognition methods and permit analysis in a wavelength space of over 1000 dimensions using fewer than 100calibration samples. A surface feature resolution of 5.5 micrometers and depth resolution of micrometers were achieved with the system. Data from the fiber optics confirmed the injury hypothesis of lesion formation in the animal subjects and the differing roles of HDL and LDL in cholesterol transport. In clinical studies, approximately half of human arteriallesions appear fibrous and contain little or no lipid. As such, these lesions would not be expected to regress in response to cholesterol-lowering agents such as one of the statin drugs. More recently, collagen and elastin have been analyzed in arterial tissue. In this study, near-IR spectrometry and principal component regression were used to determine collagen and elastin in mouse aortas, which are similar in side to human coronary vessel branches. Collagen and elastin are the major components of the fibrous cap of atheromas. When the collagen and elastin degrade and the cap thins, it can rupture, leading to sudden cardiac death. A fiber-optic probe capable of determining cap thickness and collagen and elastin content appears able to predict cap failure. In separate funded trials, identification of lesion types in vivo is being tested to enhance the efficacy of treatment programs.
An efficient eigensolver having optimal computational complexity, which is based on the algebraic multigrid (AMG) strategy and combines a FAS-AMG method with orthogonalization and nested iteration techniques. This algorithm is ableto solve for the whole spectrum of (possibly multiple) eigenvalues. Numerical results demonstrate both high efficiency and robustness of this new AMG eigensolver.
Research Approach. The required post-processing in real time as described above can be boosted by using the fast AMG approach. The present code is designed to solve for real eigenvalues and runs on sequential machines. Therefore two development steps are required. First, to extend the AMG solution process to compute complex eigenvalues. Second, to develop a parallel version of the AMG code to run on parallel supercomputer or a sufficiently large PC cluster.
Constrained Optimization in Applications
Borzi, Douglas, Haase, Lodder, ZulehnerResearch Issues. Control of time dependent nonlinear reaction-diffusion systems is required in many application areas. Reaction-diffusion systems are an essential in gredientin the modeling of chemical reaction processes, in the description of time evolution of ecological and biological systems, and coupled with Navier-Stokes equations they enter into the simulation of chemical transport phenomena and flame propagation problems.
Control of reaction-diffusion systems is the ultimate aim in biomedical and combustion applications where control is utilized on living or chemical systems to reach a desired configuration.
The U.S. Food and Drug Administration (FDA) has noted that U.S. drug products are of generally high quality, but there is an increasing trend toward manufacturing related problems that lead to recalls, disruption of manufacturing operations, and loss of availability of essential drugs. Low manufacturing process efficiency has also led to increased cost of drugs and a burden on society. Emphasis on cGMP rules (current good manufacturing practice) as the means of controlling drug quality has led to reluctance among companies to innovate in the manufacturing sector. Such problems have led the FDA to conclude that a new scientific understanding of the drug production process achieved through the use of new sensing technologies and simulations can provide science-based approaches to the regulation of drug quality, thereby alleviating these problems. Process analytical technologies (PAT) like near- infrared (NIR) spectroscopy and process simulations have been selected as the model for the U.S. to use in shifting successfully from empirical standards like cGMP to science-based standards for achieving manufacturing quality. In many cases, however, the science is still lacking.
Related Research. The efficient numerical solution of optimal control problems related to explosive combustion phenomena has been studied. This research is continued where new fast and robust parabolic multigrid methods for the control of reaction diffusion processes are presented. It is demonstrated that the resulting schemes have optimal computational complexity and that they are robust with respect to choices of the optimization weights. Algebraic multigrid solvers are presented that solve optimality systems on complex 3D domains using various discretizations. The numerical simulation of reaction-diffusion systems that model chemical turbulence is considered.
Dissolution-standard calibrator tablets (prednisone) produced over the past few decades have not always worked as well as they should. New calibration standards must be designed that will indicate whether a pharmaceutical company's dissolution apparatus is working acceptably. Tablets that do not dissolve as they should can be dangerous when the tablets contain drugs to prevent, for example, seizures or control blood pressure. PAT must be incorporated into this new calibrator tablet design to satisfy the FDA mandate.
Research Approach. Complex biological and chemical systems are characterized by many components reacting together and diffusing in space. To solve such large systems of reaction diffusion equations on space-time domains in an accurate way, large computational capabilities are required. We will further develop the methods. We will also consider an appropriate parallelization methodology for efficient and robust space-time computation.
We will also investigate new formulations of optimal control problems appropriate for the control of chaotic systems. The resulting schemes provide the framework for efficient and robust control of reaction-diffusion-transport phenomena.
For the FDA related problem, we will use physics, pharmaceutics, and our sensor data to build a calibrator-tablet process model that employs process sensor data to predict finished tablet dissolution rate.
Cache Aware and Hardware Assisted Algorithms
Douglas, HaaseResearch Issues. Recent computer architectures possess a very fast CPU and a relatively slow main memory. This means in practice that computer programs spend too much time waiting for data from memory and that only a very small percentage of the maximal floating point performance can be achieved as a consequence. The computer vendors tackle this problem by a hierarchy of faster small memory pieces, the so-called caches (L1- to L3-caches). Although compilers try to support the cache hierarchy the programmer of number cruncher software has to carefully design both the data layout and numerical algorithms in order to assist the compiler and the CPU in a better cache usage.
Related Research. Douglas and Haase worked on portable memory hierarchy techniques during the last years. These techniques have been also applied in an ocean modeling code as well as in a medical source identification problem [59]. Douglas has worked with a number of researchers on this topic.
Research Approach. All of the code kernels for saddle point problems, eigenvalue problems and optimization problems have to deal with large systems of equations to solve. We will analyze and redesign these kernels with respect to the specifications of the problem(multiple right hand sides, block systems, structured or unstructured grids). The expected performance gain will be between 2 and 5.
Craig's Home U. of Kentucky Yale ML-DDDAS Group Preprints Free software Class webs: All
TAMU CPSC 689-608Digital pictures:
Places FamilyJournals:
Computing JACTScientific Community Web Sites:
DDDAS MGNet Minimus