PCMF: Parallel Computation of Matrix Functions

| Introduction| Reports and Papers| Software| People| Conferences| Contact us|

Introduction

This EPSRC (50%) and DERA (50%) jointly funded project started on October 20, 1998 and runs for 36 months employing one research associate. The project spans the research interests of the Numerical Analysis Group in the Department of Mathematics and the Centre for Novel Computing (CNC) in the Department of Computer Science.

Many of the major linear algebra problems in scientific computing involve, or can be reduced to, the computation of matrix functions (in this project we are specifically concerned with functions of dense matrices). For example, solving a square, nonsingular system of equations Ax=b can be achieved by computing the function A-1 and applying it to the right-hand side b. Finding which eigenvalues of a matrix lie in a given region of the complex plane can be done by computing and extracting subspace information from the matrix sign function. The solution of ordinary differential equations is intimately connected with the matrix exponential and logarithm.

The traditional view, coloured by experience in serial computation, is that the matrix functions just mentioned--the inverse, sign, exponential and logarithm--are too expensive to compute, and alternative methods of solving the problems at hand should be used. However, it is now well established that in high-performance computing environments floating point operation (flop) counts can be a poor measure of performance and there is therefore much interest in using matrix function techniques.

The aim of this project is to develop new algorithms, theory and analysis for parallel computation of some matrix functions arising in important application areas. The functions chosen correspond to major computational tasks arising in science and engineering problems that currently occupy large amounts of high-performance computing time. Since we are concerned with accuracy and stability as well as computing time, we also aim to derive parallel techniques for estimating condition numbers, thereby providing error bounds for the computed quantities.

This work is divided into 3 workpackages (WPs):

WP1: Parallel Condition Number Estimation;
WP2: Parallel Algorithms for the Matrix Square Root and Related Functions;
WP3: Parallel Algorithms for the Matrix Exponential and Matrix Logarithm.

Reports and Papers

[1] A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra, (Nicholas J. Higham and Françoise Tisseur), SIAM J. Matrix Anal. Appl., 21(4): 1185-1201, 2000.
[2] Return to the Middle Ages: A Half-Angle Iteration for the Logarithm of a Unitary Matrix, (Sheung Hun Cheng, Nicholas J. Higham, Charles S. Kenney, Alan J. Laub), Proceedings of the Fourteenth International Symposium of Mathematical Theory of Networks and Systems, Perpignan, France, 2000.
[3] Approximating the Logarithm of a Matrix to Specified Accuracy, (Sheung Hun Cheng, Nicholas J. Higham, Charles S. Kenney, Alan J. Laub), SIAM J. Matrix Anal. Appl., 22(4): 1112-1125, 2001. LogPack.tar.
[4] Evaluating Padé Approximants of the Matrix Logarithm, (Nicholas J. Higham), SIAM J. Matrix Anal. Appl., 22(4): 1126-1135, 2001.
[5] Parallel Implementation of a Block Algorithm for Matrix 1-Norm Estimation, (Sheung Hun Cheng and Nicholas J. Higham), In R. Sakellariou, J. Keane, J. Gurd, and L. Freeman, editors, Euro-Par 2001, Parallel Processing, volume 2150 of Lecture Notes in Computer Science, pages 568-577. Springer-Verlag, Berlin, 2001.
[6] Implementation for LAPACK of a Block Algorithm for Matrix 1-Norm Estimation, (Sheung Hun Cheng and Nicholas J. Higham), NA Report 393, MCCM, August 2001. Also as LAPACK Working Note 152. dlacn1.tar, zlacn1.tar.
[7] Final Report on the project, January 2002.

Software


People

Grantholders

Research Staff

External Directorate

Collaborators


Conferences [talk presented by C-Cheng, H-Higham, L-Laub, T-Tisseur]

[C] Dundee Biennial Conference on Numerical Analysis, June 1999.
``Approximating the Logarithm of a Matrix with Variable Accuracy''
[C] British Applied Mathematics Colloquium, UMIST, April 2000.
``Novel Parallel Computation of Structured Matrix Functions''
[C] Dundee Biennial Conference on Numerical Analysis, June 2001.
`` Parallel Implementation of a Block Algorithm for Matrix 1-Norm Estimation''
[C] European Conference on Parallel Computing (Euro-Par), Manchester, August 2001.
`` Parallel Implementation of a Block Algorithm for Matrix 1-Norm Estimation''
[H] Householder Symposium XIV, Whistler, BC, Canada, June 1999.
``Approximating the Logarithm of a Matrix with Variable Accuracy''
[H] Dundee Biennial Conference on Numerical Analysis, June 1999.
``A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra''
[H] Department of Computer Science, Cornell University, October 1999.
``Approximating the Logarithm of a Matrix to Specified Accuracy''
[H] DERA (Malvern), November 1999.
``Computing Matrix Functions''
[H] Theoretical Physics and Applied Mathematics Department, Liverpool University, January 2000.
``Computing the Matrix Logarithm''
[H] Leicester Y2K Applied Maths Day, University of Leicester, January 2000.
``Computing the Matrix Logarithm''
[H] British Applied Mathematics Colloquium, UMIST, April 2000,
``Why and How to Compute Functions of a Matrix''
[L] International Symposium of Mathematical Theory of Networks and Systems, Perpignan, France, 2000.
``Return to the Middle Ages: A Half-Angle Iteration for the Logarithm of a Unitary Matrix''
[T] SIAM Annual Meeting, Atlanta, Georgia, May, 1999.
``A Block Algorithm for Matrix 1-Norm Estimation''
[T] Householder Symposium XIV, Whistler B.C., Canada, June 1999.
``A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra''

|
Introduction| Reports and Papers| Software| People| Conferences| Contact us|
Last updated: Wed May 29, 2002.
[cnclogo]