# Integral Equations Methods: Fast Algorithms and Applications (13w5044)

Arriving in Banff, Alberta Sunday, December 8 and departing Friday December 13, 2013

## Organizers

Alexander Barnett (Dartmouth College)

Leslie Greengard (New York University)

Shidong Jiang (New Jersey Institute of Technology)

Mary Catherine Kropinski (Simon Fraser University)

Per-Gunnar Martinsson (University of Colorado, Boulder)

Vladimir Rokhlin (Yale University)

## Objectives

Progress in science and engineering today is largely driven by the rapidly expanding capabilities for computational simulation. The objective of the proposed workshop is to accelerate this progress for some of the core problems arising in electromagnetics, acoustics, solid and fluid mechanics, molecular dynamics, quantum physics and chemistry, and astrophysics. Specifically, the focus will be on development and implementation of highly effective and robust methods for solving linear boundary value problems associated with the Laplace and Helmholtz equations, the equations of elasticity, the time-harmonic Maxwell equations, the Stokes equation, and many more. Many of these equations have already been solved extremely efficiently via techniques based on integral equations and analysis-based fast solvers such as the Fast Multipole Method (FMM). For such problems, this has proven to be game changing: FIEM have enabled the accurate solution of problems far larger than what had previously been imagined possible. We aim to expand on this success.

In recent years, several advances have raised the possibility that the exceptional performance demonstrated in certain super-computing settings can be made accessible to a much broader audience of researchers relying on scientific computing in their work. Specific advances include:

• FAST OPERATOR ALGEBRA: The first generation of analysis-based fast algorithms provided tools, such as the FMM, for rapidly applying certain integral operators. These are highly efficient but are limited to a narrow class of operators. In the last ten years, it has been demonstrated that in addition to merely applying an operator rapidly, one can also accelerate the multiplication of operators, inversion of operators, and even computing full or partial spectral decompositions. Thus, it is now possible to handle a much broader class of operators than was previously thought possible.

• INEXPENSIVE STORAGE AND MULTICORE PROCESSORS: Computing architecture is rapidly changing. While it used to be the case that storage and the cost of a single floating-point operation were the principal limiting factors, communication is now emerging as the principal constraint. The reason is the move to parallel and distributed computing, which in turn is driven by the stagnating clock-speed of processors coupled with a shrinking cost per processor. The most extreme manifestation of this shift is perhaps the emergence of components like Graphics Processing Units (GPUs), which contain a very large number of cores each having limited capabilities. The changing computing environment is making many of the currently used numerical algorithms uncompetitive. This creates a demand for new algorithms that are designed from scratch to minimize communication, rather than the number of floating point operations required.

• RANDOMIZED ALGORITHMS IN NUMERICAL LINEAR ALGEBRA: It has recently been demonstrated that approximate factorizations of matrices of numerically low rank can be constructed very efficiently via certain randomized sampling procedures. This work draws on random matrix theory, functional analysis, and linear algebra, and furnishes computational techniques that are highly efficient, robust, versatile, and of intrinsic mathematical interest. Since many analysis-based fast algorithms rely on the hierarchical splitting of a large matrix into submatrices of numerically low rank, there is an obvious opportunity to incorporate the new randomized sampling algorithms into the fast operator algebra methods to achieve even faster and more versatile algorithms.

• IMPROVED SURFACE REPRESENTATIONS AND DISCRETIZATIONS: Real-world applications often involve curves and surfaces with (sometimes thousands of) corners and edges: the interaction of such geometry with the singular kernels of integral operators poses a challenge to accurate solution, particularly in three dimensions. There has been recent progress on high-order surface representations, on the automatic generation of efficient and well-conditioned quadrature schemes for discretizing integral equations, and on evaluation of potential fields close to their sources.

• NEW AND EXPANDING AREAS OF APPLICATION: Many of the FIEM developed for the classical equations in mathematical physics have increasingly been used as building blocks for solving much more complicated boundary value problems. FIEM have now started to compete with finite element and finite differences in simulating complex systems in science and engineering.

