Numerik-Oberseminar WS 2004/05

Interessenten sind herzlich eingeladen!

Rückblick:

• Numerik-Oberseminar SS 2004
• Numerik-Oberseminar WS 2003/04
• Numerik-Oberseminar SS 2003
• Numerik-Oberseminar WS 2002/03
• Numerik-Oberseminar SS 2002
• Numerik-Oberseminar WS 2001/02
• Numerik-Oberseminar SS 2001

Abstracts zu den Vorträgen:

Abstract:
The benefit of nonsymmetric reorderings based on nonsymmetric maximum weighted matchings for the factorization and preconditioning of nonsymmetric linear systems is well-known by now and an important ingredient of direct and preconditioned iterative linear solvers.
This talk will discuss the application of symmetric weighted matchings to general symmetric indefinite systems. In the first part of the talk we will demonstrate the effectiveness of various new pivoting factorization methods [1] for solving sparse symmetric indefinite systems. We will demonstrate numerical stability and accuracy of the algorithms and also show that a high performance implementation is feasible.
In the second part of the talk we present symmetric preconditioning methods for symmetric indefinite matrices based on these maximum weighted matchings [2]. The emerging structure is exploited in a modified incomplete LDL^T factorization scheme that uses 1x1 and 2x2 diagonal block pivoting. The resulting symmetric incomplete indefinite factorizations are used as preconditioners for Krylov-subspace linear solvers e.g SQMR. The objective of the reordering is to maximize the diagonal element or the elements directly alongside the diagonal. For a large class of matrices, such reorderings allow the incomplete factorization method to choose a numerically satisfying 1x1 or a 2x2 pivot.
We show the effectiveness of the resulting methods on a number of real world symmetric indefinite linear systems ranging from augmented interior-point optimizations matrices, to general symmetric saddle point problems and the Anderson matrix eigenvalue problem, where it provides favorable performance with a set of standard parameters.

[1] O.Schenk and K.Gärtner, On fast factorization pivoting methods for sparse symmetric indefinite systems, Technical Report CS-2004-004, Department of Computer Science, University of Basel. Submitted.
[2] M.Hagemann and O.Schenk, Weighted Matchings for the Preconditioning of Symmetric Indefinite Linear Systems, Technical Report CS-2004-005, Department of Computer Science, University of Basel. Submitted.

Abstract:
LAPACK is a comprehensive software library for solving linear systems and eigenvalue problems. It provides well-tested, open source, reviewed code implementing trusted algorithms that guarantee reliability, efficiency and accuracy. LAPACK is working in the background of many other well-known mathematical software packages such as Matlab or Mathematica.
The developers of LAPACK currently plan a major revision and extension, and this talk describes software developed in the numerical analysis group at TU Berlin that has been proposed to get included. These contributions are as follows:

1. Improved routines for solving standard and generalized eigenvalue problems:
   • a multishift QZ algorithm with aggressive, early deflation,
   • highly efficient methods for reordering standard and generalized Schur forms.
2. New routines for solving structured and polynomial eigenvalue problems (quadratic, palindromic, Hamiltonian, ...).

Abstract:
We show how MATLAB has evolved over the last 20 years from a simple matrix calculator to a powerful technical computing environment. We demonstrate several examples of MATLAB applications. We conclude with a few comments about possible future developments.

Cleve Moler is the original author of MATLAB and one of the founders of the MathWorks. He is currently chairman and chief scientist of the company.

Abstract:
In the past decade model predictive control (MPC), also referred to as receding horizon control, or moving horizon control, has become a preferred control strategy for a large number of industrial processes. The main reasons for this popularity include the ability to explicitly handle constraints and to consider multivariable processes with potentially many manipulated and controlled variables. In this presentation we will give an overview over the area of model predictive control with special emphasis on nonlinear model predictive control. After a brief discussion of the history and impact of MPC we will discuss recent results regarding system theoretic properties like stability, robustness, output feedback and performance of the closed loop. With a number of applications we will demonstrate that by using specially tailored optimization methods even large problems, having hundreds of states, can be controlled efficiently using NMPC methods.

