Logo: DFG Research Center MATHEON, Mathematics for key technologies

C4: Numerical solution of large nonlinear eigenvalue problems

DFG-Forschungszentrum Technische Universität Berlin

Duration: August 2002 - May 2009
Project leaders: C. Mehl, V. Mehrmann
School of Mathematics, University of Birmingham,
Edgbaston Birmingham B15 2TT, United Kingdom
email: mehl@maths.bham.ac.uk.de
Tel: +44 121 414 6578
Department of Mathematics, Technical University of Berlin,
Strasse des 17. Juni 136, 10623 Berlin, Germany
email: mehrmann@math.tu-berlin.de
Tel: +49 (0)30 - 314 25736 (office) / - 314 21264 (secretary)
Responsible: C. Schröder, K. Schreiber
Department of Mathematics, Technical University of Berlin,
Strasse des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 23439, Tel: +49 (0)30 - 314 25741
email: schroed@math.tu-berlin.de, schreibe@math.tu-berlin.de
Cooperation: There are connections to C22, D1, D2 and D13.
Z. Bai (UC Davis)
P. Benner (TU Chemnitz)
S. Bora
A. Ran (VU Amsterdam)
L. Rodman (Williamsburg)
R. Byers and H. Xu (U of Kansas)
D. Chu and X. Liu (National U of Singapore)
W.-W. Lin (National Tsinghua U. Hsinchu, Taiwan)
H. Faßbender (TU Braunschweig)
N. Higham, F. Tisseur and T. Betcke (U of Manchester)
B. Kagström (U Umea)
K. Knothe (TU Berlin)
D. Kressner (ETH Zurich)
D. S. Mackey and N. Mackey (Western Michigan U)
E. Mengi (New York U)
H. Schwetlick (TU Dresden)
H. Voss (TU Hamburg-Harburg)
D. Watkins (UW Pullman)
Activities: Eigenvalue Day (workshop on nonlinear eigenvalue problems)
Oberseminar Numerik
HAPACK - Software for (skew-)Hamiltonian eigenvalue problems
Web computing with SLICOT
Workshop: Operator Theory in Krein Spaces and Applications
4th GAMM-Workshop, Hagen
5th GAMM Workshop on Applied and Numerical Linear Algebra, Dresden
Workshop on the Nonlinear Eigenvalue Problem 2006
4. Berlin-Manchester Workshop on the Nonlinear Eigenvalue Problem 2008
Support: DFG Research Center Matheon "Mathematics for Key Technologies"


Description

The numerical solution of large nonlinear (polynomial or rational) eigenvalue problems is a crucial question in numerous technologies like the stability and vibration analysis in classical structural mechanics and the investigation of molecular dynamics, elastic deformation of anisotropic materials, gyroscopic systems, or optical waveguide design. In particular, the trend to extreme designs (high speed trains, Airbus 380, modern materials, optoelectronic devices, micro-electromechanical systems, fluid-solid structures) presents a challenge for the numerical computation of resonance frequencies of these structures [1,28, 30, 32,42]. These extreme designs often lead to very large eigenvalue problems with an extremely bad conditioning. On the other hand, the physics of the underlying system lead to specific algebraic structures of the nonlinear eigenvalue problem that result in symmetries in the spectrum and also in specific properties of the corresponding eigenvectors or invariant subspaces. In numerical computation, it is essential to use algorithms that preserve these structures in order to obtain physically meaningful results.

Usually, nonlinear eigenvalue problems are solved by linearization, i.e., by embedding the system into a larger linear eigenvalue problem. In this context, it is essential to construct linearizations that reflect the algebraic structure of the original problem and to develop algorithms that solve the resulting linear problems in a structure preserving way. On the other hand, linearization may increase the condition number of the problem with the effect that the solution is more sensitive towards small perturbations of the original data. Hence, there is need for the design of structure preserving algorithms that work directly on the original data.

Despite numerous existing numerical approaches, there are no black-box solvers for nonlinear eigenvalue problems as they exist for linear eigenvalue problems like Linpack, Lapack, Scalapack and Arpack. The reason for this stems from the nonlinearity on one hand, which causes the absence of the basic ingredients for fast and reliable numerical methods on the other hand. Particularly, fundamental theoretical results on nonlinear eigenvalue problems are missing.

Results of the first phase

