A model is developed for the flow of blood, within a thermodynamic framework that takes cognizance of the fact that viscoelastic fluids can remain stress free in several configurations, i.e., such bodies have multiple natural configurations (see Rajagopal 1995, Rajagopal and Srinivasa 2000). This thermodynamic framework leads to blood being characterised by four independent parameters that reflect the elasticity, the viscosity of the plasma, the formation of rouleaus and their effect on the viscosity of blood, and the shear thinning that takes place during the flow. The model emerges in a hierarchy of increasingly complex nonsimple viscoelastic fluid models, and in this study two other models in the same class (proposed by Rajagopal and Srinivasa 2000) are also considered. The efficacy of these models in describing the response of blood is investigated. Among the models studied, the proposed model is not only best able to describe the response of blood but is the first to have rigorous thermodynamic moorings. The predictions of the model agree exceptionally well with the data that is available for steady flow and oscillatory flow experiments, while the two other models are inadequate to describe oscillatory flows (a serious shortcoming as oscillatory flows are the most natural flows that blood undergoes).

The procedure for determining (assigning) the material parameters that characterize blood will be outlined in detail and the results of numerical simulations are compared with the data. This method is also used to fix the relaxation times in the model proposed by Yeleswarapu 1996, and the importance of the relaxation times for simulating pulsatile flow is highlighted.

We describe data structures for representing simplicial meshes compactly while supporting online queries and updates efficiently. Our representation requires about a factor of five less memory than the most efficient standard representations of triangular or tetrahedral meshes, while efficiently supporting traversal among simplices, storing data on simplices, and insertion and deletion of simplices.

Our implementation of the data structures uses about 5 bytes/triangle in two dimensions (2D) and 7.5 bytes/tetrahedron in three dimensions (3D). We use the representations to implement 2D and 3D incremental algorithms for generating a Delaunay mesh. The 3D algorithm can generate 100 Million tetrahedrons with 1 Gbyte of memory, including the space for the coordinates and all data used by the algorithm. The runtime of the algorithm is as fast as Shewchuk's Pyramid code, the most efficient we know of, and uses a factor of 3.5 less memory overall.

Multiple interacting mechanisms control the formation and dissolution of clots to maintain blood in a state of delicate balance. In addition to a myriad of biochemical reactions, rheological factors also play a crucial role in modulating the response of blood to external stimuli. To date, a comprehensive model for clot formation and dissolution, that takes into account the biochemical, medical and rheological factors, has not been put into place, the existing models emphasizing either one or the other of the factors. In this paper, after discussing the various biochemical, physiologic and rheological factors at some length, we develop a model for clot formation and dissolution that incorporates many of the relevant crucial factors that have a bearing on the problem. The model, though just a first step towards understanding a complex phenomenon goes further than previous models in integrating the biochemical, physiologic and rheological factors that come into play.

This paper presents a scalable solution to the group mutual exclusion problem, with applications to linearizable stacks and queues, and related problems. Our solution allows entry and exit from the mutually exclusive regions in O(t_r + tau) time, where t_r is the maximum time spent in a critical region by a user, and tau is the maximum time taken by any instruction, including a fetch-and-add instruction. This bound holds regardless of the number of users. We describe how stacks and queues can be implemented using two regions, one for pushing (enqueueing) and one for popping (dequeueing). These implementations are particularly simple, are linearizable, and support access in time proportional to a fetch-and-add operation. In addition, we present experimental results comparing room synchronizations with the Keane-Moir algorithm for group mutual exclusion.

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in their scope of applicability. We propose a general mechanism for adaptive computing that enables one to make any purely-functional program adaptive.

We show that the mechanism is practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key.

To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize the change-propagation algorithm and prove its correctness.

Subdivision surfaces have become a widely used geometric representation for general curved three dimensional boundary models and thin shells as they provide a compact and robust framework for modeling 3D geometry. More recently, the shape functions used in the subdivision surfaces framework have been proposed as candidates for use as finite element basis functions in the analysis and simulation of the mechanical deformation of thin shell structures. The subdivision shape functions automatically provide the necessary continuity required for representing the solution of the governing equations, which can be difficult to provide with other descriptions. When coupled with standard solvers, however, such simulations do not scale well. Given the fourth order nature of the governing equations, the condition number of the underlying stiffness matrices scale poorly as the number of elements is increased. Run time costs associated with high-resolution simulations (10⁵ degrees of freedom or more) become prohibitive. In this paper, we describe an algorithm that exploits the hierarchical, multilevel structure of subdivision surfaces to accelerate the convergence of solution strategies. The main contribution of the paper is to show that the subdivision framework can be used not only for representing the geometry of the solid and the mechanics of the simulation, but also for accelerating the numerical solution. Specifically the subdivision matrix and its transpose are used as the prolongation and restriction operations in a multilevel preconditioner. Our method allows us to construct practical simulations that are effective on a broad range of problems. Our examples show that the run time of the algorithm presented scales nearly linearly in time with problem size.