Abstract:
Saddle point linear systems arise in a variety of applications. Due to the high indefiniteness of the coefficient matrix, preconditioning is required to speed up convergence. In most cases, the structure of the matrix and the functional properties of the associated operators can be conveniently exploited to devise an effective preconditioner. The quality of the preconditioner can be measured in terms of optimality with respect to the given continuous problem parameters, as well as in terms of computational speed.
In this talk we review some recent results on structured preconditioners such as block diagonal, indefinite and block triangular preconditioner. In addition, we present a new algebraic framework that allows to analyze a large class of computationally effective preconditioners.

Abstract:
We show how to solve a long-standing open problem in numerical linear algebra called van Loan's curse. We derive a new method for computing the Hamiltonian Schur form of a Hamiltonian matrix. The proposed method is numerically strongly backwards stable and of complexity n^3. We demonstrate the properties of the new method via several numerical examples.

Abstract:
We will present an abstract framework to obtain the eigenvalue and eigenvector estimates for the self adjoint operator defined by a positive definite form in a Hilbert space. The estimate has a form of a Temple-Kato like inequality. A Temple-Kato like estimate is a combination of a bound on the part of the spectrum one is not interested in and a measure of the residual of the considered Ritz-vectors. The obtained estimates involve "relative" quantities and test vectors that are anywhere in the form (weak) domain of the operator are allowed (think of Laplace operator and linear finite elements).
The new estimates will be considered in the context of finite element approximation methods for positive definite operators. An abstract condition that is needed to formulate a finite dimensional procedure to asses the measure of the residual will be stated. In the case of the Laplace (divergence form) operator this condition essentially depends on the measure of the oscillation of the considered Ritz-vector(s). Several computational examples will be worked out in detail.

Abstract:
New iterative methods derived by using Lagrange variational approach will be presented. A correction vector in this method is defined from a solution of a system of linear equations. To simplify this system a star approximation is introduced. This approximation results in numerical algorithms with performances from the full to diagonal methods. Numerical algorithms of new methods as well those of Davidson, Jacobi-Davidson, and Newton methods with star approximation will be discussed. Numerical examples that show performances of different methods will be presented.

Abstract:
It is well known that the convergence rate of the Conjugate Gradient method is bounded as a function of the condition number of the system matrix to which it is applied. If the condition number is large it is advisable to solve, instead, a preconditioned system. With respect to the known preconditioners at least two problems remain:

• if there are large jumps in the coefficients of the discretized PDE the convergence of PCG becomes very slow
• if a block preconditioner is used in a domain decomposition algorithm the condition number of the preconditioned matrix deteriorates if the number of blocks increases.

Abstract:
Der Kern einer numerischen Wettervorhersage besteht aus der Lösung der 3-dimensionalen Euler Gleichungen der Strömungsmechanik auf der Erdkugel. Verlässliche Vorhersagen erfordern sowohl eine genaue Reproduktion von Erhaltungsgrössen, wie der Zirkulation und potentiellen Wirbelfeldstärke, als auch die Berücksichtigung der immanenten Zeit- und Längenskalen, die sich in verschiedenen Balance-Zuständen äußern. In dem Vortrag werde ich Partikelmethoden als eine neue Alternative zu klassischen gitterbasierten Verfahren darstellen und speziellen Gesichtspunkte bzgl. der oben genannten Anforderung aus der Wettervorhersage diskutieren.

Abstract:
Symplectic matrices arise in a variety of applications of linear Hamiltonian differential equations. We consider a circular spectral dichotomy problem for symplectic matrices. This problem is closely related to generalized Lyapunov equations. An integral representation for the solutions of such equations can be used to compute a matrix spectral portrait that gives a useful information on the eigenvalue distribution in the complex plane. We present a numerical algorithm for solving Lyapunov equations that also provides the spectral projections onto the invariant subspaces of the matrix corresponding to the eigenvalues inside and outside the circle.

Abstract:
Phenomenological thermodynamics is based on the postulate of nonexistence of perpetual motion machines of the second kind. As such a postulate for equations of continuum mechanics one can consider a hypothesis of correctness of the Cauchy problem. But in this case not for all solutions of nonlinear hyperbolic equations the conservation laws are fulfilled. In this talk we consider some particular models of continuum mechanics and describe different variants of dissipative processes.

