PCMF: Parallel Computation of Matrix Functions

Introduction
Reports and Papers
Software
People
Conferences
Contact us
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 righthand 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 mentionedthe inverse, sign, exponential and
logarithmare too expensive to compute,
and alternative methods of solving the problems at hand should be used.
However, it is now well established that in highperformance 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
highperformance 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.
 [1]
A Block Algorithm for Matrix 1Norm Estimation, with an Application
to 1Norm Pseudospectra,
(Nicholas J. Higham and Françoise Tisseur),
SIAM J. Matrix Anal. Appl., 21(4): 11851201, 2000.
 [2]
Return to the Middle Ages: A HalfAngle 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): 11121125, 2001.
LogPack.tar.
 [4]
Evaluating Padé Approximants of the Matrix Logarithm,
(Nicholas J. Higham),
SIAM J. Matrix Anal. Appl., 22(4): 11261135, 2001.
 [5]
Parallel Implementation of a Block Algorithm for Matrix 1Norm
Estimation,
(Sheung Hun Cheng and Nicholas J. Higham),
In R. Sakellariou, J. Keane, J. Gurd, and L. Freeman, editors,
EuroPar 2001,
Parallel Processing, volume 2150 of Lecture Notes in
Computer Science, pages 568577. SpringerVerlag, Berlin, 2001.
 [6]
Implementation for LAPACK of a Block Algorithm for Matrix 1Norm
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.
Grantholders

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
External Directorate
Collaborators
 Dr. Charles Kenney works halftime as a Numerical Analyst
at the Naval Weapons Center, China Lake, California, and
halftime 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.
 [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 1Norm
Estimation''
 [C]
European Conference on Parallel Computing (EuroPar), Manchester, August 2001.

`` Parallel Implementation of a Block Algorithm for Matrix 1Norm
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 1Norm Estimation,
with an Application to 1Norm 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 HalfAngle Iteration for the
Logarithm of a Unitary Matrix''
 [T]
SIAM Annual Meeting, Atlanta, Georgia, May, 1999.

``A Block Algorithm for Matrix 1Norm Estimation''
 [T]
Householder Symposium XIV, Whistler B.C., Canada, June 1999.

``A Block Algorithm for Matrix 1Norm Estimation,
with an Application to 1Norm Pseudospectra''

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