Though a minor component by volume, platelets can have a profound influence on the flow characteristics of blood and thereby have serious consequences with regard to cardiovascular functions. Platelets are extremely sensitive to chemical agents as well as mechanical inputs and platelet activation is a necessary precursor to many life threatening medical conditions such as acute myocardial infarction, most strokes, acute arterial occlusion, venous thrombosis and pulmonary embolism. In cardiovascular devices such as ventricular assist devices and prosthetic heart valves, high shear stresses can trigger platelet activation. Moreover, such devices have artificial surfaces that are thrombogenic, the thrombotic deposition contributing to the failure of the device. Thus, there is a need to develop a mathematical model for the flow of blood that takes into account platelet activation, no such model being available at the moment.While there has been considerable amount of work in blood rheology, the role of platelets in the flow characteristics of blood has been largely ignored. This study addresses this lacuna.

Triangulations of a surface are of fundamental importance in computational geometry, computer graphics, and engineering and scientific simulations. Triangulations are ordinarily represented as mutable graph structures for which both adding and traversing edges take constant time per operation. These representations of triangulations make it difficult to support persistence, including ``multiple futures'', the ability to use a data structure in several unrelated ways in a given computation; ``time travel'', the ability to move freely among versions of a data structure; or parallel computation, the ability to operate concurrently on a data structure without interference.

We present a purely functional interface and representation of triangulated surfaces, and more generally of simplicial complexes in higher dimensions. In addition to being persistent in the strongest sense, the interface more closely matches the mathematical definition of triangulations (simplicial complexes) than do interfaces based on mutable representations. The representation, however, comes at the cost of requiring O( n) time for traversing or adding triangles (simplices), where n is the number of triangles in the surface. We show both analytically and experimentally that for certain important cases, this extra cost does not seriously affect end-to-end running time. Analytically, we present a new randomized algorithm for 3-dimensional Convex Hull based on our representations for which the running time matches the Omega(n log n) lower-bound for the problem. This is achieved by using only O(n) traversals of the surface. Experimentally, we present results for both an implementation of the 3-dimensional Convex Hull and for a terrain modeling algorithm, which demonstrate that, although there is some cost to persistence, it seems to be a small constant factor.

Equations governing the flow of fluid containing visco-hyperelastic particles are developed in an Eulerian framework. The novel feature introduced here is to write an evolution equation for the strain. It is envisioned that this will simplify numerical codes which typically compute the strain on Lagrangian meshes moving through Eulerian meshes. Existence results for the flow of linear visco-hyperelastic particles in a Newtonian fluid are established using a Galerkin scheme.

Many important phenomena in science and engineering, including our motivating problem of microstructural blood flow, can be modeled as flows with dynamic interfaces. The major challenge faced in simulating such flows is resolving the interfacial motion. Lagrangian methods are ideally suited for such problems, since interfaces are naturally represented and propagated. However, the material description of motion results in dynamic meshes, which become hopelessly distorted unless they are regularly regenerated. Lagrangian methods are particularly challenging on parallel computers, because scalable dynamic mesh methods remain elusive. Here, we present a parallel dynamic mesh Lagrangian method for flows with dynamic interfaces. We take an aggressive approach to dynamic meshing by triangulating the propagating grid points at every timestep using a scalable parallel Delaunay algorithm. Contrary to conventional wisdom, we show that the costs of the geometric components (triangulation, coarsening, refinement, and partitioning) can be made small relative to the flow solver. For example, in a simulation of 10 interacting viscous cells with 500,000 unknowns on 64 processors of a Cray T3E, dynamic meshing consumes less than 5 processors show that the computational geometry scales about as well as the flow solver. Therefore we anticipate that overall scalability on larger problems will be as good as the flow solver's.

We present a new method for enforcing boundary conditions within subdivision surface finite element simulations of thin shells. The proposed framework is shown to be second order accurate for displacements with respect to increasing refinement for simply-supported and clamped boundary conditions. Second order accuracy on the boundary is consistent with the accuracy of subdivision based approaches for the interior of a body. Our proposed framework is applicable to both triangular and quadrilateral refinement schemes, and does not impose any topological requirements upon the underlying subdivision control mesh. Several examples from the Belytschko obstacle course of benchmark problems are used to demonstrate the convergence of the scheme.