• NEW MATHEMATICAL FORMULATIONS OF KEY BOUNDARY VALUE PROBLEMS: There have been recent breakthroughs in creating a well-conditioned mathematical formulation of the scattering problem for time-harmonic Maxwell equations, in the representation of problems in periodic geometries, and deriving second-kind integral equations for high-order systems of PDEs. Such analytically sound formulations are key to creating software packages that are robust at all user parameters.

Recent hardware developments (GPUs, increased storage capacity, distributed computing, etc) have put us in a position where we could soon see such methods being mainstreamed to the point where it would be possible to perform complex 3D simulations in close to real time on a desktop machine. The impact of such a development would be profound.

A BIRS workshop would be an ideal vehicle for advancing progress in this field. It would achieve several key objectives:

• FACILITATING INTERDISCIPLINARY RESEARCH: The advances listed above have occurred in quite disparate fields (computer engineering, numerical analysis, functional analysis, probability theory, etc). A 5-day workshop in an intimate setting is an ideal way of bringing researchers from the different fields together.

• CONNECT ALGORITHM DEVELOPERS AND USERS: For algorithmic development to reach its full potential impact, it is essential that the actual intended users be involved from the beginning. Our proposed list of invitees has such a mix of developers and users.

• DEVELOP YOUNG TALENT: The workshop is intended to inspire and motive younger researchers in the field, and to attract some of the most promising new talent to work on a set of problems that combine mathematical depth and elegance with the potential to make a very substantial difference to our ability to simulate large and complex physical systems.

The workshop would be structured to organize the scientific discussion around three main themes, which are outlined below:

1. Mathematical Foundations of Fast Algorithms.

A discussion of recent advances, possibilities for combining the new techniques, and an exploration of future development. Topics to be discussed could include: finding stable integral equations for a broad range of boundary value problems, methods for handling surfaces with corners and edges, high-order methods for representing surfaces, fast operator algebra and direct solvers, randomized methods.

2. Applications of FIEM including modeling planet earth

In keeping with the theme Mathematics of Planet Earth, topical applications will include earthquake simulation, radar scattering for remote sensing, optical devices for solar energy, renewable energy, and oceanic vortex dynamics in the presence of geography.

3. Software, Parallelization of Fast Algorithm Libraries

Efficient parallelization techniques for algorithms based on adaptive tree structures, computing on GPUs, formulation of standardized test problems and user interfaces, and current issues in improving solvers’ accuracy and efficiency.

The format of the workshop will consist of research seminars focusing on recent advances and poster presentations. In addition, we plan to hold a forum to address the special needs of graduate students, and to provide guidance on prerequisites and possible research directions in our identified themes. We will also plan for unstructured time in order to allow brainstorming by participants on important open problems, such as high-order, adaptive, surface representations, non-constant coefficient and nonlinear PDEs, and well-conditioned formulations for complex systems of equations.

In recent years, several advances have raised the possibility that the exceptional performance demonstrated in certain super-computing settings can be made accessible to a much broader audience of researchers relying on scientific computing in their work. Specific advances include:

• FAST OPERATOR ALGEBRA: The first generation of analysis-based fast algorithms provided tools, such as the FMM, for rapidly applying certain integral operators. These are highly efficient but are limited to a narrow class of operators. In the last ten years, it has been demonstrated that in addition to merely applying an operator rapidly, one can also accelerate the multiplication of operators, inversion of operators, and even computing full or partial spectral decompositions. Thus, it is now possible to handle a much broader class of operators than was previously thought possible.

• INEXPENSIVE STORAGE AND MULTICORE PROCESSORS: Computing architecture is rapidly changing. While it used to be the case that storage and the cost of a single floating-point operation were the principal limiting factors, communication is now emerging as the principal constraint. The reason is the move to parallel and distributed computing, which in turn is driven by the stagnating clock-speed of processors coupled with a shrinking cost per processor. The most extreme manifestation of this shift is perhaps the emergence of components like Graphics Processing Units (GPUs), which contain a very large number of cores each having limited capabilities. The changing computing environment is making many of the currently used numerical algorithms uncompetitive. This creates a demand for new algorithms that are designed from scratch to minimize communication, rather than the number of floating point operations required.

