Paper on Pipelined, Flexible Krylov Subspace Methods

Patrick Sanan, Dave May and I submitted a paper entitled

Pipelined, Flexible Krylov Subspace Methods

The abstract reads

We present variants of the Conjugate Gradient (CG), Conjugate Residual (CR), and Generalized Minimal Residual (GMRES) methods which are both pipelined and flexible. These allow computation of inner products and norms to be overlapped with operator and nonlinear or nondeterministic preconditioner application.The methods are hence aimed at hiding network latencies and synchronizations which can become computational bottlenecks in Krylov methods on extreme-scale systems or in the strong-scaling limit. The new variants are not arithmetically equivalent to their base flexible Krylov methods, but are chosen to be similarly performant in a realistic use case, the application of strong nonlinear preconditioners to large problems which require many Krylov iterations. We provide scalable implementations of our methods as contributions to the PETSc package and demonstrate their effectiveness with practical examples derived from models of mantle convection and lithospheric dynamics with heterogeneous viscosity structure. These represent challenging problems where multiscale nonlinear preconditioners are required for the current state-of-the-art algorithms, and are hence amenable to acceleration with our new techniques. Large-scale tests are performed in the strong-scaling regime on a contemporary leadership supercomputer, where speedups approaching, and even exceeding 2x can be observed. We conclude by analyzing our new methods with a performance model targeted at future exascale machines.

Please find the preprint on arxiv.

pyBlaSch – An object-oriented Python code for option pricing with the Black-Scholes equation

pyBlaSch is an open-source Python code demonstrating option valuation via the solution of the Black-Scholes equation

\(\frac{\partial V}{\partial t} + \frac{1}{2}\sigma^2 S^2 \frac{\partial^2 V}{\partial S^2} + rS\frac{\partial V}{\partial S} – rV = 0.\)

It is a parabolic partial differential equation involving the option price \(V,\) the price of the underlying stock \(S,\) the volatility \(\sigma,\) and the risk free rate \(r.\) As it is simple to account for annualized dividend payments \(d\), these are included in the code, too.

Implementation

  • Finite differences discretization of the spatial derivative operators
  • Runge-Kutta schemes for the integration in time (currently first to 4th order low-storage schemes)
  • Currently only simple Dirichlet type boundary conditions are implemented
  • Types of options are European and Binary call/put
  • Derived quantities: Greeks Delta and Gamma, Put-Call parity implied price

The code design follows an object-oriented programming paradigm and was done with extensibility in mind.

Getting the code

pyBlaSch is open-source software licensed under the MIT license and available on Bitbucket at https://bitbucket.org/saschaschnepp/pyblasch.

Solution for a European Call

Solution for a European Call with expiry in one year and a strike of 100.

Book Chapter on the Power of Trefftz Approximations published

Fritz Kretzschmar, Herbert Egger, Farzad Ahmadi, Nabil Nowak, Vadim A. Markel, Igor Tsukerman and myself contributed a chapter entitled

The Power of Trefftz Approximations: Finite Difference, Boundary Difference and Discontinuous Galerkin Methods; Nonreflecting Conditions and Non-Asymptotic Homogenization

to the book Finite Difference Methods,Theory and Applications Volume 9045 of the series Lecture Notes in Computer ScienceThe abstract reads

In problems of mathematical physics, Trefftz approximations by definition involve functions that satisfy the differential equation of the problem. The power and versatility of such approximations is illustrated with an overview of a number of application areas: (i) finite difference Trefftz schemes of arbitrarily high order; (ii) boundary difference Trefftz methods analogous to boundary integral equations but completely singularity-free; (iii) Discontinuous Galerkin (DG) Trefftz methods for Maxwell’s electrodynamics; (iv) numerical and analytical nonreflecting Trefftz boundary conditions; (v) non-asymptotic homogenization of electromagnetic and photonic metamaterials.

Please find the chapter online.

Paper on the A priori error analysis of space-time Trefftz discontinuous Galerkin methods for wave problems

Fritz Kretzschmar, Andrea Moiola, Ilaria Perugia and I prepared a paper on the a priori error analysis of space-time Trefftz discontinuous Galerkin methods for wave problems.

The abstract reads

We present and analyse a space-time discontinuous Galerkin method for wave propagation problems. The special feature of the scheme is that it is a Trefftz method, namely that trial and test functions are solution of the partial differential equation to be discretised in each element of the (space-time) mesh. The method considered is a modification of the discontinuous Galerkin schemes of Kretzschmar et al., and of Monk and Richter. For Maxwell’s equations in one space dimension, we prove stability of the method, quasi-optimality, best approximation estimates for polynomial Trefftz spaces and (fully explicit) error bounds with high order in the meshwidth and in the polynomial degree. The analysis framework also applies to scalar wave problems and Maxwell’s equations in higher space dimensions. Some numerical experiments demonstrate the theoretical results proved and the faster convergence compared to the non-Trefftz version of the scheme.

Please find the preprint on arXiv.

For more information on the DG Trefftz method please see the posts tagged Trefftz DG.

EDIT Oct/28/2015: The paper got accepted by IMA Journal of Numerical Analysis
EDIT Dec/18/2015: Please find the final paper online.

Paper on A Space-Time Discontinuous Galerkin Trefftz Method for the Time-Dependent Maxwell’s Equations

Fritz Kretzschmar, Herbert Egger, Thomas Weiland and I submitted a paper on a space-time discontinuous Galerkin Trefftz method for the time-dependent Maxwell’s equations. Trefftz methods require the basis functions to fulfill the underlying PDEs in an exact sense. Consequently, vectorial basis functions in a space-time setting have to be considered. It is shown that we obtain a largely reduced number of degrees of freedom.

EDIT: The paper was published in the SIAM Journal on Scientific Computing (SISC) 37(5).

The abstract reads

We consider the discretization of electromagnetic wave propagation problems by a discontinuous Galerkin method based on Trefftz polynomials. This method fits into an abstract framework for space-time discontinuous Galerkin methods for which we can prove consistency, stability, and energy dissipation without the need to completely specify the approximation spaces in detail. Any method of such a general form results in an implicit time-stepping scheme with some basic stability properties. For the local approximation on each space-time element, we then consider Trefftz polynomials, i.e., the subspace of polynomials that satisfy Maxwell’s equations exactly on the respective element. We present an explicit construction of a basis for the local Trefftz spaces in two and three dimensions and summarize some of their basic properties. Using local properties of the Trefftz polynomials, we can establish the well-posedness of the resulting discontinuous Galerkin Trefftz method. Consistency, stability, and energy dissipation then follow immediately from the results about the abstract framework. The method proposed in this paper therefore shares many of the advantages of more standard discontinuous Galerkin methods, while at the same time, it yields a substantial reduction in the number of degrees of freedom and the cost for assembling. These benefits and the spectral convergence of the scheme are demonstrated in numerical tests.

Please find the preprint on arXiv.

For more information on the DG Trefftz method please see also our previous paper, which includes the exact treatment of inhomogeneous materials in partially filled cells as immersed boundaries and this link regarding transparent boundary conditions.

UPDATE May, 28, 2015: The paper was accepted.