Past Computational Mathematics and Applications Seminar

Partial differential equations with a nonlinear pointwise constraint defined through a manifold occur in a variety of applications: The magnetization of a ferromagnet can be described by a unit length vector field and the orientation of the rod-like molecules that constitute a liquid crystal is often modeled by a vector field that attains its values in the real projective plane thus respecting the head-to-tail symmetry of the molecules. Other applications arise in geometric

modeling, quantum mechanics, and general relativity. Simple examples reveal that it is impossible to satisfy pointwise constraints exactly by lowest order finite elements. For two model problems we discuss the practical realization of the constraint, the efficient solution of the resulting nonlinear systems of equations, and weak accumulation of approximations at exact solutions.

We focus on domain decomposition methods for systems of PDEs (versus scalar PDEs). The Smith factorization (a "pure" algebra tool) is used systematically to derive new domain decompositions methods for symmetric and unsymmetric systems of PDEs: the compressible Euler equations, the Stokes and Oseen (linearized Navier-Stokes) problem. We will focus on the Stokes system. In two dimensions the key idea is the transformation of the Stokes problem into a scalar bi-harmonic problem. We show, how a proposed domain decomposition method for the bi-harmonic problem leads to a domain decomposition method for the Stokes equations which inherits the convergence behavior of the scalar problem. Thus, it is sufficient to study the convergence of the scalar algorithm. The same procedure can also be applied to the three-dimensional Stokes problem.

The butterfly-shaped Lorenz attractor is a fractal set made up of infinitely many periodic orbits. Ever since Lorenz (1963) introduced a system of three simple ordinary differential equations, much of the discussion of his system and its strange attractor has adopted a dynamical point of view. In contrast, we allow time to be a complex variable and look upon such solutions of the Lorenz system as analytic functions. Formal analysis gives the form and coefficients of the complex singularities of the Lorenz system. Very precise (> 500 digits) numerical computations show that the periodic orbits of the Lorenz system have singularities which obey that form exactly or very nearly so. Both formal analysis and numerical computation suggest that the mathematical analysis of the Lorenz system is a problem in analytic function theory. (Joint work with S. Sahutoglu).

The advent of multicore processors and other technologies like Graphical Processing Units (GPU) will considerably influence future research in High Performance Computing.

To take advantage of these architectures in dense linear algebra operations, new algorithms are

proposed that use finer granularity and minimize synchronization points.

After presenting some of these algorithms, we address the issue of pivoting and investigate randomization techniques to avoid pivoting in some cases.

In the particular case of GPUs, we show how linear algebra operations can be enhanced using

hybrid CPU-GPU calculations and mixed precision algorithms.

This is not intended to be a systematic History, but a selection of highlights, with some digressions, including:

The early days of the Computing Lab;

How the coming of the Computer changed some of the ways we do Computation;

A problem from the Study Groups;

Influence of the computing environment (hardware and software);

Convergence analysis for the heat equation, then and now.

Dirichlet to Neumann maps and their generalizations are exceptionally useful tools in the study of eigenvalue problems for ODEs and PDEs. They also have real physical significance through their occurrence in electrical impedance tomography, with applications to medical imagine, landmine detection and non-destructive testing. This talk will review some of the basic properties of Dirichlet to Neumann maps, some new abstract results which make it easier to use them for a wide variety of models, and some analytical/numerical results which depend on them, including detection and elimination of spectral pollution.

The Jacobi-Davidson method, proposed by Sleijpen and Van der Vorst more than a decade ago, has been successfully used to numerically solve large matrix eigenvalue problems. In this talk we will give an introduction to and an overview of this method, and also point out some recent developments.

The task is to compute orthogonal eigenvectors (without Gram-Schmidt) of symmetric tridiagonals for isolated clusters of close eigenvalues. We review an "old" method, the Submatrix method, and describe an extension which significantly enlarges the scope to include several mini-clusters within the given cluster. An essential feature is to find the envelope of the associated invariant subspace.

"Eigenvalue avoidance" or "level repulsion" refers to the tendency of eigenvalues of matrices or operators to be distinct rather than degenerate.

The mathematics goes back to von Neumann and Wigner in 1929 and touches many subjects including numerical linear algebra, random matrix theory, chaotic dynamics, and number theory.

This talk will be an informal illustrated discussion of various aspects of this phenomenon.

We discuss general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We discuss several real industrial applications ranging from acoustic field computations to optimal control problems.

We discuss linearization and first order formulations and their relationship to the corresponding techniques used in the treatment of systems of higher order differential equations.

In order to deal with structure preservation, we derive condensed/canonical forms that allow (partial) deflation of critical eigenvalues and the singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors.

Based on these new linearization techniques we discuss new structure preserving eigenvalue methods and present several real world numerical examples.

Meshfree methods become more and more important for the numerical simulation of complex real-world processes. Compared to classical, mesh-based methods they have the advantage of being more flexible, in particular for higher dimensional problems and for problems, where the underlying geometry is changing. However, often, they are also combined with classical methods to form hybrid methods.

In this talk, I will discuss meshfree, kernel based methods. After a short introduction along the lines of optimal recovery, I will concentrate on results concerning convergence orders and stability. After that I will address efficient numerical algorithms. Finally, I will present some examples, including one from fluid-structure-interaction, which will demonstrate why these methods are currently becoming Airbus's preferred solution in Aeroelasticity.

A well-known problem in protein modeling is the determination of the structure of a protein with a given set of inter-atomic or inter-residue distances obtained from either physical experiments or theoretical estimates. A general form of the problem is known as the distance geometry problem in mathematics, the graph embedding problem in computer science, and the multidimensional scaling problem in statistics. The problem has applications in many other scientific and engineering fields as well such as sensor network localization, image recognition, and protein classification. We describe the formulations and complexities of the problem in its various forms, and introduce a so-called geometric buildup approach to the problem. We present the general algorithm and discuss related computational issues including control of numerical errors, determination of rigid vs. unique structures, and tolerance of distance errors. The theoretical basis of the approach is established based on the theory of distance geometry. A group of necessary and sufficient conditions for the determination of a structure with a given set of distances using a geometric buildup algorithm are justified. The applications of the algorithm to model protein problems are demonstrated.

Graph-theoretic ideas have become very useful in understanding modern large-scale data-mining techniques. We show in this talk that ideas from optimization are also quite useful to better understand the numerical behavior of the corresponding algorithms. We illustrate this claim by looking at two specific graph theoretic problems and their application in data-mining.

The first problem is that of reputation systems where the reputation of objects and voters on the web are estimated; the second problem is that of estimating the similarity of nodes of large graphs. These two problems are also illustrated using concrete applications in data-mining.