Eigenvalues/singular values and fast PDE algorithms: acceleration, conditioning, and stability (12w5021)

Arriving in Banff, Alberta Sunday, June 24 and departing Friday June 29, 2012


(California Institute of Technology)

Michael Haslam (York University)

Mark Lyon (University of New Hampshire)

(Case Western Reserve University)


The objective of the proposed 5-day workshop is to gather a reduced
community of noted experts whose cutting edge research relates closely
to the challenges in numerical solution of PDEs that arise, as
mentioned above, to unfavourable spectral distributions. We believe
the cross fertilization that will result does not often occur in
regular conference settings, which tend to organize themselves by
sub-areas in the field of numerical analysis. Thus, for example, it is
rare for experts in embedded boundary methods to meet mathematicians
working on advanced finite-element methods or spectral methods even
though many of the challenges faced, in particular the poor behavior
of certain eigenvalues/singular values, extensively cross subfield
boundaries. Our workshop proposal was born from our belief that much
can be expected from such interactions across sub-areas to address
common challenges: we hope our workshop will facilitate an exchange of
ideas well beyond what would occur through a study of the published
literature or from occasional encounters in large yearly conferences.

We are very pleased to be able to indicate that, indeed, many
ground-breaking contributions in numerical analysis of PDEs have been
made by individuals who are planning to attend this workshop. The
exchanges between experts at the forefront of the subfields will
surely lead to an advancement of the field as a whole.

To positively promote such effective exchanges our workshop will

Host two main one-hour lectures per day of the workshop, one in
the morning and one in the afternoon;
Host an additional four half-hour lectures per day of the
Host a daily 90 minute afternoon discussion session with two
moderators each promoting a different point of view (all to be
conducted in what is expected will be a most cordial atmosphere).

With the emergence of potentially revolutionary advances in numerical
methods over the last couple of years, the time is perfect for us
to capitalize on the wealth of new ideas and techniques---we believe
the resulting synergy will be extremely valuable. This comes at a
time, further, when new, radically innovative computer architectures,
such as clusters of Graphical Processing Units (such as GPUs put forth
recently by NVIDIA, which nowadays can contain 400 processors in a
regular desktop computer case!) and heterogeneous multi-processing
units (such as the IBM's PowerXCell 8i processor and its fast
double-precision floating point units), and mathematicians are in a
position to make a significant impact on the hardware-architecture
designs---by demonstrating ways in which the realism now available in
computer gaming can be achieved in the much more complex scientific
context, by means of reliable, accurate and efficient computational
algorithms for the solution of PDEs.

As mentioned above, one of the main purposes of our workshop is to
study the basic underpinning of recent successes in the field of
numerical analysis and their connection with the
eigenvalues/singular-values of the associated discrete systems, and to
understand the extent to which desirable spectral properties can be
extended to other types of problems and algorithms. Some prominent
topics that will be considered during the workshop are listed below,
along with a brief mention of associated recent successes and

Stability - Regardless of the accuracy of a particular
method for time-dependent problems, if it is not in some measure
stable it will not be useful: failing stability, the numerical
approximation of a bounded solution becomes infinite (and thus totally
inaccurate) in finite time. The stability of the system is indeed
governed by certain eigenvalues and singular values. Recent ideas,
including temporal sub-cycling in high-order Discontinuous Galerkin
methods and boundary projections in Fourier-Continuation methods, can
nearly (even completely, in some cases) overcome stability constraints
without sacrificing computational efficiency.

High-Order/Spectral Accuracy - Relying on methods that
ensure agreement of solutions to their Taylor/Fourier expansions to
some (adequately high) order $n$, higher-order/spectral methods
generally use fewer unknowns to reach a prescribed solution
accuracy. At the same time the eigenvalues of the resulting systems
are often correlated to the order of the method and the problems
associated with poorly behaved eigenvalues are exacerbated as the
order is increased. Further, the eigenvalues are often very sensitive
to the specific geometry and/or mesh of the problem. The advent of
certain embedded-boundary methods, high-order integral methods, and
overlapping meshes has greatly broadened the applicability of
high-order and spectral methods.

Fast Iterative Methods - Relying on ideas related to the
Fast Fourier Transform, use of approximate inverses (preconditioners)
to accelerate convergence of iterative methods and low-rank matrix
approximations, the advent of fast integral-equation solvers and
multi-grid methods, as well as wavelet-based and fast direct solvers
has inaugurated a new research direction in the field of numerical
solution of PDEs. The overall computational cost of these methods is
often tied directly to behavior of eigenvalues. Poorly behaved
eigenvalues will lead to the requirement of larger numbers of
linear-algebra iterations which can then only be reduced by finely
tuned preconditioners. Emerging hybrid methods, which employ, say, a
combination of a fast algorithm and a classical method (e.g., a hybrid
of integral equation solvers and high-order finite-element
approximations), are promising and currently a subject of much

The field of computational PDEs encompasses, without doubt, some of
the most useful and, at the same time, scholarly challenging offerings
the broad field of applied mathematics has ever produced. Recent
advances in numerical analysis have the potential to allow unequaled
simulation capabilities for understanding of complex phenomena in an
extremely diverse range of applications. The participants of this
workshop include some of the most highly recognized international
experts in the field, who are highly qualified to contribute to the
main subject matter of the workshop: study and remediation of the
negative effects arising from unfavorable spectral distributions in
numerical PDE solvers. We are confident the outcome of this workshop
will have a significant impact on science and engineering in years to