Abstract

We provide a notion of finite element system, that enables the construction of spaces of differential forms, which can be used for the numerical solution of variationally posed partial differential equations. Within this framework, we introduce a form of upwinding, with the aim of stabilizing methods for the purposes of computational fluid dynamics, in the vanishing viscosity regime.

Foreword

I am deeply honored to have received the first Stephen Smale prize from the Society for the Foundations of Computational Mathematics.

I want to thank the jury for deciding, in what I understand was a difficult weighing process, to tip the balance in my favor. The tiny margins that similarly enable the Gömböc to find its way to equilibrium, give me equal pleasure to contemplate. It's a beautiful prize trophy.

It is a great joy to receive a prize that celebrates the unity of mathematics. I hope it will draw attention to the satisfaction there can be, in combining theoretical musings with potent applications. Differential geometry, which infuses most of my work, is a good example of a subject that defies perceived boundaries, equally appealing to craftsmen of various trades.

As I was entering the subject, rumors that Smale could turn spheres inside out without pinching, were among the legends that gave it a sense of surprise and mystery. I also remember reading about Turing machines built on rings other than ℤ/2ℤ, which, together with parallelism and quantum computing, convinced me that the foundations of our subject were still in the making.

The Society for the Foundations of Computational Mathematics supports and promotes fundamental research in computational mathematics and its applications, interpreted in the broadest sense. It fosters interaction among mathematics, computer science and other areas of computational science through its conferences, workshops and publications. As part of this endeavour to promote research across a wide spectrum of subjects concerned with computation, the Society brings together leading researchers working in diverse fields. Major conferences of the Society have been held in Park City (1995), Rio de Janeiro (1997), Oxford (1999), Minneapolis (2002), Santander (2005), Hong Kong (2008), and Budapest (2011). The next conference is expected to be held in 2014. More information about FoCM is available at its website http://focmsociety. org.

The conference in Budapest on July 4 – 14, 2011, was attended by some 450 scientists. FoCM conferences follow a set pattern: mornings are devoted to plenary talks, while in the afternoon the conference divides into a number of workshops, each devoted to a different theme within the broad theme of foundations of computational mathematics. This structure allows for a very high standard of presentation, while affording endless opportunities for cross-fertilization and communication across subject boundaries. Workshops at the Budapest conference were held in the following nineteen fields:

1. – Approximation theory

2. – Asymptotic analysis and high oscillation

3. – Computational algebraic geometry

4. – Computational dynamics

5. – Computational harmonic analysis, image and signal processing

6. – Computational number theory

7. – Continuous optimization

8. – Flocking, swarming, and control of distributed systems

9. – Foundations of numerical PDEs

10. – Geometric integration and computational mechanics

11. – Information-based complexity

12. – Learning theory

13. – Multiresolution and adaptivity in numerical PDEs

14. – Numerical linear algebra

15. – Random matrix theory, computations & applications

16. – Real-number complexity

17. – Special functions and orthogonal polynomials

18. – Stochastic computation

19. – Symbolic analysis

Abstract

In this paper we survey parts of group theory, with emphasis on structures that are important in design and analysis of numerical algorithms and in software design. In particular, we provide an extensive introduction to Fourier analysis on locally compact abelian groups, and point towards applications of this theory in computational mathematics. Fourier analysis on non-commutative groups, with applications, is discussed more briefly. In the final part of the paper we provide an introduction to multivariate Chebyshev polynomials. These are constructed by a kaleidoscope of mirrors acting upon an abelian group, and have recently been applied in numerical Clenshaw-Curtis type numerical quadrature and in spectral element solution of partial differential equations, based on triangular and simplicial subdivisions of the domain.

Introduction

Group theory is the mathematical language of symmetry. As a mature branch of mathematics, with roots going almost two centuries back, it has evolved into a highly technical discipline. Many texts on group theory and representation theory are not readily accessible to applied mathematicians and computational scientists, and the relevance of group theoretical techniques in computational mathematics is not widely recognized.

Nevertheless, it is our conviction that knowledge of central parts of group theory and harmonic analysis on groups is invaluable also for computational scientists, both as a language to unify, analyze and generalize computational algorithms and also as an organizing principle of mathematical software construction.