In the first phase of the project, structured linear eigenvalue problems arising from the linearization of several classes of nonlinear eigenvalue problems have been investigated and structure preserving algorithms have been developed. In this context, Hamiltonian eigenvalue problems that arise in the linearization of gyroscopic quadratic eigenvalue problems have been analyzed in [2,4,5,7,9,18,20] concerning perturbation analysis, development of algorithms, and implementation aspects. In particular, a software package has been implemented [3], see http://www.math.tu-berlin.de/~kressner/hapack . This research is part of the Ph.D. thesis of D. Kressner [22]. Specific structure preserving methods for gyroscopic systems have been constructed in [15]. The same methods were applicable in optimal waveguide design. Jacobi-like algorithms for the solution of generalized indefinite Hermitian eigenvalue problem have been developed in [26].

A new theory for the representation of nonlinear eigenvalue problems via generalized eigenvalue problems has been developed in [24,25]. This approach allows to find structure reflecting and optimally conditioned linearizations and, in particular, a comparison of the condition numbers of the original nonlinear problem and its linearization [12]. Based on the results in [24,25,26], specific methods for a polynomial eigenvalue problem in the vibration analysis of high speed trains have been developed in cooperation with the company SFE Berlin in [13,14] leading to computed eigenvalues with as many correct digits as the finite element discretization allows, in contrast to no correct digits before. These results have been publicized by I. Ipsen in SIAM News [16].

Concerning the problem of finding algorithms that work directly on the original data, Krylov subspace methods for nonlinear eigenvalue problems including techniques for locking and restarting have been developed in [31]. Moreover, algorithmic aspects of product eigenvalue problems have been investigated [19,21]. These type of nonlinear eigenvalue problems arise, e.g., in bifurcation analysis.

A first step towards a perturbation analysis of structured eigenvalue problems has been made by developing and analyzing canonical forms for several structured eigenvalue problems in [27]. Moreover, condition numbers for nonlinearly structured eigenvalue problems have been investigated in [17].

Finally, a documentation of the state of art in numerical solution methods for nonlinear eigenvalue problems has been presented in [29].

New results and their impact