We propose to develop advanced parallel geometric and numerical algorithms and software for simulating complex flows with dynamic interfaces. The development of scalable, parallel high-accuracy algorithms for simulating such flows poses enormous challenges, particularly on systems with thousands of processors. We will use the resulting tools to simulate blood flowin artificial heart devices. This application provides an excellent testbed for the methods we develop: simulation-based artificial organ design is extremely computationally challenging and of critical societal importance.

Flows with dynamic interfaces arise in many fluid-solid and fluid-fluid interaction problems, and are among the most difficult computational problems in continuum mechanics. Examples abound in the aerospace, automotive, biomedical, chemical, marine, materials, and wind engineering sciences. These include large-amplitude vibrations of such flexible aerodynamic components as high aspect ratio wings and blades; flows of mixtures and slurries; wind-induced deformation of towers, antennas, and lightweight bridges; hydrodynamic flows around offshore structures; interaction of biofluids with elastic vessels; and materials phase transition problems. We are particularly interested in modeling the flow of blood, which is a mixture of interacting solid cells and fluid plasma. Current blood flow models are macroscopic, treating the mixture as a homogeneous continuum. Microstructural models resolve individual cell deformations and interactions with the surrounding fluid plasma. Because of the computational difficulties of resolving tens of thousands of deforming cellular interfaces, no one to date has simulated realistic blood flows at the microstructural level. Yet such simulations are necessary in order to gain a better understanding of blood damage which is central to improved artificial organ design and for the development of more rational macroscopic blood models.

Parallel flow solvers on fixed domains are reasonably well understood. In contrast, simulating flows with dynamic interfaces is much more difficult. The central challenges are to develop numerical algorithms that stably and accurately couple the moving fluid and solid domains and resolve the deforming interfaces, and geometric algorithms for evolving and managing the resulting dynamic particle/mesh systems. The associated dynamic data structures are particularly troublesome on highly parallel computers, which are made necessary by the complexity of many applications. Most current methods approach the difficulties of dynamic interfaces by computing the flow on a fixed, regular grid. The effect of the dynamic interfaces is then incorporated either through some type of constraint or force representing the interface, or through an auxiliary field variable that signifies the presence of fluid or solid material at a spatial point. Parallelizing these methods is relatively straightforward, since the flow is computed on a fixed grid. However, the resulting fixed resolution is a serious disadvantage if one wants to vary resolution sharply within the grid. This is the case for example when local interfacial dynamics are critical, as in blood flow or phase change problems.

Our approach is radically different. We will treat the fluid and solid domains as collections of particles, with associated meshes, that evolve over time, and devise numerical algorithms that couple the fluid and solid together seamlessly. We will attack the difficulty of generating and managing a constantly evolving mesh/particle system by creating fundamentally new highly parallel and scalable algorithms for the convex hull, Delaunay triangulation, meshing, partitioning, and N-body components. Our preliminary 2D work demonstrates that the resulting geometric computations can be made very cheap compared to numerical computations. Despite the conventional wisdom on parallel dynamic mesh methods, we believe that with careful attention to fundamental algorithmic issues flow simulations on constantly evolving domains can be made to scale to the thousands of processors that characterize multi-teraflop systems.

While microstructural blood flow modeling will serve as our first application, the computational algorithms and software we create will be more widely applicable to a variety of fluid solid inter-action problems. More generally, the core parallel computational geometry kernels convex hull, Delaunay triangulation, coarsening/refinement, partitioning, N-body provide generic support for the geometric computations underlying many dynamic irregular problems. We will create and publically distribute a portable library of efficient implementations of these algorithms. Much as the PETSc library has greatly simplified the task of programming parallel PDE solvers by providing many of the necessary numerical kernels, we envision a library of parallel geometric kernels being of great benefit across a wide range of scientific computing problems that involve dynamic meshes.

We have assembled a multidisciplinary team that combines Carnegie Mellon s leadership in computer and computational science with the University of Pittsburgh Medical Center s world-class program in artificial organs. This project will support 11 graduate students and a group of un-dergraduates. These students will be part of a new program at CMU in Computational Science and Engineering that we are in the process of establishing. The proposed project will also be part of that program, and we believe will serve as an archetype of how applications, computational, computer, and mathematical scientists can work together to tackle societal problems that cannot be addressed solely from the vantage of any one discipline. Moreover, we intend to communicate our work to the broader public (as we have done in the past), in the process demonstrating how high end computing can contribute to improving the health of our society.