Group project Computational Science 2000-2001

Contents

This project is a fourth year course for students Computational Science at the Utrecht University. Eight students started in September 2000 and presented their results in February 2001. The supervisor of the project was prof. dr. H.A. van der Vorst.


Pseudospectra

Eigenvalues of a matrix (or linear operator) reveal important information about the properties of the concerning matrix. As Trefethen [1] says, there are (at least) three useful reasons to study eigenvalues. First, if a matrix can be diagonalized, a speedup in computing the solution can be obtained. Furthermore, eigenvalues tell something about the physical behavior of a certain system, like stability, growth or decay. Also, eigenvalues make it easier for a human to visualize and interpret a matrix.

However, computation of the eigenvalues of a matrix in a standard way is expensive and, more important, does not give reliable results for highly nonnormal matrices. A matrix is nonnormal if the eigenvectors are not orthogonal and, as a consequence, the condition number of the matrix of eigenvectors may be very large. Pseudospectra may help in this case.

There are several ways to compute the pseudospectrum of a matrix and many implementations are available. Generally speaking, there are two approaches known. The first simply computes the whole pseudospectrum on a given domain. In general, this is a robust but very expensive approach. Another approach is known as curve tracing, which is based on a curve tracing following algorithm, which promises to be less costly and more accurate. This method was first proposed by Brühl [2]. We studied this approach and an implementation was developed.


Matlab Pseudospectrum Continuer

The Matlab Pseudospectrum Continuer (MPC) is a tool built in MATLAB® which enables the user to interactively create and study the pseudospectrum of a user-specified matrix using curve tracing with predictor-corrector methods. Various information is shown during this process and the controls provide the user with tools for system control and program control, the ability to import and export systems, curve selection, etc.

The continuer was built with the following goals in mind:


Results

Two applications were investigated. Firstly, pseudospectra may be useful when applied to unstable electronic circuits. This proved to be difficult. Secondly, a simple model of water transport in the Atlantic Ocean was studied. The results can be found in the report.

The progress of the project was monitored, and various research-results were published at an online project site. A static mirror of the final site can be found here.


Download


Related sites


Acknowledgements

This project finished in February 2001. The following people were part of the CS2000 team. Without their unimaginable and continuous efforts, this project would never have been possible.

If you have any questions or suggestions about pseudospectra or the MPC or any other related subject, do not hesitate to contact us. Please bear in mind that the current contact information may change in the near future. You may also contact us through our teacher Henk A. van der Vorst.

CS2000 would especially like to thank Jos van Dorsselaer, Wim Bomhof, Hans Dijkstra, Michiel Hochstenbach et al. for giving invaluable information about pseudospectra and other subjects.


Bibliography

  1. L. N. Trefethen, Pseudospectra of linear operators, SIAM Review 39:383-406, 1997
  2. M. Brühl, A curve tracing algorithm for computing the pseudospectrum, BIT 36(3):441-445, 1996

Last update: September 7, 2001