Abstract Abstract A virtual test facility (VTF) for studying the three-dimensional dynamic response of solid materials subject to strong shock and detonation waves has been constructed as part of the research program of the Center for Simulating the Dynamic Response of Materials at the California Institute of Technology. The compressible fluid flow is simulated with a Cartesian finite volume method and treating the solid as an embedded moving body, while a Lagrangian finite element scheme is employed to describe the structural response to the hydrodynamic pressure loading. A temporal splitting method is applied to update the position and velocity of the boundary between time steps. The boundary is represented implicitly in the fluid solver with a level set function that is constructed on-the-fly from the unstructured solid surface mesh. Block-structured mesh adaptation with time step refinement in the fluid allows for the efficient consideration of disparate fluid and solid time scales. We detail the design of the employed object-oriented mesh refinement framework AMROC and outline its effective extension for fluid-structure interaction problems. Further, we describe the parallelization of the most important algorithmic components for distributed memory machines and discuss the applied partitioning strategies. As computational examples for typical VTF applications, we present the dynamic deformation of a tantalum cylinder due to the detonation of an interior solid explosive and the impact of an explosion-induced shock wave on a multi-material soft tissue body. Introduction The virtual test facility (VTF) is a software environment for coupling solvers for compressible computational fluid dynamics (CFD) with solvers for computational solid dynamics (CSD). The CFD solvers facilitate the computation of flows with strong shocks as well as fluid mixing. The CSD solvers provide capabilities for simulation of dynamic response in solids such as large plastic deformations, fracture and fragmentation. In addition, the VTF can be used to simulate highly coupled fluidstructure interaction problems, such as the high rate deformation of metallic solid targets forced by the loading from the detonation of energetic materials, or the rupture and fragmentation of brittle materials under shock wave impact. At present, all VTF solvers use timeexplicit shock-capturing schemes. Introduction In order to implement fluid-structure coupling in the VTF, we apply a loosely coupled, partitioned approach. The technique operates as follows: one assumes disjoint fluid and solid domains and that the interaction takes place only at the fluid-solid interface. In this way, one can apply algorithms that are intrin-sically suited for simulation of phenomena such as shock propagation, detonation or fluid mixing in the fluid solver, while algorithms similarly optimized for phenomena such as high-rate plastic deformation or fracture can be employed in the solid solver. For example, a Lagrangian representation is most suitable to account numerically for large solid deformations, contact and fracture, while the governing equations of compressible fluid motion are most effectively solved in an Eulerian frame of reference [1] . In the loose fluid-structure coupling adopted, the information exchange is reduced to communicating the velocities and the geometry of the solid surface to the Eulerian fluid and imposing the hydrostatic pressure onto the Lagrangian solid as a force acting on its exterior [1] [2] [3] [4] [5] [6] [7] . This approach offers several advantages. Firstly, it allows for solver reuse (see [8] or [2] for details on the idea of modularization). Secondly, it becomes straightforward to take advantage of recent advances in multiscale constitutive modeling to describe the dynamic response of both solid and fluid. Such modeling typically also employs a Lagrangian description for solids and an Eulerian description for the fluid. Introduction A key issue that arises with the proposed approach is how to represent the evolving surface geometry on the Eulerian fluid mesh. The application of body-conforming meshes is somewhat cumbersome, because the fluid equations first need to be cast into a local arbitrary Lagrangian-Eulerian (ALE) frame of reference [9] . At each step, the mesh topology would have to be reconstructed and the solution re-interpolated. While this is possible (and successfully implemented in many present-day codes), the issues of mesh tangling and the requirements of frequent re-meshing in the case of large deformations remain a challenge. The need to remesh is also an inherent bottleneck in massively parallel simulations [6] . Introduction An alternative to the use of body-aligned fluid grids is the application of Cartesian meshes with immersed or embedded irregular boundaries. Here, there are two basic approaches: ''cut-cell'' techniques that construct smaller cells by intersecting the Cartesian mesh exactly with the (triangulated) boundary and techniques that ''diffuse'' the boundary within one cell [10] . Cut-cell methods have the advantage that they can represent accurately the boundary flux and thus facilitate the implementation of discretely conservative fluid solvers. However, the proposed numerical circumventions of the severe time step restriction in time-explicit schemes [11, 12] , which can result from very small cells created by the boundary intersection, are logically quite complicated. Most approaches have not yet been extended successfully to three spatial dimensions even for pure fluid flow problems. In the VTF, we therefore employ a diffused boundary technique in which some interior cells are used directly to enforce the embedded boundary conditions in the vicinity of the solid surface [4, 13] . This has been called the ''ghost fluid'' approach. One advantage of this approach is that the numerical stencil is not modified, thus ensuring optimal parallel scalability. We minimize conservation errors as well as possible numerical ''staircase'' artifacts at the embedded boundary by using block-structured dynamic adaptation of the fluid mesh. As the solid deforms, the solid-fluid boundary is represented implicitly with a scalar level set variable that is updated on-the-fly using an efficient algorithm described in more detail below. An important additional advantage of this approach is the ability to cope with topological transitions such as fracture or penetration. Introduction The present paper details the implementation of the VTF approach and also describes its application to fluid-solid interaction problems wherein detonation and shock waves impinge on thick three-dimensional solid materials. An extension of the basic, non-adaptive fluid-solid coupling algorithm used herein to thin, open structures has recently been presented in [14] . In Sect. 2, a Cartesian dynamically adaptive finite volume fluid solver for Euler equations with one-step chemistry is described. We detail the design of the underlying mesh refinement framework and discuss its parallelization. Section 3 outlines the parallel Lagrangian finite element solver for solid materials subjected to high-intensity shock loadings. In Sect. 4, we describe a highly efficient algorithm to transform a triangulated surface mesh into a signed distance function on a hierarchical Cartesian mesh as a prerequisite for coupling. The fluid-structure interaction methodology, highlighting particular its incorporation into the adaptive fluid mesh refinement framework, and an efficient inter-solver communication library are detailed in Sect. 5. Section 6 provides two three-dimensional computational examples. In Sect. 6.1, we simulate the impact event of a strong hydrodynamic shock wave on a body comprised of softtissue; in Sect. 6.2 the propagation of a detonation wave in HMX through a plastic tantalum cylinder is described. Both computations were run on distributed memory machines and we comment briefly on the overall computational efficiency of the approach. Eulerian fluid dynamics In this section, we are concerned with the construction of an Eulerian fluid solver framework suitable for efficient fluid-structure coupling. Although the pre-sentation is tailored to the Euler equations with simple one-step reaction, the concepts are equally applicable to general conservation laws with arbitrary source terms. Within the Center for Simulating the Dynamic Response of Materials at the California Institute of Technology, the same framework is also used successfully with solvers for the compressible Favreaveraged Navier-Stokes equations with a large-eddy turbulence model [15] and for detonation simulation in thermally perfect gas mixtures with detailed chemical kinetics [16] [17] [18] [19] [20] . Governing equations In order to model detonation waves in solid energetic materials, we utilize the single-phase model proposed by Fickett and Davis [21] , which has also been used by Clarke et al. [22] to evaluate numerical methods for detonation simulation. We assume a single chemical reaction A À! B that is modeled by a progress variable k, which corresponds to the mass fraction ratio between the density of the product B and the total density q, i.e. k = q B /q. The governing equations of the model read Governing equations Here, u is the velocity vector and E the specific total energy. The hydrostatic pressure p is given by Governing equations with c denoting the ratio of specific heats and q the heat release due to the chemical reaction per unit mass. The reaction itself is modeled by the simple rate function Governing equations In Eq. 6, T R denotes a typical time associated with the reaction, in which the depletion from A to B is complete. It is worth mentioning that the above model includes the Euler equations for a single polytropic gas as Eqs. 1-3 and 5 for w " 0 and q " 0, which is the appropriate model for purely hydrodynamic shock wave propagation (cf. Sect. 6.1). Cartesian finite volume method with embedded boundaries Following Clarke et al. [22] , we apply the method of fractional steps to decouple the chemical reaction and hydrodynamic transport numerically. The homogeneous system of Eqs. 1-4 and the scalar ordinary differential equation ¶ t k = w(k) are solved successively with the data of the preceding step as initial conditions. As the homogeneous system Eqs. 1-4 is a hyperbolic conservation law that admits discontinuous solutions (cf. [22] ), we use a time-explicit finite volume discretization that achieves a proper upwinding in all characteristic fields. The scheme is based on a straightforward generalization of the Roe scheme for the purely hydrodynamic Euler equations 1-3 and is extended to a multi-dimensional Cartesian scheme via the method of fractional steps (cf. [23] ). To circumvent the intrinsic problem of unphysical total densities and internal energies near vacuum due to the Roe linearization (cf. [24] ), the scheme has the possibility to switch to the simple, but extremely robust Harten-LaxVan Leer (HLL) Riemann solver [17] [18] [19] . The MUS-CL-Hancock variable extrapolation technique of Van Leer [23] is employed to achieve second-order accuracy in regions where the solution is smooth. Geometrically complex moving boundaries are considered within the Cartesian method outlined above by utilizing some of the finite volume cells as ghost cells to enforce immersed boundary conditions [10, 25] . The ghost cell values are set immediately before the original numerical update to model moving embedded walls. The boundary geometry is mapped onto the Cartesian mesh by employing a scalar level set function / that stores the signed distance to the boundary surface and allows the efficient evaluation of the boundary outer normal in every mesh point as n ¼ Àr/=jr/j [26] . In coupled Eulerian-Lagrangian simulations, / is updated on-the-fly by calling the closest-point-transform algorithm described in detail in Sect. 4. A cell is considered to be a valid fluid cell within the interior, if the distance / in the cell midpoint is positive, and is treated as exterior otherwise. The unavoidable staircase approximation of the boundary with this approach is alleviated by using the dynamic mesh adaptation technique described in the next section to also refine the Cartesian mesh appropriately along the boundary. Cartesian finite volume method with embedded boundaries For the system of Eqs. 1-4, the boundary condition at a rigid wall moving with velocity w is u Á n ¼ w Á n: Enforcing the latter with ghost cells requires the mirroring of the primitive values q, u; p, k across the embedded boundary and the velocity modification Engineering with Computers (2006) 22:325-347 327 u 0 ¼ 2 ðw À uÞ Á n ð Þ n þ u within the ghost cells. We derive mirrored values in a ghost cell center x by calculating spatially interpolated values at the point x ¼ x þ 2/n from neighboring interior cells. For instance, in two spatial dimensions a bilinear interpolation between (usually) four adjacent cell values is employed, but directly near the boundary the number of cells contributing to the interpolation needs to be decreased to preserve the monotonicity of the numerical solution. Figure 1 highlights the reduction of the interpolation stencil for some exemplary cases close to the embedded boundary. The interpolation locations are indicated by the origins of the arrows normal to the complex boundary (dotted). Cartesian finite volume method with embedded boundaries After the application of the numerical scheme, the cells that have been used to impose the internal boundary conditions are set to the entire state vector of the nearest cell in the interior. This operation achieves a constant value extrapolation and ensures proper values in case such a cell becomes a regular interior cell in the next step due to boundary movement. Note that the boundary velocity w gets automatically considered through the velocity modification in the internal ghost cells and the usual stability condition for time-explicit methods for system 1-4 also ensures that the embedded boundary propagates at most one cell further in every time step. Structured adaptive mesh refinement In order to supply the required temporal and spatial resolution efficiently, we employ the structured adaptive mesh refinement (SAMR) method after Berger and Colella [27] , which is tailored especially for hyperbolic conservation laws on logically rectilinear finite volume grids. Instead of replacing single cells by finer ones, as is done in cell-oriented refinement techniques, the Berger-Collela SAMR method follows a patch-oriented approach. Cells being flagged by various error indicators (shaded in Fig. 2 ) are clustered with a special algorithm [28] into non-overlapping rectangular grids. Refinement grids are derived recursively from coarser ones and a hierarchy of successively embedded levels is thereby constructed (cf. Fig. 2 ). All mesh widths on level l are r l -times finer than on level l -1, i.e. Dt l : = Dt l-1 /r l and Dx k,l : = Dx k,l-1 /r l with r l ‡ 2 for l > 0 and with r 0 = 1, and a time-explicit finite volume scheme will (in principle) remain stable on all levels of the hierarchy. Structured adaptive mesh refinement The numerical scheme is applied on level l by calling a single-grid routine in a loop over all subgrids. The subgrids get computationally decoupled by employing additional ghost cells around each computational grid. Three different types of ghost cells have to be considered: cells outside of the root domain are used to implement physical boundary conditions. Ghost cells overlaid by a grid on level l have a unique interior cell analogue and are set by copying the data value from the grid, where the interior cell is contained (synchronization). On the root level no further boundary conditions need to be considered, but for l > 0 internal boundaries can also occur. They are set by a conservative time-space interpolation from two previously calculated time steps of level l -1. Structured adaptive mesh refinement Besides a general tree data structure that stores the topology of the hierarchy (cf. Fig. 2 ), the SAMR method requires at most two regular arrays assigned to each subgrid. They contain the discrete vector of state for the actual and updated time step. The regularity of the data allows high performance on vector and superscalar processors that allow cache optimizations. Small data arrays are effectively avoided by leaving coarse level data structures untouched when higher level grids are created. Values of cells covered by finer subgrids Fig. 1 Interpolation from interior cells to construct mirrored values to be used within internal ghost cells (gray) Fig. 2 The AMR method creates a hierarchy of rectangular subgrids are subsequently overwritten by averaged fine grid values. This operation leads to a modification of the numerical stencil on the coarse mesh and requires a special flux correction in cells abutting a fine grid. The correction replaces the coarse grid flux along the fine grid boundary by a sum of fine grid fluxes and ensures the discrete conservation property of the hierarchical method (at least for purely Cartesian problems without embedded boundaries; see [27] or [19] for details). Parallel implementation Up to now, various reliable implementations of the SAMR method for single processor computers have been developed. Even the usage of parallel computers with shared memory is straightforward, because timeexplicit methods allow the parallel calculation of the grid-wise numerical update [28] . But the question of an efficient parallelization strategy becomes more delicate for distributed memory architectures, because on such machines the costs for communication cannot be neglected. Due to the technical difficulties of implementing dynamical adaptive methods in distributed memory environments only a few parallelization strategies have been considered in practice to date (cf. [29, 30] ). Parallel implementation Parallel SAMR in the VTF at the California Institute of Technology is provided generically by the AMROC (Adaptive Mesh Refinement in Object-oriented C++) framework [31] . AMROC has been parallelized very effectively for distributed memory machines [32] and can be used on all systems that provide the MPI library. The parallelization strategy is a rigorous domain decomposition approach that partitions the SAMR hierarchy from the root level on. The key idea is that all higher level domains are required to follow this ''floor plan''. A careful analysis of the SAMR algorithm uncovers that the only parallel operations under this paradigm are ghost cell synchronization, redistribution of the hierarchical data and the application of the previously mentioned flux correction terms. Interpolation and averaging, and, in particular, the calculation of the flux corrections remain strictly local [19] . Currently, we employ a generalization of Hilbert's space-filling curve [33] to derive load-balanced root level lisa22@example.net. The entire SAMR hierarchy is considered by projecting the accumulated work from higher levels onto the root level cells. Although rigorous domain decomposition does not lead to a perfect balance of workload on single levels, good scale-up is usually achieved for moderate CPU counts. Figure 3 shows a representative scalability test for a three-dimensional spherical shock wave problem for the Euler equations of a single nonreactive gas (Eqs. 1-3 and 5 Fig. 3 shows a reasonable scale-up for at least up to 64 CPUs. We are currently researching scalability strategies that will allow full scale-up to thousands of processors. Design of the AMROC framework A salient feature of AMROC compared to other available SAMR implementations, e.g. [29, 34] , is the realization of object-oriented framework concepts in C++ on all levels of software design. This allows for effective code re-use in implementing parallel SAMR algorithms and extensive capability for customization through subclass derivation. Design of the AMROC framework In block-structured dynamically adaptive codes, three abstraction levels can be identified. At the top level, a particular physical simulation problem is formulated by providing a numerical scheme, by setting 3) with geometric adaptive multigrid methods for implicit discretizations, reveals that the SAMR auxiliary components show great similarity and can easily be reused. In AMROC, components such as the flagging of cells for refinement depending on various criteria, the clustering of flagged cells into rectangular regions, inter-level data transfer and flux correction (fixup) reside in clearly separated classes. This is highlighted in Fig. 4 which displays the most important AMROC classes and their relationships in unified modeling language (UML) notation [35] for the purely Cartesian case. The recursive Berger-Collela SAMR algorithm tailored for the hyperbolic problems of interest is realized here in the central class HypSAMRSolver; all others classes are generic, enabling the utilization of AMROC as a software framework for the efficient implementation of different SAMR algorithms typically implemented in new central SAMRSolver classes. The intermediate AMROC design level naturally utilizes classes of the base level that provide hierarchical data structures. The base level is divided into elementary functionality for single grid patches and the implementation of various lists that store these patches hierarchically. A common design for the base level (see also [29] ) involves a Box class to specify a single rectangular box in global integer index space. Methods for geometric operations on boxes like concatenation or intersection are available. A Patch class adds consecutive data storage to a Box. In AMROC, the geometrical description of all refinement areas is stored in hierarchical lists of Box objects inside a single GridHierarchy. The templatized class GridFunction creates Patch objects for various, possibly complex, data types following exactly the Box lists of GridHierarchy. As the refinement lists in GridHierarchy evolve and are dynamically distributed to an evolving set of processors, the Patch objects in GridFunction are automatically re-created, including parallel redistribution and synchronization. Design of the AMROC framework The design of the hierarchical data structures in AMROC follows the DAGH (Distributive Adaptive Grid Hierarchies) package by Parashar and Browne [30] that itself was intended as software framework for SAMR algorithms, but the enormous complexity in SAMR algorithms and their auxiliary components makes framework concepts at higher design levels (see above) more effective. As an illustration, Fig. 5 shows the most important classes that have been added to the originally Cartesian SAMR framework to implement arbitrary level-set-based embedded boundary methods like the one sketched in Sect. 2.2. An abstract class LevelSetEvaluation is provided to evaluate the scalar GridFunction / patch-wise; EmbeddedBoundaryConditions allows the specification of the detailed boundary value modification. Multiple EmbeddedBoundaryMethods can also be considered and are incorporated with minimal implementation overhead into the existing algorithms of the SAMRSolver class for hyperbolic problems, HypSAMRSolver, through the derived class EBMHypSAMRSolver. The only operation that had to be extended was that of applying physical boundary conditions. Lagrangian formulation of solid dynamics We adopt a conventional Lagrangian formulation [36] for describing the large, dynamic deformations of solid materials subject to high-intensity shock loadings. The formulation accounts for finite kinematics, inertia and general constitutive behavior, including strength. Governing equations We select the configuration B 0 & R 3 of the body at time t 0 as the reference configuration. The coordinates X of points in B 0 are used to identify material particles throughout the motion. The motion of the body is described by the deformation mapping x ¼ uðX; tÞ ð 7Þ Governing equations (not to be confused with the levelset function). Thus, x is the position of material particle X at time t. The material velocity and acceleration fields follow from Eq. 7 as _ uðX; tÞ and € uðX; tÞ; where a superposed ð _ Þ denotes partial differentiation with respect to time at fixed X. The local deformation of an infinitesimal material neighborhood is described by the deformation gradient Governing equations where Ñ 0 denotes the material gradient of a function defined over B 0 . The scalar function Governing equations is the Jacobian of the deformation and measures the ratio of the deformed to undeformed volume of an infinitesimal material neighborhood. The motion of the body is subject to conservation of linear momentum (cf. [36] ), which takes the form Governing equations where B(X, t) is the body force per unit mass, P(X,t) denotes the first Piola-Kirchhoff stress tensor and q 0 (X) the mass density over B 0 . The symmetric Cauchy stress tensor follows from P through the relation Governing equations For purposes of formulating boundary conditions, we partition the boundary of B 0 into a Dirichlet or displacement boundary ¶B 01 and a Neumann or traction boundary ¶B 02 . The boundary conditions then take the form Governing equations where " uðX; tÞ is the prescribed deformation mapping on ¶B 01 , N is the unit outward normal to ¶B 02 and " TðX; tÞ are the prescribed tractions applied to ¶B 02 . Finally, dynamic problems require initial conditions u 0 ðXÞ and _ u 0 ðXÞ to be specified over B 0 . Shock-capturing material model Assuming the material behavior is reversible, the stress tensor can be computed from an internal energy function U as Shock-capturing material model This model is well suited for low-intensity loading (see Sect. 6.1), but when the solid interacts with highintensity fluid shocks, a strong stress wave propagates within the solid (cf. Sect. 6.2). The inelastic material behavior then has to be accounted for and a shockcapturing numerical scheme is also needed to accurately represent evolving stress fronts inside the solid. Here, we apply a Lagrangian artificial viscosity method for solids with strength presented in [37] . The addition of artificial viscosity has the intended effect of spreading fronts that are too steep to be resolved accurately over several grid points without altering their speed of propagation while avoiding the introduction of numerical artifacts such as spurious oscillations (cf. [38] ). Shock-capturing material model A general constitutive theory of inelastic material behavior may be based on irreversible continuum thermodynamics (cf. [39] [40] [41] for more extensive accounts). In this context, viscosity may be modeled by assuming an additive decomposition Shock-capturing material model of the first Piola-Kirchhoff stress tensor into an equilibrium part P e and a viscous part P v . Additionally, we assume that the local thermodynamic state of the material is fully described by the local deformation F, the local absolute temperature T, and a collection q of internal state variables. In particular, we assume that the free energy per unit of undeformed volume can be expressed as a function A(F, T, q). As in the reversible case expressed in Eq. 14, the equilibrium stresses then follow from the free energy as Shock-capturing material model In materials without strength, A depends on the deformation only through the Jacobian J and the hydrostatic pressure p is computed by Shock-capturing material model Here, we adopt the usual fluids convention and regard compressive pressure as positive. In the presence of shocks propagating in the solid, the volumetric response is described by a suitable equation of state (EOS). The constitutive library in the VTF is endowed with well-established phenomenological equations of state for solids including the Mie-Gruneisen EOS, as well as others obtained from first-principles quantum mechanics calculations as part of the Center's efforts in multiscale modeling. In addition to a volumetric equation of state, a complete characterization of the behavior of the solid requires a description of its strength, including its elasticity, yield point, strain hardening, rate sensitivity and temperature dependence. This is accomplished by the specification of the internal energy density A, plus suitable kinetic equations for the internal state variables q. Owing to the high strain rate under consideration, only adiabatic material models are considered. In addition, the material is assumed to obey the J 2 -flow theory of plasticity. We adopt a standard formulation of finite-deformation plasticity based on a multiplicative decomposition of the deformation gradient into elastic and plastic components: F = F e F p , where F p is assumed to be volume-preserving. The equilibrium stress-strain relation 17 is now extended to include the elasticity of the material in shear, with the result [41, 42] Shock-capturing material model where C e = F eT F e is the elastic Cauchy-Green deformation tensor, log ffiffiffiffiffi ffi C e p is the logarithmic elastic strain and l is a shear modulus. The plastic deformation F p is assumed to obey the Prandtl-Reuss flow rule Shock-capturing material model where s e ¼ r e;dev is the stress deviator, " r ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ð3=2Þs e ij s e ij q denotes the von Mises stress, and e p is the effective plastic strain. Relation 19 is solved by considering a hardening law Shock-capturing material model that characterizes the material behavior. The VTF possesses a large set of constitutive models and algorithmic updates that describe a wide range of material response, including variational updates for isotropic and crystal plasticity [41] , a multiscale model of singlecrystal b.c.c. tantalum [43] and a polyconvex model for anisotropic cubic crystals [44] . The viscous part of the stresses (Eq. 15) is assumed to take the form Shock-capturing material model where r v ¼ 2g h ðsym _ FF À1 Þ dev and g h denotes the viscosity coefficient. In the latter, sym and dev denote the symmetric and deviatoric components of a tensor, respectively. In order to construct an artificialviscosity-based scheme, we assume that the viscosity coefficient is comprised of two terms, leading to Shock-capturing material model where g is the physical viscosity coefficient of the material and D g the added artificial viscosity. We refer to [37, 38, 45] for details about the evaluation of D g. Finite-element temporal integration The preceding continuum formulation is rendered into a form suitable for computation by combining a time discretization of the momentum and constitutive equations with a finite element discretization for the reference configuration of the solid. More detailed accounts may be found in [40, 41] . We consider finite element interpolations of the form Finite-element temporal integration where x a is the current position at node a and N a are the shape functions. The sum on a ranges over the N nodes of the mesh. The displacement shape functions N a must be conforming. In calculations, we employ standard quadratic, six-noded triangles or ten-noded tetrahedra (e.g. [46] ). Utilizing these definitions, the weak formulation of the linear-momentum balance equation 10 is written as Finite-element temporal integration In these equations, M is the diagonal lumped mass matrix and f inert , f int and f ext are the inertial, internal and external forces, respectively. Finite-element temporal integration Here and subsequently, we implement an incremental solution procedure aimed at sampling the solution at discrete times t 0 , t 1 ,...,t n , where t n+1 = t n + nt. The integration in time is performed with the Newmark family of time-stepping algorithms: Finite-element temporal integration where b and c are Newmark parameters. The performance of the Newmark algorithm, including its range of stability, has been extensively documented in the literature (e.g. [47] [48] [49] ). Our particular case of Finite-element temporal integration 2 is explicit and second-order accurate and leads to a central difference scheme. Parallel implementation Our finite element solid solver ''Adlib'' is implemented in C following a modular concept that encapsulates similar functionality in libraries. The main libraries are -The material library, which provides the material response to a given deformation history for a set of complex constitutive material models. -The mesh manager, which is responsible for the construction of the elements, connectivity tables and for the attribution of the properties to the elements. Parallel implementation -The mechanics library, which manages the space and time integration of the finite element discretization. -The partitioning library, which is responsible for distributing the mesh to the processors of a parallelized application. In Adlib, different types of applications are realized by providing a specific main program that calls the required library functionality. Problem-specific frontend routines, e.g. for boundary conditions, are linked to enable detailed customization. Although more classical than the concepts discussed in Sect. 2.5, we achieve effective code re-use in the same application domain. For instance, the extensive VTF material library is shared among Adlib and the VTF thin-shell finite element solver with fracture capability (see [50] for a computational example). Parallel implementation In the following, we detail the Adlib parallelization library. The parallelization strategy employed in Adlib is straightforward domain decomposition. The mesh distribution is based on heuristic graph partitioning as provided by the well-established software package METIS [51] . Optionally, the local mesh can be recursively refined using a mesh subdivision algorithm for tetrahedral meshes proposed by Liu and Joe [52] . In every refinement iteration, each tetrahedron is subdivided into eight new ones. For illustration purposes, this algorithm is applied to the mesh for a beam with about 10,000 elements shown in Fig. 6 that is distributed to 16 processors. On each processor, the mesh is subdivided with one level of refinement leading to the configuration displayed in Fig. 7 . The main advantage of this algorithm is that only two new classes of slightly less regular tetrahedra are introduced, independent of the number of refinement iterations, thus enabling the creation of distributed meshes in a scalable way. The uniqueness of the algorithm ensures conforming elements in every level of subdivision. Note that the application of the subdivision procedure mandates the reconstruction of the interprocessor communication maps. Parallel implementation For parallel fluid-structure interaction simulations, all the above libraries are linked to the coupled code. A solid update step begins as usual by applying boundary conditions (here tractions produced by the hydrodynamic pressure), and proceeds by computing the predictor configuration of the solid and performing the necessary constitutive updates at each element quadrature point as part of the assembly of the global residual vector. At this point, a point-topoint communication operation is necessary to exchange the incomplete residuals at partition boundary nodes. After this step, the corrected nodal accelerations and velocities can be obtained locally by Engineering Parallel implementation applying the unmodified corrector step. As the communication operations involve only partition boundary data, and retain a surface to volume character, the solid update algorithm shows excellent scalability properties. In order to illustrate this fact, a study of strong scaling has been performed for a tensile test utilizing the mesh depicted in Fig. 6 (one level of subdivision) . The test was run on a cluster of AMD Opteron-2.2 GHz quad-core nodes connected with an Infiniband network. The average compute time per element per step is shown in Fig. 8 and we measure a constant parallel efficiency of approximately 0.9. The efficiency of the method has also been confirmed in several large-scale computations related to the dynamic response of polycrystalline materials [53] [54] [55] [56] [57] [58] that have only been made possible by employing the massively parallel systems provided by the DoE ASC program. Closest-point-transform algorithm In Sect. 2, we have introduced the concept of a signed distance function as a natural way to represent a complex embedded boundary on a Cartesian mesh. While signed distance functions are easily prescribed for single elementary geometric objects, their evaluation can be extremely cumbersome for complex shapes. In coupled Eulerian-Lagrangian simulations, this complex shape is defined by the boundary of the solid mesh. Since the solid mesh is tetrahedral (cf. Sect. 3), the interface is a triangle mesh. In the following, we outline the specific algorithm that we have developed to effectively transform the explicit description of a triangulated surface mesh into a signed distance function. The problem is equivalent to finding for every discrete point on the Cartesian SAMR grid the nearest or closest point on this surface mesh. The algorithm is therefore named the closest point transform (CPT). Without loss of generality, we assume a single uniform Cartesian grid in the following discussion. Problem description Let, /ðxÞ; x 2 R n ; be the distance from the point x to a manifold I : If dimðI Þ ¼ n À 1 and the manifold is closed, (for example, curves in 2-D or surfaces in 3-D), then the distance may be signed. The orientation of the manifold determines the sign of the distance. We adopt the convention that the outward normal points in the positive direction. In order for the distance to be well defined, the manifold must be orientable and have a consistent orientation. A Klein bottle in 3-D, for example, is not orientable. Two concentric circles in 2-D have consistent orientations only if the normals of the inner circle point ''inward'' and the normals of the outer circle point ''outward'', or vice versa. Otherwise, the distance would be illdefined in the region between the circles. For manifolds which are not closed, the signed distance is ill- defined in any neighborhood of the boundary. However, the distance is well-defined in neighborhoods of the manifold which do not contain the boundary. Problem description The signed distance / to a surface I satisfies the eikonal equation Problem description with boundary conditions / I ¼ 0 (see [59] ). For most boundary conditions, a solution to Eq. 31 exists only in the weak sense. It is continuous, but only piecewise differentiable. The solution is non-differentiable where characteristics intersect. These are places that have multiple closest points to the manifold. At differentiable points on the manifold, the direction of the characteristics of Eq. 31 is given by the local normal on I ; i.e. Ñ//|Ñ/|, and the characteristics are straight lines. Problem description In computing the distance and closest point to a triangle mesh surface, one can consider each component of the mesh (face, edge or vertex) separately. For each entity, there are simple geometric formulas for computing the distance and closest point. For signed distance, one needs to use the surface normals to determine the sign of the distance. The surface normal along an edge is in the direction of the average of the incident face normals. The surface normal at a vertex is a weighted average of the incident face normals. The weighting is proportional to the angle in the face at that vertex. Problem description For the fluid-solid coupling, we only need to determine the distance and closest point information in a narrow band around the interface as the information is only utilized in the ghost cells. Let d be the Cartesian distance such that all ghost cells are within that distance of the interface surface. If the distance is computed up to d, then one can flood fill the distance to determine which of the remaining grid points are inside or outside the solid. Iteration and tree data structures In the simplest algorithm for computing distance / and closest point information C up to a distance d, one loops over all components of the surface mesh I (faces, edges and vertices) and all Cartesian grid points. This straightforward algorithm reads: Iteration and tree data structures The algorithm has computational complexity OðMGÞ; where M is the number of components in the mesh and G is the number of grid points. Since timeexplicit finite volume methods basically have complexity OðGÞ for a single time step, this naive algorithm is not suitable for computing the CPT during the course of a simulation. Iteration and tree data structures An alternative could be to store the mesh in a data structure that supports minimum distance queries, like a bounding box tree [60] . However, the average expected complexity of a single distance or closest point computation in this approach would still be Oðlog MÞ: This implies an overall complexity of OðG log MÞ for the CPT algorithm. By taking advantage of the fact that the grid points of the Cartesian mesh form a lattice, we have been able to develop a CPT algorithm tailored especially for our purposes with better computational complexity. The CSC algorithm One can efficiently compute the distance and closest point on a grid by solving the eikonal equation with the method of characteristics and utilizing polyhedron scan conversion. This is called the characteristics/scan conversion (CSC) algorithm [61] . For a given grid point, the closest point on the triangle mesh lies on one of the primitives (faces, edges and vertices) that comprise the surface. The characteristics emanating from each of these primitives form polyhedral shapes, which we call characteristic polyhedra. A characteristic polyhedron contains all of the points which are possibly closest to its corresponding face, edge or vertex. We determine the grid points that lie within each of these polyhedra, then use simple geometric formulas to calculate distance and closest points for the primitive. The CSC algorithm The closest points to a triangle face must lie within a triangular prism defined by the face and its normal. The prism contains the characteristic lines emanating 1 Flood filling means looping over the grid points while only keeping track of the sign of the distance. from the face (see Fig. 9a for the face polyhedra of an icosahedron). Each edge in the mesh is shared by two faces. The closest points to an edge must lie in a cylindrical wedge defined by the line segment and the normals to the two incident faces, which is depicted in Fig. 9b . A single edge polyhedron is shown in Fig. 9c . Each vertex in the mesh is shared by three or more faces. The closest points to a vertex must lie in a polygonal pyramid defined by the normals to the incident faces. The vertex polyhedra of an icosahedron are displayed in Fig. 9d . We can determine the grid points that lie inside a characteristic polyhedron with polyhedron scan conversion. The polyhedron is first sliced along each sheet of the grid lattice to produce polygons. Polygon scan conversion (or rasterization) is a standard technique in computer graphics for displaying filled polygons on raster displays [62, 63] . It is a method for determining the pixels on the display which lie inside a polygon. Figure 10 depicts polygon scan conversion and slicing of a polyhedron. Utilizing the method of characteristics and scan conversion together, we formulate the algorithm for computing the CPT now as follows: Computational complexity Consider computing the CPT up to a distance of d. If d is small and the surface is smooth, the computational complexity of the algorithm is linear in both the size of the mesh and the number of grid points within d of the surface. Thus, it has the optimal complexity. Computational complexity Let the Cartesian grid have N points within a distance d of the surface, and let m be the ratio of the sum of the volumes of all the scan converted polyhedra divided by the volume of the domain within a distance d of the surface. The ratio m depends on the shape of the surface and the distance d. If the surface is jagged and d is relatively large, then m will be large. If the surface is smooth and d is relatively small, then m will be close to unity. The total computational complexity of the algorithm is OðmN þ MÞ: The OðmNÞ term again comes from scan conversion and the closest point and distance computations for the grid points. The OðMÞ term represents the construction of the characteristic polyhedra. Since we expect both M and N to be small compared to the total number of grid points G, the CSC algorithm is suitable for computing the CPT during the course of a simulation. Computational complexity The CSC algorithm stores the grids for distance and closest point and the mesh for which the CPT is computed. Beyond these data structures, which define the problem, it does not require significant additional storage. The components of the mesh (i.e. the faces, edges and vertices) are dealt with one at a time. The (a) (b) (d) (c) Fig. 9 The characteristic polyhedra for faces, edges, and vertices Fig. 10 Scan conversion of a polygon in 2-D and slicing of a polyhedron to form polygons memory required to scan convert a single polyhedron is insignificant compared to the memory needs of the grid and the mesh. Thus, the CSC algorithm essentially has the minimum storage requirements for the CPT problem. Concurrency and SAMR If the solid mesh (and hence the solid boundary) is distributed over multiple processes, the pieces must be assembled into a cohesive triangle mesh before computing the CPT. This is because one needs to know the incident faces of edges and vertices in order to compute the correct sign of the distance. We accomplish this by maintaining global identifiers for the nodes in the solid mesh. Concurrency and SAMR In the course of a simulation with the SAMR framework sketched in Sect. 2.4, each fluid process performs the sequential CSC algorithm. As we use a rigorous domain decomposition to partition the SAMR hierarchy, only those components of the triangulated surface meshes that are within a distance d of the local domain need to be considered for this computation. The necessary clipping operation is best performed before sending the distributed parts of the solid surface mesh to the receiving fluid processes. The details of our implementation are outlined in Sect. 5.2. Concurrency and SAMR In order to make efficient use of the CPT algorithm within the SAMR method, we have organized our CPT implementation such that the algorithm can be called once for a multitude of subgrids that effectively lie within the same lattice. This arrangement ensures that each characteristic polyhedron is constructed and scan converted only once for each level in the SAMR hierarchy and guarantees computational performance that is basically independent of the number of subgrids. Fluid-structure coupling The explicit fluid and solid solvers are weakly coupled by applying appropriate boundary conditions at the fluid-solid interface I via a time-splitting technique described below. In the case of inviscid flows considered here, these boundary conditions correspond-in the Lagrangian notation of Sect. 3, [14] -to the continuity of the normal component of the velocity field: Fluid-structure coupling and the continuity of the normal component of the traction across the fluid-solid interface, i.e. Fluid-structure coupling In the expressions above, : ½ ½ represents field jumps and u is the velocity which in the solid can be expressed in terms of the deformation mapping u X; t ð Þ as Fluid-structure coupling where t and n are the spatial surface traction and normal vectors, respectively, and r ij are the components of the Cauchy stress tensor as defined in Eq. 11. The resulting boundary conditions at the fluid solid interface are simply Fluid-structure coupling For simplicity, and owing to the extremely short time scales involved in the problems of interest, it is assumed that heat transfer across the fluid-solid interface is negligible and, thus, can be ignored. Fluid-structure coupling The following simple temporal splitting scheme is adopted to accomplish the loose coupling between fluid and solid solver [2] 2 : Fluid-structure coupling We have implemented this algorithm with an ad-hoc partitioning into dedicated fluid and solid processes that communicate to exchange the data along I : In the following subsections we will outline some of the specifics of our approach that make the VTF a highly efficient framework for fluid-structure simulation on distributed memory machines. Coupled simulations with Eulerian SAMR Unsteady compressible fluid flows typically show a wide range of temporal and spatial scales. While the correct numerical representation of supersonic shock and detonation waves usually requires very fine resolution only in a small band around the phenomenon of interest, a considerably coarser resolution is often sufficient in the majority of the fluid domain. This is in particular true in our case of strong pressure waves arising from the detonation of highly energetic materials; one is interested mainly in the stress waves produced by shock impact in the solid target materials and 2 More general implicit and staggering schemes for coupled systems have been proposed and studied in detail in [64, 65] . Coupled simulations with Eulerian SAMR Engineering with Computers (2006) 22:325-347 337 the resulting material response. Hence, incoming fluid waves and the near-body fluid-structure interaction have to be captured with high accuracy, but resolution can be reduced for outgoing fluid phenomena and in the far field. We achieve the required solution adaptation in the fluid by applying the dynamic mesh adaptation algorithm described in Sect. 2.3. The fluidsolid interface I is treated herein as a discontinuity with a-priori refinement at least up to the coupling level l c . As the wave phenomena in solid materials are usually at least as fast as the waves in compressible fluids, the coupling level l c will usually be the highest computationally permissible choice in order to ensure an accurate wave transmission. But special care is required to initiate the data exchange according to the above basic coupling method in a way that is compatible with the recursive SAMR algorithm. The coupled SAMR method is implemented below in the routine advance_level() that calls itself recursively with the current level as argument l: Coupled simulations with Eulerian SAMR The algorithm calls the routine cpt() from Sect. 4.3 to evaluate the signed distance / and the closest point information C for the actual level l based on the currently available interface I : Together with the recent solid velocity on the interface u S j I ; the discrete vector of state in the fluid Q is updated for the entire level with the numerical scheme outlined in Sect. 2.2. The SAMR method then proceeds as usual recursively to higher levels and utilizes the (more accurate) data from the next higher level to correct the values in cells of the current level overlaid by refinement. If level l is the coupling level l c , we use the updated fluid data to evaluate the pressure values to be sent to the solid and to receive an updated interface mesh and velocities u S j I : The recursive order of the SAMR algorithm automatically ensures that updated interface mesh information is available for later time steps on coarser levels and to adjust the grids on level l c dynamically before the current mesh (i.e. the level set information derived from it) is actually used to again advance level l c . In order to achieve a proper matching of communication operations, we start the cycle by posting a receive-message in the routine fluid_step(), which does one fluid time step on level 0, before entering into
{'paper_id': '1949950', 'title': 'A virtual test facility for the efficient simulation of solid material response under strong shock and detonation wave loading', 's2_url': 'https://api.semanticscholar.org/CorpusID:1949950', 'source': 'S2ORC'}