PCMF: Parallel Computation of Matrix Functions

Introduction

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

• Functions condest and normest1, implementing the algorithm of [1] are part of MATLAB 6.
• Routine ZLACON in LAPACK 3.0 incorporates improvements to the original LAPACK norm estimator identified in [1].
• LAPACK programming style routines DLACN1 and ZLACN1 plus their dependencies, as described in [6], can be downloaded here. dlacn1.tar, zlacn1.tar.
• LAPACK programming style routine for approximating the logarithm of a matrix, as described in [3], can be downloaded here. LogPack.tar.
• For an example of where the matrix square root and logarithm algorithms developed in this project are being used, see GluCat: Generic library of universal Clifford algebra templates.

People

• Prof. Nick Higham is the Richardson Professor of Applied Mathematics at the University of Manchester.
• Dr. Len Freeman is a Senior Lecturer in Computer Science and Mathematics at the University of Manchester. He is also the Director of CNC.
• Prof. John Gurd is a Professor of Computer Science at the University of Manchester.

Research Staff

• Dr. Bobby Cheng is a Research Associate in the CNC. From December 2001 he is a Numerical Analyst at The MathWorks, Inc.

External Directorate

• Dr. Cliff Addison is Research Manager of the Languages and Tools group at the Fujitsu European Centre for Information Technology Ltd. (FECIT).
• Prof. Sven Hammarling is Principal Consultant at The Numerical Algorithms Group Ltd. (NAg).
• Dr. Mark Smith is a Research Scientist at DERA.

Collaborators

• Dr. Charles Kenney works half-time as a Numerical Analyst at the Naval Weapons Center, China Lake, California, and half-time as a Research Engineer in the Electrical and Computer Engineering Department at the University of California, Santa Barbara.
• Prof. Alan Laub is Dean of the College of Engineering, University of California, Davis.
• Dr. Françoise Tisseur is Colin Roscoe Lecturer in Numerical Analysis at the University of Manchester.

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

Last updated: Wed May 29, 2002.