Abstract

This article highlights a coherent series of algorithmic tools to compute and work with algebraic and differential invariants.

Introduction

Group actions are ubiquitous in mathematics and arise in diverse fields of science and engineering, including physics, mechanics, and computer vision. Invariants of these group actions typically arise to reduce a problem or to decide if two objects, geometric or abstract, are obtained from one another by the action of a group element. [8, 9, 10, 11, 13, 15, 17, 39, 40, 42, 43, 45, 46, 52, 59] are a few recent references of applications. Both algebraic and differential invariant theories have become in recent years the subject of computational mathematics [13, 14, 17, 40, 60]. Algebraic invariant theory studies polynomial or rational invariants of algebraic group actions [18, 22, 23, 54]. A typical example is the discriminant of a quadratic binary form as an invariant of an action of the special linear group. The differential invariants appearing in differential geometry are smooth functions on a jet bundle that are invariant under a prolonged action of a Lie group [4, 16, 34, 48, 53]. A typical example is the curvature of a plane curve, invariant under the action of the group of the isometries on the plane. Curvature is not a rational function, but an algebraic function. Concomitantly the classical Lie groups are linear algebraic groups.

This article reviews results of [14, 28, 29, 30, 31, 32] in order to show their coherence in addressing algorithmically an algebraic description of the differential invariants of a group action. In the first section we show how to compute the rational invariants of a group action and give concrete expressions to a set of algebraic invariants that are of fundamental importance in the differential context. The second section addresses the question of finite representation of differential invariants with invariant derivations, a set of generating differential invariants and the differential relationships among them. In the last section we describe the algebraic structure that better serves the representation of differential invariants.

Abstract

We investigate the dual role of convection on the large time behavior of the 3D incompressible Navier-Stokes equations. On the one hand, convection is responsible for generating small scales dynamically. On the other hand, convection may play a stabilizing role in potentially depleting nonlinear vortex stretching for certain flow geometry. Our study is centered around a 3D model that was recently proposed by Hou and Lei in [23] for axisymmetric 3D incompressible Navier-Stokes equations with swirl. This model is derived by neglecting the convection term from the reformulated Navier-Stokes equations and shares many properties with the 3D incompressible Navier-Stokes equations. In this paper, we review some of the recent progress in studying the singularity formation of this 3D model and how convection may destroy the mechanism that leads to singularity formation in the 3D model.

Introduction

Whether the 3D incompressible Navier-Stokes equations can develop a finite time singularity from smooth initial data with finite energy is one of the seven Millennium problems posted by the Clay Mathematical Institute [16]. This problem is challenging because the vortex stretching nonlinearity is super-critical for the 3D Navier-Stokes equation. Conventional functional analysis based on energy type estimates fails to provide a definite answer to this problem. Global regularity results are obtained only under certain smallness assumptions on the initial data or the solution itself. Due to the incompressibility condition, the convection term seems to be neutrally stable if one tries to estimate the Lp (1 < p≤∞) norm of the vorticity field. As a result, the main effort has been to use the diffusion term to control the nonlinear vortex stretching term by diffusion without making use of the convection term explicitly.

Abstract

This article reviews some of the phenomena and theoretical results on the long-time energy behaviour of continuous and discretized oscillatory systems that can be explained by modulated Fourier expansions: longtime preservation of total and oscillatory energies in oscillatory Hamiltonian systems and their numerical discretizations, near-conservation of energy and angular momentum of symmetric multistep methods for celestial mechanics, metastable energy strata in nonlinear wave equations. We describe what modulated Fourier expansions are and what they are good for.

Introduction

As a new analytical tool developed in the past decade, modulated Fourier expansions have been found useful to explain various long-time phenomena in both continuous and discretized oscillatory Hamiltonian systems, ordinary differential equations as well as partial differential equations. In addition, modulated Fourier expansions have turned out useful as a numerical approximation method in oscillatory systems.

In this review paper we first show some long-time phenomena in oscillatory systems, then give theoretical results that explain these phenomena, and finally outline the basics of modulated Fourier expansions with which these results are proved.

Abstract

