Numerical Analysis Archives for Academic Year 2017

Waves in viscoelastic media

When: Tue, September 5, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Francisco-Javier Sayas (Department of Mathematical Sciences, University of Delaware) -
Abstract: I will explain ongoing work with my team (Tom Brown, Shukai Du, and Hasan Eruslu) on Finite Element simulation of elastic wave propagation in media that are modeled using a strain-to-stress relation that keeps track of the past evolution of the solid. The family of models I will discuss includes the classical (Zener) differential viscoelastic model, a fractional derivative version thereof, and combinations of the above with pure elastic behavior. The analysis will be presented using transfer function techniques, but I will explain how in some cases refined results can be found using techniques of semigroup theory.

Finite element approximation of nonconvex uniformly elliptic fully nonlinear equations

When: Tue, September 12, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Abner J. Salgado (University of Tennessee, Knoxville) -
Abstract: We propose and analyze a two-scale finite element method for the Isaacs equation. By showing the consistency of the approximation and that the method satisfies the discrete maximum principle we establish convergence to the viscosity solution. By properly choosing each of the scales, and using the recently derived discrete Alexandrov Bakelman Pucci estimate we can deduce rates of convergence.

An angular momentum method for approximating wave maps into the sphere

When: Tue, September 19, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Franziska Weber (Department of Mathematics, University of Maryland, College Park) -
Abstract: We present a convergent finite difference method for approximating wave maps into the sphere. The method is based on a reformulation of the second order wave map equation as a first order system by using the angular momentum as an auxiliary variable. This enables us to preserve the length constraint as well as the energy inherit in the system of equations at the discrete level. The method is shown to converge to a weak solution of the wave map equation as the discretization parameters go to zero. Moreover, it is fast in the sense that O(N log N) operations are required in each time step (where N is the number of grid cells) and a linear CFL-condition is sufficient for stability and convergence. The performance of the method is illustrated by numerical experiments.

The method can be extended to a convergent scheme for the damped wave map equation and the heat map flow. If time permits, I will also discuss possible extensions of the method to applications for liquid crystal dynamics.

An optimal adaptive Fictitious Domain Method