Abstract:
After some introductory remarks about the University of Stuttgart and an overview about the Institute B of Mechanics and its current research projects, some aspects of contact mechanics will be described. On the one end of the formulations is the consideration of deformable bodies with sometimes complicated shapes using the Finite-Element method. Due to the complexity of the description and the high computation times, we have to restrict ourselves to few bodies and short simulation times. The other end of possible contact formulations is in the consideration of granular media. Here we have many bodies, where many bodies often means more than 100 000 particles in a system, but only simple geometries and hardly any deformations. Obviously, this demands sophisticated algorithms for neighborhood search and contact administration. In the talk many examples will be shown and some effects and critical issues will be discussed.

Abstract:
Automatic Differentiation (AD) is a technique to evaluate derivatives of functions that are defined by numerical programmes. In contrast to traditional derivative approximation by divided differences, AD employs the chain rule to provide accurate derivatives. Basic concepts of AD such as forward and reverse modes are explained and illustrated using simple examples. The AD tools TAF and TAC++ are introduced, and a number of large-scale applications for sensitivity studies, state/parameter estimation, and uncertainty propagation are presented. The selected examples focus on codes for the simulation of the global oceanic and atmospheric circulation, aerodynamic flows as well as the terrestrial biosphere. Integrating an AD tool in such a modelling system allows for quick updates of the derivative code after modifications of the underlying model.

Abstract:
Based on a fv-discretization the Navier-Stokes equation will be solved by an implicit time integration scheme (unsteady case) and a Newton method (steady case). Experiences and consequences of different approximations of the convective terms and the automatic evaluation of the Jacobian for the Newton method using AD-tools will be presented.

Abstract:
Maxwell's equations contain a dielectric coefficient that describes the particular media. For homogenous materials the dielectric coefficient is constant within the media. However, there is a jump in this coefficient between differing media. This discontinuity frequently significantly reduces the order of accuracy of the scheme. We present an analysis and implementation of high (fourth) order approximations of Maxwell equations, when there is an interface between two media, and so the dielectric coefficient is discontinuous. We consider not only the order of accuracy but also the preservation of the zero divergence of the appropriate electromagnetic fields. We analyze the one dimensional system in frequency space.

Abstract:
The talk deals with algorithmic aspects of the numerical solution for elliptic shape optimization problems. After introducing the shape problem and some basics from the underlying shape calculus, the ``lack of regularity problem'' is explained using the torsional rigidity of an elastic bar and the perimeter of a domain as illustrational examples. The relation to properties of the shape Hessian and to a proper preconditioning of related finite dimensional auxiliary optimization problems is discussed as well. As a byproduct, further results are presented about the numerical solution in 2d and 3d of the exterior electromagnetic shaping problem, the electrical impedance tomography problem and the free boundary problem like in electrochemical processing.

Abstract:
A complex square matrix A is said to be stable if the spectrum of A lies in the open left or right half-plane. This, as well as other related types of matrix stability, play an important role in various applications. As such, matrix stability has been intensively investigated in the past two centuries. A plausible way for finding necessary and/or sufficient conditions for matrix stability is to examine classes of matrices that are known to be stable, and to identify common properties of these classes. Indeed, some well known classes of stable matrices share properties associated with nonnegativity, such as positivity of the principal minors (P-matrices) and weak sign symmetry. It was conjectured by Carlson that the combination P-matrix + weak sign symmetry implies stability. This conjecture was recently disproved by Holtz. However, if we replace the weak sign symmetry by the stronger sign symmetry property, then it was shown already by Carlson that P-matrix + sign symmetry implies stability. The talk will review various results that relate positivity of the principal minors, weak sign symmetry, sign symmetry and stability.

Abstract:
We report on our efforts to use parallel asynchronous iterative methods for large Markov chains of the type used by web searches such as the PageRank algorithm reportedly used by Google. It is shown that the well developed theory of asynchronous iterations can be used in this special case of parallel asynchronous power method. Numerical results illustrate the potential of these methods.

(joint work with Efstratios Gallopoulos and Giorgos Kollias, University of Patras, Greece)