Sage is a large free open source software package aimed at all areas of mathematical computation. Hundreds of people have contributed to the project, which has steadily grown in popularity since 2005. This paper describes the motivation for starting Sage and the history of the project.

Introduction

The goal of the Sage project (http://www.sagemath.org) is to create a viable free open source alternative to Magma, Maple™, Mathematica®, and MATLAB®, which are the most popular non-free closed source mathematical software systems. Magma is (by far) the most advanced non-free system for structured abstract algebraic computation, Mathematica and Maple are popular and highly developed systems that shine at symbolic manipulation, and MATLAB is the most popular system for applied numerical mathematics. Together there are over 3,000 employees working at the companies that produce the four Ma's listed above, which take in over a hundred million dollars of revenue annually.

By a viable free alternative to the Ma's, we mean a system that will have the important mathematical features of each Ma, with comparable speed. It will have 2d and 3d graphics, an interactive graphical user interface, and documentation, including books, papers, school and college curriculum materials, etc. A single alternative to all of the Ma's is not necessarily a drop-in replacement for any of the Ma's; in particular, it need not run programs written in the custom languages of those systems. Thus an alternative may be philosophically different than the open source system Octave, which understands the MATLAB source language and attempts to implement the entire MATLAB library.

Introduction

With sensors becoming ubiquitous, there is an increasing interest in mining the data from these sensors as the data are being collected. This analysis of streaming data, or data streams, is presenting new challenges to analysis algorithms. The size of the data can be massive, especially when the sensors number in the thousands and the data are sampled at a high frequency. The data can be non-stationary, with statistics that vary over time. Real-time analysis is often required, either to avoid untoward incidents or to understand an interesting phenomenon better. These factors make the analysis of streaming data, whether from sensors or other sources, very data- and compute-intensive. One possible approach to making this analysis tractable is to identify the important data streams to focus on them. This chapter describes the different ways in which this can be done, given that what makes a stream important varies from problem to problem and can often change with time in a single problem. The following illustrate these techniques by applying them to data from a real problem and discuss the challenges faced in this emerging field of streaming data analysis.

This chapter is organized as follows: first, I define what is meant by streaming data and use examples from practical problems to discuss the challenges in the analysis of these data. Next, I describe the two main approaches used to handle the streaming nature of the data – the sliding window approach and the forgetting factor approach.

Introduction

Protecting communications networks against attacks where the aim is to steal information, disrupt order, or harm critical infrastructure can require the collection and analysis of staggering amounts of data. The ability to detect and respond to threats quickly is a paramount concern across sectors, and especially for critical government, utility, and financial networks. Yet detecting emerging or incipient threats in immense volumes of network traffic requires new computational and analytic approaches. Network security increasingly requires cooperation between human analysts able to spot suspicious events through means such as data visualization and automated systems that process streaming network data in near real-time to triage events so that human analysts are best able to focus their work.

This chapter presents a pair of network traffic analysis tools coupled to a computational architecture that enables the high-throughput, real-time visual analysis of network activity. The streaming data pipeline towhich these tools are connected is designed to be easily extensible, allowing newtools to subscribe to data and add their own in-stream analytics. The visual analysis tools themselves – Correlation Layers for Information Query and Exploration (CLIQUE) and Traffic Circle – provide complementary views of network activity designed to support the timely discovery of potential threats in volumes of network data that exceed what is traditionally visualized. CLIQUE uses a behavioral modeling approach that learns the expected activity of actors (such as IP addresses or users) and collections of actors on a network, and compares current activity to this learned model to detect behavior-based anomalies.

Introduction

Support vector machines (SVM) are currently one of the most popular and accurate methods for binary data classification and prediction. They have been applied to a variety of data and situations such as cyber-security, bioinformatics, web searches, medical risk assessment, financial analysis, and other areas [1]. This type of machine learning is shown to be accurate and is able to generalize predictions based upon previously learned patterns. However, current implementations are limited in that they can only be trained accurately on examples numbering to the tens of thousands and usually run only on serial computers. There are exceptions. A prime example is the annual machine learning and classification competitions such as the International Conference on Artificial Neural Networks (ICANN), which present problems with more than 100,000 elements to be classified. However, in order to treat such large test cases the formalism of the support vector machines must be modified.

SVMs were first developed by Vapnik and collaborators [2] as an extension to neural networks. Assume that we can convert the data values associated with an entity into numerical values that form a vector in the mathematical sense. These vectors form a space. Also, assume that this space of vectors can be separated by a hyperplane into the vectors that belong to one class and those that form the opposing class.

Introduction

In the last two decades, the continuous increase of computational power has produced an overwhelming flow of data, which called for a paradigm shift in the computing architecture and large scale data processing mechanisms. In a speech given just a few weeks before he was lost at sea off the California coast in January 2007, Jim Gray, a database software pioneer and a Microsoft researcher, called the shift a “fourth paradigm” [32]. The first three paradigms were experimental, theoretical and, more recently, computational science. Gray argued that the only way to cope with this paradigm is to develop a new generation of computing tools to manage, visualize, and analyze the data flood. In general, the current computer architectures are increasingly imbalanced where the latency gap between multicore CPUs and mechanical hard disks is growing every year, which makes the challenges of data-intensive computing harder to overcome [6]. Therefore, there is a crucial need for a systematic and generic approach to tackle these problems with an architecture that can also scale into the foreseeable future. In response, Gray argued that the new trend should instead focus on supporting cheaper clusters of computers to manage and process all this data instead of focusing on having the biggest and fastest single computer. Figure 5.1 illustrates an example of the explosion in scientific data, which creates major challenges for cutting-edge scientific projects. For example, modern high-energy physics experiments, such as DZero, typically generate more than one terabyte of data per day.

An Architecture Blueprint

As the previous chapter describes, data-intensive applications arise from the interplay of ever-increasing data volumes, complexity, and distribution. Add the needs of applications to process this complex data mélange in ever more interesting and faster ways, and you have an expansive landscape of specific application requirements to address.

Not surprisingly, this breadth of specific requirements leads to many alternative approaches to developing solutions. Different application domains also leverage different technologies, adding further variety to the landscape of dataintensive computing. Despite this inherent diversity, several model solutions for contemporary data-intensive problems have emerged in the last few years. The following briefly describes each one:

Data processing pipelines: Emerging from scientific domains, many large data problems are addressed using processing pipelines. Raw data that originates from a scientific instrument or a simulation is captured and stored. The first stage of processing typically applies techniques to reduce the data in size by removing noise and then processes the data (such as index, summarize, or markup) so that it can be more efficiently manipulated by downstream analytics. Once the capture and initial processing takes place, complex algorithms search and process the data. These algorithms create information and/or knowledge that can be digested by humans or further computational processes. Often, these analytics require large-scale distribution or specialized high-performance computing platforms to execute, making the execution environment of most pipelines both distributed and heterogeneous. Finally, the analysis results are presented to users so that they can be digested and acted upon.

Introduction

Data-intensive applications have special characteristics that in many cases prevent them from executing well on traditional cache-based processors. They can have highly irregular access patterns with very little locality that do not match the expectations of automatically controlled caches. In other cases, such as when they process data in streaming, they do not have temporal locality at all and only limited spatial locality, therefore reducing the effectiveness of caches.

We present an application-driven study of several architectures that are suitable for data-intensive algorithms. Our chosen application is high-speed string matching, which exhibits two key properties of data-intensive codes: highly irregular access patterns and high-speed streaming data. Irregular access patterns appear in string matching when traversing graph-based representations of the pattern dictionaries being used. String matching is typically used in cybersecurity applications to scan incoming network traffic or files for the presence of signatures (such as specific sequences of symbols), which may relate to attack patterns, viruses, or other malware.

String Matching

String matching algorithms check and detect the presence of one or more known symbol sequences inside the analyzed data sets. Besides their wellknown application to databases and text processing, they are the basis of several other critical, real-world applications. String matching algorithms are key components of DNA and protein sequencing, data mining, security systems, such as Intrusion Detection Systems (IDS) for Networks (NIDS), Applications (APIDS), Protocols (PIDS), or Systems (Host based IDS [HIDS]), anti-virus software, and machine learning problems.