• RANDOMIZED ALGORITHMS IN NUMERICAL LINEAR ALGEBRA: It has recently been demonstrated that approximate factorizations of matrices of numerically low rank can be constructed very efficiently via certain randomized sampling procedures. This work draws on random matrix theory, functional analysis, and linear algebra, and furnishes computational techniques that are highly efficient, robust, versatile, and of intrinsic mathematical interest. Since many analysis-based fast algorithms rely on the hierarchical splitting of a large matrix into submatrices of numerically low rank, there is an obvious opportunity to incorporate the new randomized sampling algorithms into the fast operator algebra methods to achieve even faster and more versatile algorithms.

• IMPROVED SURFACE REPRESENTATIONS AND DISCRETIZATIONS: Real-world applications often involve curves and surfaces with (sometimes thousands of) corners and edges: the interaction of such geometry with the singular kernels of integral operators poses a challenge to accurate solution, particularly in three dimensions. There has been recent progress on high-order surface representations, on the automatic generation of efficient and well-conditioned quadrature schemes for discretizing integral equations, and on evaluation of potential fields close to their sources.

• NEW AND EXPANDING AREAS OF APPLICATION: Many of the FIEM developed for the classical equations in mathematical physics have increasingly been used as building blocks for solving much more complicated boundary value problems. FIEM have now started to compete with finite element and finite differences in simulating complex systems in science and engineering.

• NEW MATHEMATICAL FORMULATIONS OF KEY BOUNDARY VALUE PROBLEMS: There have been recent breakthroughs in creating a well-conditioned mathematical formulation of the scattering problem for time-harmonic Maxwell equations, in the representation of problems in periodic geometries, and deriving second-kind integral equations for high-order systems of PDEs. Such analytically sound formulations are key to creating software packages that are robust at all user parameters.

Recent hardware developments (GPUs, increased storage capacity, distributed computing, etc) have put us in a position where we could soon see such methods being mainstreamed to the point where it would be possible to perform complex 3D simulations in close to real time on a desktop machine. The impact of such a development would be profound.

A BIRS workshop would be an ideal vehicle for advancing progress in this field. It would achieve several key objectives:

• FACILITATING INTERDISCIPLINARY RESEARCH: The advances listed above have occurred in quite disparate fields (computer engineering, numerical analysis, functional analysis, probability theory, etc). A 5-day workshop in an intimate setting is an ideal way of bringing researchers from the different fields together.

• CONNECT ALGORITHM DEVELOPERS AND USERS: For algorithmic development to reach its full potential impact, it is essential that the actual intended users be involved from the beginning. Our proposed list of invitees has such a mix of developers and users.

• DEVELOP YOUNG TALENT: The workshop is intended to inspire and motive younger researchers in the field, and to attract some of the most promising new talent to work on a set of problems that combine mathematical depth and elegance with the potential to make a very substantial difference to our ability to simulate large and complex physical systems.

The workshop would be structured to organize the scientific discussion around three main themes, which are outlined below:

1. Mathematical Foundations of Fast Algorithms.

A discussion of recent advances, possibilities for combining the new techniques, and an exploration of future development. Topics to be discussed could include: finding stable integral equations for a broad range of boundary value problems, methods for handling surfaces with corners and edges, high-order methods for representing surfaces, fast operator algebra and direct solvers, randomized methods.

2. Applications of FIEM including modeling planet earth

In keeping with the theme Mathematics of Planet Earth, topical applications will include earthquake simulation, radar scattering for remote sensing, optical devices for solar energy, renewable energy, and oceanic vortex dynamics in the presence of geography.

3. Software, Parallelization of Fast Algorithm Libraries

Efficient parallelization techniques for algorithms based on adaptive tree structures, computing on GPUs, formulation of standardized test problems and user interfaces, and current issues in improving solvers’ accuracy and efficiency.

The format of the workshop will consist of research seminars focusing on recent advances and poster presentations. In addition, we plan to hold a forum to address the special needs of graduate students, and to provide guidance on prerequisites and possible research directions in our identified themes. We will also plan for unstructured time in order to allow brainstorming by participants on important open problems, such as high-order, adaptive, surface representations, non-constant coefficient and nonlinear PDEs, and well-conditioned formulations for complex systems of equations.