Structured linear eigenvalue problems arising from the linearization of several classes of nonlinear eigenvalue problems have been investigated and structure preserving algorithms have been developed. In this context, Hamiltonian eigenvalue problems that arise in the linearization of gyroscopic quadratic eigenvalue problems have been considered. A structured, backward stable algorithm (solving the long-open problem called ``Van Loan's curse'') was developed in [8].

Another main topic have been palindromic and even eigenvalue problems that arise in applications like the vibration analysis of rail tracks, but also in discrete or continous time optimal control. A structured canonical form for palindromic pencils is described in [34,38]. Also, numerical methods were developed. The structure-preserving version of the well known QR-algorithm was developed for palindromic eigenvalue problems [23,36]. It is especially well suited for the important class of SISO systems. For other types of palindromic problems, the antitriangular URV algorithm was presented in [35]. This method uses a deflation procedure to calculate eigenvalues bounded away from the unit circle and uses accurate methods for a remaining small and dense eigenvalue problem with eigenvalues close to the unit circle. One of these accurate methods was an adaption of a nonsymmetric Jacobi algorithm whose convergence properties have been investigated in [28]. Most of the research on palindromic eigenvalue problems forms also part of the Ph.D. thesis of C. Schröder [39].

A structure similar to the palindromic structure arises in the stability analysis of time delay systems. These so-called PCP-palindromic eigenvalue problems were analysed in [10].

A first step towards a perturbation analysis of structured eigenvalue problems has been made by developing and analyzing canonical forms for several structured eigenvalue problems in [27].

General nonlinear eigenvalue problems were tackled in the Ph.D. thesis of K. Schreiber [33]. There, concerning basic theoretical results, a representation for the inverse of a nonlinear operator has been developed, which motivates nonlinear inverse iteration techniques, and a representation for the condition number of an eigenvalue for general nonlinear problems has been found.

A generalization of the (two-sided) Rayleigh quotient for nonlinear eigenvalue problems was given and analyzed, in particular a standard and a generalized Rayleigh functional, for which locally unique existence, first order perturbation expansions and and error bounds in the vectors, as well as stationarity have been shown, cf. [33].

With the so gained knowledge on Rayleigh functionals, new basic methods for the computation of eigenvalues and -vectors have been designed. These one- resp.\ two-vector methods are essential for subspace extension methods like Jacobi--Davidson [6] and nonlinear Arnoldi [43] in two ways: First, these methods are based upon the respective one-vector methods in the sense that they provide the vector updates; second, the subspace expansion methods still need to solve small dimensional dense nonlinear problems, which is usually done by the nonlinear inverse iteration. The two--sided Rayleigh functional iteration is the analogon to the two-sided Rayleigh quotient iteration for nonnormal matrices, and has been shown to converge locally cubically as well. A generalization of the residual inverse iteration has been shown to converge locally quadratically [33].

Different versions of nonlinear Jacobi--Davidson methods have been discussed. The two-sided nonlinear version was shown to converge locally cubically [33]. A nonlinear Jacobi-Davidson-like method that is especially suited for the computation of ill-conditioned eigenvalues has been developed and analyzed in [40].

A technique to accelerate convergence for methods computing left and right eigenvectors has been introduced in [33]. The half-step two-sided Rayleigh functional iteration is shown to converge with R-order 4.

The special case of nonlinear complex symmetric eigenvalue problems has been examined, where an appropriate complex symmetric Rayleigh functional has been developed, the locally cubic convergence of the complex symmetric Rayleigh functional iteration / Jacobi-Davidson method, and the locally quadratic convergence of the complex symmetric residual inverse iteration method have been shown in the Ph.D. thesis of K. Schreiber [33]..

It has been shown in [41] that the generalization from one-dimensional methods to methods that compute invariant subspaces for matrices is not always straight-forward and may fail.

Bibliography

1
Z. Bai., J. Demmel, J. Dongorra, A. Ruhe, and H. van der Vorst.
Templates for the solution of algebraic eigenvalue problems.
SIAM, Philadelphia, 2000.

2
P. Benner and D. Kressner.
Balancing sparse Hamiltonian eigenproblems.
Linear Algebra Appl.415(1):3-19, 2006.

3
P. Benner and D. Kressner.
Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II.
ACM Trans. Math. Software, 32(2):352-373, 2006.

4
P. Benner, D. Kressner, and V. Mehrmann.
Structure preservation: A challenge in computational control.
Future Generation Computer Systems, 19(7):1243-1252, 2003.

5
P. Benner, D. Kressner, and V. Mehrmann.
Skew-hamiltonian and hamiltonian eigenvalue problems: Theory, algorithms and applications.
In Proceedings of ApplMath03, Brijuni (Croatia), June 23-27. Kluwer, 2005.

6
T. Betcke and H. Voss.
A Jacobi-Davidson-type Projection Method for Nonlinear Eigenvalue Problems.
Future Generation Computer Systems, 20:363--372, 2004.

7
R. Byers and D. Kressner.
On the condition of a complex eigenvalue under real perturbations.
BIT Numerical Mathematics, 44(2):209-215, 2004.

8
R. Byers and V. Mehrmann and H. Xu.
Staircase forms and trimmed linearization for structured matrix polynomials.
Preprint 395, DFG Research Center Matheon in Berlin, 2007.

9
D. Chu, X. Liu, and V. Mehrmann.
A numerically strongly stable method for computing the Hamiltonian Schur form.
Numer. Math., 105(3):375-412, 2007.

10
H. Fassbender, N. Mackey, D. S. Mackey and C. Schröder.
A structured polynomial eigenproblem arising in the analysis of time delay systems and related polynomial eigenproblems.
Preprint TU Braunschweig, 2007.

11
I. Gohberg, P. Lancaster, and L. Rodman.
Matrix polynomials.
Academic Press, New York, 1982.

12
N. Higham, D. Mackey, and F. Tisseur.
The conditioning of linearization of matrix polynomials.
SIAM J. Matrix Anal. Appl., 28(4):1005-1028, 2006.

13
A. Hilliges.
Numerische Lösung von quadratischen Eigenwertproblemen mit Anwendung in der Schienendynamik.
Diplomarbeit, TU Berlin, Inst. f. Mathematik, 2004.

14
A. Hilliges, C. Mehl, and V. Mehrmann.
On the solution of palindromic eigenvalue problems.
In Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS). Jyväskylä, Finland, 2004.
CD-ROM.

15
T.-M. Hwang, W.-W. Lin, and V. Mehrmann.
Numerical solution of quadratic eigenvalue problems with structure-preserving methods.
SIAM J. Sci. Comput., 24(4):1283-1302, 2003.

16
I. Ipsen.
Accurate eigenvalues for fast trains.
SIAM News, 37(9):1-2, 2004.

17
M. Karow, D. Kressner, and F. Tisseur.
Structured eigenvalue condition numbers.
SIAM J. Matrix Anal. Appl., 28(4):1052-1068, 2006.

18
D. Kressner.
Block algorithms for orthogonal symplectic factorizations.
BIT Numerical Mathematics, 43(4):775-790, 2003.

19
D. Kressner.
The periodic QR algorithm is a disguised QR algorithm.
Linear Algebra Appl., 417(2-3):423-433, 2006.

