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 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.
- [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.
-
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.
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 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.
- [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.
|
|