Moderator: Robert Falgout (Lawrence Livermore National Laboratory)
|Abstract: No Abstract
|Mark Ainsworth (University of Strathclyde)
||Optimally Blended Spectral-Finite Element Scheme for Wave Propagation, and Non-Standard Reduced Integration
|Abstract: In an influential article, Marfurt suggested that the best scheme for computational wave propagation would involve an averaging of the consistent and lumped finite element approximations. Many authors have considered how this might be accomplished for first order approximation, but the case of higher orders remained unsolved. We describe recent work on the dispersive and dissipative properties of a novel scheme for computational wave propagation obtained by averaging the consistent (finite element) mass matrix and lumped (spectral element) mass matrix. The objective is to obtain a hybrid scheme whose dispersive accuracy is superior to both of the schemes. We present the optimal value of the averaging constant for all orders of finite elements and proved that for this value the scheme is two orders more accurate compared with finite and spectral element schemes, and, in addition, the absolute accuracy is of this scheme is better than that of finite and spectral element methods.
Joint work with Hafiz Wajid, COMSATS Institute of Technology, Pakistan.
|Blanca Ayuso de Dios (Centre de Recerca Matemàtica )
||Preconditioning Interior Penalty Discontinuous Galerkin Methods
|Abstract: We propose iterative methods for the solution of the linear systems resulting from
Interior Penalty (IP) discontinuous Galerkin (DG) approximations of elliptic problems.
The precoonditioners are derived from a natural decomposition of the DG finite element spaces. We present the convergence analysis of the solvers for both symmetric and non-symmetric IP schemes. Extension to problems with jumps in the coefficients and linear elasticity will also be discussed. We describe in detail the preconditioning techniques for low order (piece-wise linear ) IP methods and we indicate how to proceed in the case of high order (odd degree) approximations. The talk is based on joint works with Ludmil T. Zikatanov from Penn State University (USA).
|Xiao-Chuan Cai (University of Colorado)
||Developing fast and scalable implicit methods for shallow
water equations on cubed-sphere
|Abstract: We are interested in solving coupled systems of partial
differential equations on computers with a large number of processors. With some combinations of domain decomposition and multigrid methods, one can easily
design algorithms that are highly scalable in terms of the
number of linear and nonlinear iterations. However, if the goal is to minimize the
total compute time and keep the near ideal scalability at the
then the task is more difficult. We discuss some recent
solving the shallow water equations on the sphere for the
global climate. This is a joint work with C. Yang.
|Carsten Carstensen (Yonsei University)
||A posteriori error estimator competition for 2nd-order partial differential equations*
|Abstract: Five classes of up to 13 a posteriori error estimators compete in three second-order model
cases, namely the conforming and non-conforming first-order approximation of the Poisson-Problem
plus some conforming obstacle problem.
Since it is the natural first step, the error is estimated in the energy norm exclusively
— hence the competition has limited relevance. The competition allows merely guaranteed
error control and excludes the question of the best error guess.
Even nonsmooth problems can be included. For a variational inequality,
Braess considers Lagrange multipliers and some resulting auxiliary equation to view
the a posteriori error control of the error in the obstacle problem
as computable terms plus errors and residuals in the auxiliary equation.
Hence all the former a posteriori error estimators apply to this nonlinear benchmark
example as well and lead to surprisingly accurate guaranteed upper error bounds.
This approach allows an extension to more general boundary conditions
and a discussion of efficiency for the affine benchmark examples.
The Luce-Wohlmuth and the least-square error estimators win the
competition in several computational benchmark problems.
Novel equilibration of nonconsistency residuals and novel conforming averaging
error estimators win the competition for Crouzeix-Raviart
nonconforming finite element methods.
Our numerical results provide sufficient evidence that guaranteed error control in the
energy norm is indeed possible with efficiency indices between one and two. Furthermore,
accurate error control is slightly more expensive but pays off in all applications under
consideration while adaptive mesh-refinement is sufficiently pleasant as accurate when
based on explicit residual-based error estimates.
Details of our theoretical and empirical ongoing investigations will be found in
the papers quoted below.References:
S. Bartels, C. Carstensen, R. Klose, An
experimental survey of a posteriori Courant finite element
error control for the Poisson equation, Adv. Comput. Math., 15
(2001), pp. 79-106.
C. Carstensen, C. Merdon, Estimator
competition for Poisson problems, J. Comp. Math., 28 (2010),
- C. Carstensen, C. Merdon, Computational
survey on a posteriori error estimators for nonconforming
finite element methods, Part I: Poisson problems (in
- C. Carstensen, C. Merdon, A posteriori error
estimator competition for conforming obstacle problems, Part I:
Theoretical findings (in preparation),
Part II: Numerical results (in preparation)
* This work was supported by DFG Research Center MATHEON and by the World Class University (WCU) program through the National Research Foundation of Korea (NRF) funded by the
Ministry of Education, Science and Technology R31-2008-000-10049-0.
|Robert D. Falgout (Lawrence Livermore National Laboratory)
||Compatible Relaxation in Algebraic Multigrid
|Abstract: Algebraic multigrid (AMG) is an important method for solving the large sparse linear systems that arise in many PDE-based scientific simulation codes. A major component of algebraic multigrid methods is the selection of coarse grids and the construction of interpolation. The idea of compatible relaxation (CR) was introduced by Brandt as a cheap method for measuring the quality of a coarse grid. In this talk, we will review the theory behind CR, describe our CR-based coarsening algorithm, and discuss aspects of the method that require additional development such as coarsening for systems of PDEs. We will also discuss CR's ability to predict the convergence behavior of the AMG method and ideas for improving the accuracy of its predictions. Finally, we will talk about issues of parallelizing these methods to run on massively parallel computers.
|Andreas Frommer (Bergische Universität-Gesamthochschule Wuppertal (BUGH))
||Domain Decomposition for the Wilson Dirac Operator
|Abstract: In lattice QCD, a standard discretization of the Dirac operator is given by the Wilson-Dirac operator, representing a nearest neighbor coupling on a 4d torus with 3x4 variables per grid point. The operator is non-symmetric but (usually) positive definite. Its small eigenmodes are non-smooth due to the stochastic nature of the coupling coefficients. Solving systems with the Wilson-Dirac operator on state-of-the-art lattices, typically in the range of 32-64 grid points in each of the four dimensions, is one of the prominent supercomputer applications today.
In this talk we will describe our experience with the domain decomposition principle as one approach to solve the Wilson-Dirac equation in parallel. We will report results on scaling with respect to the size of the overlap, on deflation techniques that turned out to be very useful for implementations on QPACE, the no 1 top green 500 special purpose computer developed tiogethe with IBM by the SFB-TR 55 in Regensburg and Wuppertal, and on first results on adaptive approaches for obtaining an appropriate coarse system.
|Ronald H.W. Hoppe (University of Houston)
||Projection based model reduction for shape optimization of the Stokes system
|Abstract: The optimal design of structures and systems described by partial differential equations (PDEs) often gives rise to large-scale optimization problems, in particular if the underlying system of PDEs represents a multi-scale, multi-physics problem. Therefore, reduced order modeling techniques such as balanced truncation model reduction, proper orthogonal decomposition, or reduced basis methods are used to significantly decrease the computational complexity while maintaining the desired accuracy of the approximation. In particular, we are interested in such shape optimization problems where the design issue is restricted to a relatively small area of the computational domain. In this case, it appears to be natural to rely on a full order model only in that specific part of the domain and to use a reduced order model elsewhere. An appropriate methodology to realize this idea consists in a combination of domain decomposition techniques and balanced truncation model reduction. We will consider such an approach for shape optimization problems associated with the time-dependent Stokes system and derive explicit error bounds for the modeling error.
As an application in life sciences, we will be concerned with the optimal design of surface acoustic wave driven microfluidic biochips that are used in clinical diagnostics, pharmacology, and forensics for high-throughput screening and hybridization in genomics and protein profiling in proteomics.
|Guido Kanschat (Texas A & M University)
||Discontinuous Galerkin methods for radiative transfer: Some old results and some new results
|Abstract: In the 1970s, discontinuous Galerkin (DG) methods were invented as a
means to solve neutron/radiation transport problems. Their convergence
analysis had been developed by the early 1980s. Between 1989 and 2000
several publications in nuclear engineering suggested, that the method
does not converge in scattering dominated regimes. In this presentation,
we will review these seemingly contradicting results. A first robustness
result requires that the DG finite element space contains an
approximating continuous space. Since this result is not sufficient for
applications, we use the information contained in the analysis to devise
a new DG method, which will converge to the correct solution independent
of the model parameters.
|David L. Keyes (King Abdullah University of Science & Technology)
||Preconditioners for interface problems in Eulerian formulations
|Abstract: Eulerian formulations of problems with interfaces avoid the subtleties
of tracking and remeshing, but do they complicate solution of the
discrete equations, relative to domain decomposition methods that
respect the interface? We consider two different interface problems –
one involving cracking and one involving phase separation. Crack
problems can be formulated by extended finite element methods (XFEM),
in which discontinuous fields are represented via special degrees of
freedom. These DOFs are not properly handled in a typical AMG
coarsening process, which leads to slow convergence. We propose a
Schwarz approach that retains AMG advantages on the standard DOFs and
avoids coarsening the enriched DOFs. This strategy allows reasonably
mesh-independent convergence rates, though the convergence degradation
of the (lower dimensional) set of crack DOFs remains to be addressed.
Phase separation problems can be formulated by the Cahn-Hilliard
approach, in which the level set of a continuous Eulerian field
demarcates the phases. Here, scalable preconditioners follow
naturally, once the subtlety of the temporal discretization is sorted
out. The first project is joint with R. Tuminaro and H. Waisman and
the second with X.-C. Cai and C. Yang.
|Jan Mandel (University of Colorado)
||Coupled atmosphere - wildland fire numerical simulation by WRF-Fire
|Abstract: WRF-Fire consists of a fire-spread model, implemented by the level set method, coupled with the Weather Research and Forecasting model (WRF). In every time step, the fire model inputs the surface wind and outputs the heat flux from the fire. The level set method allows submesh representation of the burning region and flexible implementation of various ignition modes. This presentation will address the numerical methods in the fire module, solving the Hamilton-Jacobi level set equation, modeling real wildfire experiments, and visualization.
Visualizations by Bedrich Sousedik, Erik Anderson, and Joel Daniels.
Modeling of real fires with Adam Kochanski.
Jan Mandel, Jonathan D. Beezley, Janice L. Coen, and Minjeong Kim, Data Assimilation for Wildland Fires: Ensemble Kalman filters in coupled atmosphere-surface models, IEEE Control Systems Magazine 29, Issue 3, June 2009, 47-65
Jan Mandel, Jonathan D. Beezley, and Volodymyr Y. Kondratenko, Fast Fourier Transform Ensemble Kalman Filter with Application to a Coupled Atmosphere-Wildland Fire Model. Anna M. Gil-Lafuente, Jose M. Merigo (Eds.) Computational Intelligence in Business and Economics (Proceedings of the MS'10 International Conference, Barcelona, Spain, 15-17 July 2010), World Scientific, pp. 777-784. Also available at arXiv:1001.1588
|Thomas A. Manteuffel (University of Colorado)
||A Parallel, Adaptive, First-Order System Least-Squares (FOSLS) Algorithm for Incompressible, Resistive Magnetohydrodynamics
|Abstract: Magnetohydrodynamics (MHD) is a fluid theory that describes Plasma Physics by treating the plasma as a fluid of charged particles. Hence, the equations that describe the plasma form a nonlinear system that couples Navier-Stokes with Maxwell's equations. We describe how the FOSLS method can be applied to incompressible resistive MHD to yield a well-posed, H$^1$-equivalent functional minimization.
To solve this system of PDEs, a nested-iteration-Newton-FOSLS-AMG-LAR approach is taken. Much of the work is done on relatively coarse grids, including most of the linearizations. We show that at most one Newton step and a few V-cycles are all that is needed on the finest grid. Estimates of the local error and of relevant problem parameters that are established while ascending through the sequence of nested grids are used to direct local adaptive mesh refinement (LAR), with the goal of obtaining an optimal grid at a minimal computational cost. An algebraic multigrid solver is used to solve the linearization steps.
A parallel implementation is described that uses a binning strategy. We show that once the solution is sufficiently resolved, refinement becomes uniform which essentially eliminates load balancing on the finest grids.
The ultimate goal is to resolve as much physics as possible with the least amount of computational work. We show that this is achieved in the equivalent of a few dozen work units on the finest grid. (A work unit equals a fine grid residual evaluation).
Numerical results are presented for two instabilities in a large aspect-ratio tokamak, the tearing mode and the island coalescence mode.
|Ricardo H. Nochetto (University of Maryland)
||Convergence rates of AFEM with H -1 Data
|Abstract: In contrast to most of the existing theory of adaptive
element methods (AFEM), we design an AFEM for -Δ u =
f with right hand side f in H -1 instead of
two important consequences. First we formulate our AFEM in
natural space for f, which is nonlocal. Second, we show
decay rates for the data estimator are dominated by those
solution u in the energy norm. This allows us to conclude
the performance of AFEM is solely dictated by the
class of u. This is joint work with A. Cohen and R.
|Ana Radovanović (Google Inc.)
||Asymptotically optimal safety stuffing for inventory allocation in display advertising
|Abstract: A widely used model in online advertising industry is the one in which advertisers pre-purchase a reservation package of online inventory on content sites owned by the publishers (e.g., CNN, amazon, etc.). This package consists of specified inventory bundles of various types that are priced differently and differ in various properties including their expected effectiveness (e.g., Click Through Rate). When online advertisers arrive to a publisher, they have a daily budget, desirable duration of the advertising campaign and a performance goal, which is expressed through some target 'effectiveness' of the purchased package. We design a simple and easy to implement online inventory allocation policy and rigorously prove its asymptotically optimal long run performance.The underlying dynamics of the described application has some similarities with bandwidth sharing in communication networks. However, there are intrinsic characteristics that make the problem of impression allocations in online advertising novel from the modeling and analysis perspective. The key difference is a random budget, which translates into random inventory demand. The other important property is that online advertisers do not ask for specific inventory type, but expect some overall effectiveness from the package of purchased inventory. In view of the existing capacity constraints, we propose a simple online inventory allocation rule, which uses 'careful' sizing of safety stocks to deal with the finite inventory capacities. We rigorously prove the long run revenue optimality of our policy in the regime where demand and inventory capacities grow proportionally.Joint work with Assaf Zeevi (Columbia University).
|Ulrich Rüde (Friedrich-Alexander-Universität Erlangen-Nürnberg)
||Towards Exascale Computing: Multilevel Methods and Flow Solvers for Millions of Cores
|Abstract: We will report on our experiences implementing PDE solvers on Peta-Scale computers, such as the 290 000 core IBM Blue Gene system in the Jülich Supercomputing Center. The talk will have two parts, the first one reporting on our Hierarchical Hybrid Grid method, a prototype Finite Element Multigrid Solver scaling up to a trillion (10^12) degrees of freedom on a tetrahedral mesh by using a carefully designed matrix-free implementation. The second part of the talk will present our work on simulating complex flow phenomena using the Lattice-Boltzmann algorithm. Our software includes parallel algorithms for treating free surfaces with the goal of simulating fully resolved bubbly flows and foams. Additionally, we will report on a parallel fluid-structure-interaction technique with many moving rigid objects. This work is directed towards the modeling of particulate flows that we can represent using fully resolved geometric models of each individual particle embedded in the flow. The talk will end with some remarks on the challenges that algorithm developers will be facing on the path to exascale in the coming decade.
|Andreas Michael Veeser (Università di Milano)
||Local and global approximation of gradients with piecewise polynomials
|Abstract: The quality of a finite element solution hinges in particular on the approximation properties of the finite element space. In the first part of this talk we will consider the approximation of the gradient of a target function by continuous piecewise polynomials over a simplicial, 'shape-regular' mesh and prove the following result: the global best approximation error is equivalent to an appropriate sum in terms of the local best approximation errors on the elements, which do not overlap. This means in particular that, for gradient norms, the continuity requirement does not downgrade the local approximation potential on elements and that discontinuous piecewise polynomials do not offer additional approximation power. In the second part of the talk we will discuss the usefulness of this result in the context of adaptive methods for partial differential equations. Joint work with Francesco Mora (Milan).
|Olof B. Widlund (New York University)
||New Domain Decomposition Algorithms from Old
|Abstract: In recent years, variants of the two-level Schwarz algorithm
have been developed in collaboration between Clark Dohrmann
of Sandia-Albuquerque and a group at the Courant Institute.
By a modification of the coarse component of the preconditioner,
borrowed in part from older domain decomposition methods
of iterative substructuring type, the new methods are easier
to implement for general subdomain geometries and can be made
insensitive to large variations on the coefficients of the partial
differential equation across the interface between the subdomains.
After an introduction to the design of these methods, results on
applications to almost incompressible elasticity and Reissner-Mindlin
plates - solved by using mixed finite elements - and problems
posed in H(div) and H(curl) will be discussed. Some of these results
will appear in the doctoral dissertations of Jong Ho Lee and Duk-soon
Oh, two PhD candidates at the Courant Institute.
|Carol S. Woodward (Lawrence Livermore National Laboratory)
||Implicit Solution Approaches: Why We Care and How We Solve the Systems
|Abstract: Parallel computers with large storage capacities have paved the way for increasing both the fidelity and complexity of large-scale simulations. Increasing fidelity leads to tighter constraints on time steps for stability of explicit methods. Increasing complexity tends to also increase the number of physics models and variations in time scales. Providing both a stable solution process which can accurately capture nonlinear coupling between dynamically relevant phenomena while stepping over fast waves or rapid adjustments leads us toward implicit solution approaches.
This presentation provides an overview of issues arising in large- scale, multiphysics simulations and some of the motivators for looking at implicit approaches. We discuss several popular implicit nonlinear solver technologies and show examples of uses of them within the context of problems found in supernova, subsurface simulation, fusion, and nonlinear diffusion problems.