20
D. Kressner.
Perturbation bounds for isotropic invariant subspaces of skew-Hamiltonian matrices.
SIAM J. Matrix Anal. Appl., 26(4):947-961, 2005.

21
D. Kressner.
A Krylov-Schur algorithm for matrix products.
Numer. Math., 103(3):461-483, 2006.

22
D. Kressner.
Numerical methods for general and structured eigenvalue problems.
Springer, Heidelberg. Lecture Notes in Computational Science and Engineering, vol. 46., 2005.

23
D. Kressner, C. Schröder and D. S. Watkins.
Implicit QR Algorithms for Palindromic and Even Eigenvalue Problems.
Preprint 432, DFG Research Center Matheon in Berlin, 2008.

24
D. Mackey, N. Mackey, C. Mehl, and V. Mehrmann.
Structured polynomial eigenvalue problems: Good vibrations from good linearizations.
SIAM J. Matrix Anal. Appl., 28:1029-1051,2006.

25
D. Mackey, N. Mackey, C. Mehl, and V. Mehrmann.
Vector spaces of linearizations for matrix polynomials.
SIAM J. Matrix Anal. Appl., 28:971-1004,2006.

26
C. Mehl.
Jacobi-like algorithms for the indefinite generalized Hermitian eigenvalue problem.
SIAM J. Matrix Anal. Appl., 25:964-985, 2004.

27
C. Mehl.
On classification of normal matrices in indefinite inner product spaces: the complex case.
Electron. J. Linear Algebra, 15: 50-83, 2006.

28
C. Mehl.
On asymptotic convergence of nonsymmetric Jacobi algorithms.
SIAM J. Matrix Anal. Appl.30:291--311, 2008.

29
V. Mehrmann and H. Voss.
Nonlinear eigenvalue problems: A challenge for modern eigenvalue methods.
Mitt. der Ges. f. Ang. Mathematik und Mechanik, 27:121-151, 2005.

30
V. Mehrmann and D. Watkins.
Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltoninan/Hamiltonian pencils.
SIAM J. Sci. Comput., 22:1905-1925, 2001.

31
C. Otto.
Arnoldi and Jacobi-Davidson methods for quadratic eigenvalue problems.
Diplomarbeit, TU Berlin, Inst. f. Mathematik, 2004.

32
C. Schmidt, T. Friese, L. Zschiedrich, and P. Deuflhard.
Adaptive multigrid methods for the vectorial maxwell eigenvalue problem for optical waveguide design.
ZIB-report 00-54, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000.

33
K. Schreiber.
Nonlinear Eigenvalue Problems: Newton-type Methods and Nonlinear Rayleigh Functionals.
PhD Thesis, TU Berlin, Institut für Mathematik, 2008.
submitted.

34
C. Schröder.
A Structured Kronecker form for the Palindromic Eigenvalue Problem
Proc. Appl. Math. and Mech., GAMM Annual Meeting 2006 - Berlin, 6:721-722, 2006.

35
C. Schröder.
URV decomposition based structured methods for palindromic and even eigenvalue problems.
Preprint 375, DFG Research Center Matheon in Berlin, 2007.

36
Christian Schröder
A QR-like algorithm for the palindromic eigenvalue problem.
Preprint 388, DFG Research Center Matheon in Berlin, 2007.

37
Christian Schröder and Tatjana Stykel,
Passivation of LTI systems,
Preprint DFG Research Center Matheon in Berlin, 2007

38
Christian Schröder
A canonical form for palindromic pencils and palindromic factorizations,
Preprint 316, DFG Research Center Matheon in Berlin, 2006.

39
Christian Schröder
Palindromic and Even Eigenvalue Problems -- Analysis and Numerical Methods.
PhD Thesis, TU Berlin, Institut für Mathematik, 2008.
submitted.

40
H. Schwetlick and K. Schreiber.
A primal-dual Jacobi-Davidson-like method for nonlinear eigenvalue problems,
Preprint TU Dresden ZIH-IR-0613, 2006.

41
H. Schwetlick and K. Schreiber.
A Counterexample for Characterizing an Invariant Subspace by a Singularity System.
Preprint 419, DFG Research Center Matheon in Berlin, 2007.

42
F. Tisseur and K. Meerbergen.
A survey of the quadratic eigenvalue problem.
SIAM Rev., 43:234-286, 2001.

43
H. Voss
An Arnoldi Method for Nonlinear Eigenvalue Problems.
BIT,44:387--401, 2004.

last modified April 03, 2008