When: Thu, October 5, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Rob Stevenson (University of Amsterdam) -
Abstract: We consider a Fictitious Domain formulation of an elliptic PDE, and solve the arising saddle-point problem by an inexact preconditioned Uzawa iteration.
Solving the arising `inner' elliptic problems with an adaptive finite element method, we prove that the overall method converges with the best possible rate.
So far our results apply to two-dimensional domains and lowest order finite elements (continuous piecewise linears on the fictitious domain, and piecewise constants on the boundary of the physical domain).

Joint work with S. Berrone (Torino), A. Bonito (Texas A&M), and M. Verani (Milano).

Adaptive Higher-Order Finite Element Simulations for the Time-Harmonic Maxwell Equations

When: Tue, October 10, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Matthias Maier (University of Minnesota) -
Abstract: In the terahertz frequency range, the effective (complex-valued) surface conductivity of atomically thick 2D materials such as graphene has a positive imaginary part that is considerably larger than the real part. This feature allows for the propagation of slowly decaying electromagnetic waves, called surface plasmon-polaritons (SPPs), that are confined near the material interface with wavelengths much shorter than the wavelength of the free-space radiation. SPPs are promising ingredients in the design of novel optical applications promising "subwavelength optics" beyond the diffraction limit. There is a compelling need for controllable numerical schemes which, placed on firm mathematical grounds, can reliably describe SPPs in a variety of geometries.

In this talk we present a higher-order finite element approach for the simulation of SPP structures on a conducting sheet, excited by a plane-wave or electric Hertzian dipole sources. Aspects of the numerical treatment such as absorbing, perfectly matched layers, local refinement and a-posteriori error control are discussed. Corresponding analytical results are briefly presented as well.

A Finite Element Scheme for a Phase Field Model of Nematic Liquid Crystal Droplets

When: Tue, October 17, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Shawn Walker (Louisiana State University) -
Abstract: We present a phase field model for nematic liquid crystal droplets. Our model couples the Cahn-Hilliard equation to Ericksen's one constant model for liquid crystals with variable degree of orientation. We present a special discretization of the liquid crystal energy that can handle the degenerate elliptic part without regularization. In addition, our discretization uses a mass lumping technique in order to handle the unit length constraint. Discrete minimizers are computed via a discrete gradient flow. We prove that our discrete energy Gamma-converges to the continuous energy and our gradient flow scheme is monotone energy decreasing. Numerical simulations will be shown in 2-D to illustrate the method. This work is joint with Amanda Diegel (post-doc at LSU).

Near the end of the talk, I will discuss 3-D simulations of the Ericksen model coupled to the Allen-Cahn equations (with a mass constraint). This work is joint with REU 2017 students (E. Seal and A. Morvant).

A new and robust approach to construct energy stable schemes for gradient flows

When: Tue, October 24, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Jie Shen (Purdue University) -
Abstract: We propose a new technique, the single auxiliary variable (SAV) approach, to deal with nonlinear terms in a large class of gradient flows. The technique is not restricted to specific forms of the nonlinear part of the free energy, it leads to linear and unconditionally energy stable second-order (or higher-order with weak stability conditions) schemes which only require solving decoupled linear equations with constant coefficients. Hence, these schemes are extremely efficient as well as accurate.

We apply the SAV approach to deal with several challenging applications which can not be easily handled by existing approaches, and present convincing numerical results to show that the new schemes are not only much more efficient and easy to implement, but also can better capture the physical properties in these models.

Adaptive FEM for the fractional Laplacian: a priori and a posteriori error estimates, efficient implementation and multigrid solver

When: Tue, October 31, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Christian Glusa (Sandia National Laboratories) -
Abstract: We explore the connection between fractional order partial differential
equations in two or more spatial dimensions with boundary integral
operators to develop techniques that enable one to efficiently tackle
the integral fractional Laplacian. We develop all of the components
needed to construct an adaptive finite element code that can be used to
approximate fractional partial differential equations, on non-trivial
domains in \(d\geq 1\) dimensions. Our main approach consists of taking
tools that have been shown to be effective for adaptive boundary element
methods and, where necessary, modifying them so that they can be applied
to the fractional PDE case. Improved a priori error estimates are
derived for the case of quasi-uniform meshes which are seen to deliver
sub-optimal rates of convergence owing to the presence of singularities.
Attention is then turned to the development of an a posteriori error
estimate and error indicators which are suitable for driving an adaptive
refinement procedure. We assume that the resulting refined meshes are
locally quasi-uniform and develop efficient methods for the assembly of
the resulting linear algebraic systems and their solution using
iterative methods, including the multigrid method. The storage of the
dense matrices along with efficient techniques for computing the dense
matrix vector products needed for the iterative solution is also
considered. Importantly, the approximation does not make any strong
assumptions on the shape of the underlying domain and does not rely on
any special structure of the matrix that could be exploited by fast
transforms. The performance and efficiency of the resulting algorithm is
illustrated for a variety of examples.

This is joint work with Mark Ainsworth, Brown University.

Optimal Estimation and Computation from Data

When: Tue, November 7, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Simon Foucart (Texas A&M University) -
Abstract: Scientific problems often feature observational data received in the form $w_1=l_1(f), \ldots$, $w_m=l_m(f)$ of known linear functionals applied to an unknown function $f$ from some Banach space $\mathcal{X}$, and it is required to either approximate $f$ (the full approximation problem) or to estimate a quantity of interest $Q(f)$. In typical examples, the quantities of interest can be the maximum/minimum of $f$ or some averaged quantity such as the integral of $f$, while the observational data consists of point evaluations. To obtain meaningful results about such problems, it is necessary to possess additional information about $f$, usually as an assumption that $f$ belongs to a certain model class $\mathcal{K}$ contained in $\mathcal{X}$. This is precisely the framework of optimal recovery, which produced substantial investigations when the model class is a ball of a smoothness space, e.g. when it is a Lipschitz, Sobolev, or Besov class. This presentation concentrates on other model classes described by approximation processes. The main innovations are:
(i) for the estimation of quantities of interest, the production of numerically implementable algorithms which are optimal over these model classes,
(ii) for the full approximation problem, the construction of linear algorithms which are optimal or near optimal over these model classes in case of data consisting of point evaluations.
Regarding (i), when $Q$ is a linear functional, the existence of linear optimal algorithms was established by Smolyak, but the proof was not numerically constructive. In classical recovery settings, it is shown here that such linear optimal algorithms can be produced by constrained minimization methods, and examples involving the computations of integrals from the given data are examined in greater details. Regarding (ii), it is shown that linearization of optimal algorithms can be achieved for the full approximation problem, too, in the important situation where the $l_j$ are point evaluations and $\mathcal{X}$ is a space of continuous functions equipped with the uniform norm. It is also revealed how the quasi-interpolation theory allows for the construction of linear algorithms which are near optimal.

Numerical computations with functions defined on the sphere and disk

When: Tue, November 14, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Alex Townsend (Cornell University) -
Abstract: A classical technique for computing with functions on the sphere and disk is to "double up" the domain, leading to regularity preserving approximants. We synthesize this with new techniques for constructing low rank function approximations to develop a whole collection of fast and adaptive algorithms for sphere and disk computations that are accurate to machine precision. Applications include vector calculus, the solution of PDEs, and the long-time simulation of active biological fluids. This is joint work with Heather Wilber and Grady Wright from Boise State University.

Energy-Minimization, Finite Elements, and Multilevel Methods for Liquid Crystals

When: Tue, December 5, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: James Adler (Tufts University Department of Mathematics) -
Abstract: Liquid crystals are substances that possess mesophases with properties intermediate between liquids and crystals, existing at different temperatures or solvent concentrations. We consider two types of liquid crystals in this talk, nematic and cholesteric, which are formed by rod-like molecules that self-assemble into an ordered structure, such that the molecules tend to align along a preferred orientation. The preferred average direction at any point in a domain is known as the director and is taken to be of unit length at every point in the domain. In addition to their inherent structure, which is affected both by the self-assembly and boundary affects, most liquid crystals are responsive to electric fields and may be compelled to arrange their structure in new ways by the presence of these fields. Simulating this realignment from all of these factors is crucial for understanding many applications where such switching is useful, such as energy generators and actuators.

The main focus of this talk will be on the computational modeling of equilibrium configurations for liquid crystals influenced by elastic and electric effects. Thus, the method targets minimization of the system free energy based on the so-called Frank-Oseen free-energy model, subject to the unit-length constraint of the director. We consider an energy-minimization finite-element approach to discretize the constrained optimization problem along with Newton's method to linearize the system. We are able to show that solutions to the intermediate discretized linearizations exist generally and are unique under certain assumptions. Numerical experiments are performed for problems with a range of Frank elastic constants as well as simple and patterned boundary conditions. The resulting algorithm accurately handles heterogeneous Frank constants and efficiently resolves configurations resulting from complicated boundary conditions relevant in ongoing research. Additionally, we present techniques to handle situations in which multiple equilibrium states can arise. This involves the incorporation of multilevel and nonlinear deflation techniques to solve the resulting linear systems.

Analyzing Complex Systems and Networks: Incremental Optimization and Robustness

When: Tue, December 12, 2017 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Mert Gurbuzbalaban (Rutgers University) -

Many of the emergent technologies and systems including infrastructure systems (communication, transportation and energy systems) and decision networks (sensor and robotic networks) require rapid processing of large data and comprise dynamic interactions that necessitate robustness to small errors, disturbances or outliers.
Motivated by large-scale data processing in such systems, we first consider additive cost convex optimization problems (where each component function of the sum represents the loss associated to a data block) and propose and analyze novel incremental gradient algorithms which process component functions sequentially and one at a time, thus avoiding costly computation of a full gradient step. We focus on two randomized incremental methods, Stochastic Gradient Descent (SGD) and Random Reshuffling (RR), which have been the most widely used optimization methods in machine learning practice since the fifties. The only difference between these two methods is that RR samples the component functions without-replacement whereas SGD samples with-replacement. Much empirical evidence suggested that RR is faster than SGD, although no successful attempt has been made to explain and quantify this discrepancy for a long time. We provide the first theoretical convergence rate result of O(1/k2s) for any s in (1/2,1) (and O(1/k2) for a bias-removed novel variant) with probability one for RR showing its improvement over Ω(1/k) rate of SGD and highlighting the mechanism for this improvement. Our result relies on a detailed analysis of deterministic incremental methods and a careful study of random gradient errors. We then consider deterministic incremental gradient methods with memory and show that they can achieve a much-improved linear rate using a delayed dynamical system analysis.

In the second part, we focus on large-scale continuous-time and discrete-time linear dynamical systems that model various interactions over complex networks and systems. There are a number of different metrics that can be used to quantify the robustness of such dynamical systems with respect to input disturbance, noise or error. Some key metrics are the H-infinity norm and the stability radius of the transfer matrix associated to the system. Algorithms to compute these metrics exist, but they are impractical for large-scale complex networks or systems where the dimension is large and they do not exploit the sparsity patterns in the network structure. We develop and analyze the convergence of a novel scalable algorithm to approximate both of the metrics for large-scale sparse networks. We then illustrate the performance of our method on numerical examples and discuss applications to design optimal control policies for dynamics over complex networks and systems.

Taking Mathematics to Heart [special Math Colloquium]

When: Fri, February 2, 2018 - 3:15pm
Where: Kirwan Hall 3206
Speaker: Alfio Quarteroni (Politecnico di Milano, Milan, Italy and EPFL, Lausanne, Switzerland ) -
Abstract: In this presentation I will highlight the great potential offered by the interplay between data science and computational science to efficiently solve real life large scale problems . The leading application that I will address is the numerical simulation of the heart function.
The motivation behind this interest is that cardiovascular diseases unfortunately represent one of the leading causes of death in Western Countries.
Mathematical models based on first principles allow the description of the blood motion in the human circulatory system, as well as the interaction between electrical, mechanical and fluid-dynamical processes occurring in the heart. This is a classical environment where multi-physics processes have to be addressed.

Appropriate numerical strategies can be devised to allow for an effective description of the fluid in large and medium size arteries, the analysis of physiological and pathological conditions, and the simulation, control and shape optimization of assisted devices or surgical prostheses.
This presentation will address some of these issues and a few representative applications of clinical interest.

Defects in periodic homogenization problems : Toward a complete theory [Appl. Math. Colloquium]

When: Tue, February 6, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Claude Le Bris (Ecole des Ponts and Inria) -
Abstract: We will present some recent mathematical contributions related to nonperiodic homogenization problems. The difficulty stems from the fact that the medium is not assumed periodic, but has a structure with a set of embedded localized defects, or more generally a structure that, although not periodic, enjoys nice geometrical features. The purpose is then to construct a theoretical setting providing an efficient and accurate approximation of the solution. The questions raised ranged from the theory of elliptic PDEs, homogenization theory to harmonic analysis and singular operators.

Mathematical theory and computational approaches for modern materials science [Aziz Lecture]

When: Wed, February 7, 2018 - 3:15pm
Where: Kirwan Hall 3206
Speaker: Claude Le Bris (Ecole des Ponts and Inria) -
Abstract: The talk, intended for a general audience, will survey some challenging mathematical and numerical problems in contemporary materials science. Questions such as the passage from the microscale to the macroscale, the insertion of uncertainties, defects and heterogeneities in the models, will be examined. We will discuss the interesting issues raised for mathematical analysis (theory of partial differential equations, stochastic processes, homogenization theory) and for numerical analysis (finite element methods, discrete to continuum, Monte Carlo methods, etc).

A Conformal Mapping Formulation For Inviscid Incompressible Fluid Drops and its Numerical Analysis

When: Tue, February 13, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Lei Li (Department of Mathematics, Duke University) -
Abstract: We study incompressible, irrotational flows of an inviscid fluid with free surface in planar domains conformally equivalent to a disk. I will talk about some properties of the equations under the conformal mapping formulation, which is the geodesic of a Riemannian structure. In particular, linearization of the equations shows a nonlocal hyperbolic structure, which ensures linear stability. I will then describe a filtered-Fourier pseudospectral method for numerical simulation. The convergence of the numerical schemes is then proved making use of the hyperbolic structure.
This is a joint work with Jian-Guo Liu and Robert Pego.

Nonconforming Finite Element Methods for High Order Elliptic Equations in $\mathbb{R}^n$

When: Tue, February 20, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Shuonan Wu (Penn State University) -
Abstract: In this talk, we propose two families of nonconforming finite element methods for 2m-th order elliptic equations in $\mathbb{R}^n$ on simplicial grids. Both of them naturally extend the methods proposed by Wang and Xu [Math. Comp. 82(2013), pp. 25--43], where m = 0, n >= 1, introduces some interior penalty terms to the bilinear form when $m > n$. The shape function space of nonconforming element consists of all polynomials with a degree not greater than m and is hence minimal. The nonconforming finite element spaces have some natural inclusion properties as in the corresponding Sobolev spaces in the continuous cases. We establish quasi-optimal error estimates in the energy norm for both of them, provided that the corresponding conforming relatives exist. These theoretical results are further validated by the numerical tests. Besides, we propose an $H^3$ nonconforming finite element that is robust for the sixth order singularly perturbed problems in 2D, which is of practical interest to the mathematical models containing small parameters.

Nonlocal transport modeling: statistical foundations and applications

When: Tue, March 6, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Diego Del-Castillo-Negrete (Oak Ridge National Laboratory)

Abstract: Transport modeling is a key element of applied sciences and engineering, and a fertile area of applied mathematics. In the past, a significant amount of work has been devoted to models formulated in terms of local partial differential equations (e.g., linear and nonlinear advection-diffusion type equations). However, relatively recently there has been growing experimental and theoretical evidence that these models fail to describe anomalous non-diffusive transport (e.g., super-diffusive and sub-diffusive transport). To describe these phenomena, nonlocal models introduce nonlocal flux-gradient relations and formulate transport in terms of partial integro-differential equations. The goal of this lecture is to present a tutorial introduction to nonlocal transport modeling with emphasis on applications. We will start with an overview of nonlocal (in space and time) transport, and the statistical foundations of nonlocal models based on the theory of continuous time random walks driven by general Levy processes. Following this, we will review several applications including: (i) Nonlocal particle and heat transport in fluids and plasmas; (ii) Fluctuation-driven transport in the nonlocal Fokker-Planck equation (e.g., Levy ratchets); (iii) Nonlocal reaction diffusion systems (e.g., front acceleration in the nonlocal Fisher-Kolmogorov equation); (iv) Nonlocal models of option prices in markets with jumps based on the fractional Black-Scholes equation.

The shifted boundary method: An embedded approach for computational mechanics

When: Tue, March 27, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Guglielmo Scovazzi (Duke University) -

Abstract: Embedded boundary methods obviate the need for continual re-meshing in many applications involving rapid prototyping and design. Unfortunately, many finite element embedded boundary methods for incompressible flow are also difficult to implement due to the need to perform complex cell cutting operations at boundaries, and the consequences that these operations may have on the overall conditioning of the ensuing algebraic problems. We present a new, stable, and simple embedded boundary method, which we call “shifted boundary method” (SBM), that eliminates the need to perform cell cutting. Boundary conditions are imposed on a surrogate discrete boundary, lying on the interior of the true boundary interface. We then construct appropriate field extension operators, with the purpose of preserving accuracy when imposing the boundary conditions. We demonstrate the SBM on large-scale incompressible flow problems, multiphase flow problems, solid mechanics problems, and shallow water flow problems.

Positivity-preserving high order discontinuous Galerkin schemes for compressible Navier-Stokes equations

When: Tue, April 3, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Xiangxiong Zhang (Purdue University) -
Abstract: For gas dynamics equations such as compressible Euler and Navier-Stokes equations, preserving the positivity of density and pressure without losing conservation is crucial to stabilize the numerical computation. The L1-stability of mass and energy can be achieved by enforcing the positivity of density and pressure during the time evolution. However, high order schemes such as DG methods do not preserve the positivity. It is difficult to enforce the positivity without destroying the high order accuracy and the local conservation in an efficient manner for time-dependent gas dynamics equations. For compressible Euler equations, a weak positivity property holds for any high order finite volume type schemes including DG methods, which was used to design a simple positivity-preserving limiter for high order DG schemes by Zhang and Shu in 2010. Generalizations to compressible Navier-Stokes equations are however nontrivial. We show that weak positivity property still holds for DG method solving compressible Navier-Stokes equations if a proper penalty term is added in the scheme. This allows us to obtain the first high order positivity-preserving schemes for compressible Navier-Stokes equations.

An accurate and fast solver for high-frequency wave propagation

When: Tue, April 10, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Matthias Taus (MIT) -
Abstract: In science and engineering, the fast and accurate solution of high-frequency wave propagation problems in highly heterogeneous media is of extremely high interest. For example, these problems are a crucial part in inverse problems for oil exploration. In this context, it is important to solve the problem not only accurately but also fast. Recently, there have been many advances in the development of fast solvers (linear complexity with respect to the number of degrees of freedom). While most of those methods only scale optimally in the context of low-order discretizations and smooth wave speed distributions, the Method of Polarized Traces has been shown to be the only method that scales optimally for high-order discretizations and highly heterogeneous (and even discontinuous) wave speed distributions.

In this work, we show that the combination of Hybridizable Discontinuous Galerkin (HDG) Methods and the Method of Polarized Traces results in an accurate and fast solver for high frequency wave propagation in highly heterogeneous media. In particular, we show that on a uniform mesh, HDG methods are second order accurate, can be made pollution free, and can be solved in O(N) time where N is the number of total degrees of freedom. We concentrate on the aspects of discretization and its use in the context of the Method of Polarized Traces. However, our approach also shows a lot of inherent parallelism which can be used for further speed-up.

We motivate and introduce the new method and corroborate our claims using geophysical numerical examples.

Rate optimal adaptivity and LU-factorization

When: Tue, April 24, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Michael Feischl (KIT Karlsruhe) -
Abstract: We develop a framework which allows us to prove the essential general quasi-orthogonality for non-symmetric and indefinite problems as the stationary Stokes problem or certain transmission problems. General quasi-orthogonality is a necessary ingredient of rate optimality proofs and is the major difficulty on the way to prove rate optimal convergence of adaptive algorithms for many strongly non-symmetric or indefinite problems. The proof exploits a new connection between the general quasi-orthogonality and LU-factorization of infinite matrices.

Approximation diffusion and fluid limits for random kinetic equations [Appl Math Colloquium]

When: Tue, May 1, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Arnaud Debussche (ENS Rennes) -
Abstract: In this talk, I consider kinetic equations containing random terms. The kinetic models contain a small parameter and it is wellknown that, after parabolic rescaling, when this parameter goes to zero the limit problem is a diffusion equation in the PDE sense, ie a parabolic equation of second order. A smooth noise is added, accounting for external perturbation. It scales also with the small parameter. It is expected that the limit equation is then a stochastic parabolic equation where the noise is in Stratonovitch form.
Our aim is to justify in this way several SPDEs commonly used. We first treat linear equations with multiplicative noise. Then show how to extend the methods to some nonlinear equations or to the more physical case of a random forcing term. The method is to combine the classical perturbed test function method with PDE argument.

Butterflies in layered media

When: Tue, May 8, 2018 - 3:30pm
Where: Kirwan Hall 3206
Speaker: Nick Knight (New York University) -

Abstract: Using a combination of physical-domain and Fourier-domain integral representations, we present an iterative algorithm for solving the two-dimensional Helmholtz equation in layered media geometries. The scheme is accelerated by use of a butterfly algorithm, which allows for nearly optimal $O(N \log^2 N)$ asymptotic scaling in the high-frequency limit.