%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nicholas J. Higham",
%%% version = "1.00",
%%% date = "March 10, 2014",
%%% time = "",
%%% filename = "u-manchester-mccm.bib",
%%% address = "Department of Mathematics
%%% University of Manchester
%%% Manchester M13 9PL
%%% England",
%%% telephone = "+44 (0)161 275 5800",
%%% FAX = "+44 (0)161 275 5819",
%%% checksum = ""
%%% email = "nick.higham@manchester.ac.uk",
%%% codetable = "ISO/ASCII",
%%% keywords = "bibliography, Manchester, numerical
%%% analysis",
%%% supported = "yes",
%%% docstring = "BibTeX bibliography for the Numerical
%%% Analysis Reports of the Manchester Centre for
%%% Computational Mathematics
%%% (University of Manchester and UMIST)."
%%% }
%%% ====================================================================
%%% The URL (Uniform Resource Locator) of this file is
%%%
%%% URL = "http://www.maths.manchester.ac.uk/~higham/narep/u-manchester-mccm.bib"
%%%
%%% This is narep.bib, the index for the Numerical Analysis Reports of the
%%% Manchester Centre for Computational Mathematics
%%% (University of Manchester and UMIST).
%%% It is in BibTeX form, with additional fields.
%%% Entries are in reverse chronological order.
@String{inst-MCCM = "Manchester Centre for
Computational Mathematics"}
@String{inst-MCCM:adr = "Manchester, England"}
%%% Numerical Analysis Reports: ISSN 1360-1725
@String{t-NAREP = "Numerical Analysis Report"}
@String{inst-U-MANCHESTER = "University of Manchester"}
@String{inst-U-MANCHESTER:adr = "Manchester M13 9PL, England"}
@String{pub-LONGMAN = "Longman Scientific and Technical"}
@String{pub-LONGMAN:adr = "Essex, UK"}
@String{pub-OUP = "Oxford University Press"}
@String{pub-OUP:adr = "Oxford, UK"}
@String{pub-SV = "Spring{\-}er-Ver{\-}lag"}
@String{pub-SV:adr = "Berlin, Germany~/ Heidelberg,
Germany~/ London, UK~/ etc."}
%%% ====================================================================
@techreport{Guo:2005:SNM,
author = "Chun-Hua Guo and Nicholas J. Higham",
title = "A {Schur--Newton} Method for the Matrix $p$th Root and its Inverse",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 475",
pages = "17",
month = oct,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep475.pdf",
abstract = "Newton's method for the inverse matrix $p$th root, $A^{-1/p}$, has
the attraction that it involves only matrix multiplication. We
show that if the starting matrix is $c^{-1}I$ for $c\in\R^+$ then
the iteration converges quadratically to $A^{-1/p}$ if the
eigenvalues of $A$ lie in a wedge-shaped convex set containing the
disc $\{\, z: |z-c^p| < c^p\,\}$. We derive an optimal choice of
$c$ for the case where $A$ has real, positive eigenvalues. An
application is described to roots of transition matrices from
Markov models, in which for certain problems the convergence
condition is satisfied with $c=1$. Although the basic Newton
iteration is numerically unstable, a coupled version is stable and
a simple modification of it provides a new coupled iteration for
the matrix $p$th root. For general matrices we develop a hybrid
algorithm that computes a Schur decomposition, takes square roots
of the upper (quasi)triangular factor, and applies the coupled
Newton iteration to a matrix for which fast convergence is
guaranteed. The new algorithm can be used to compute either
$A^{1/p}$ or $A^{-1/p}$, and for large $p$ that are not highly
composite it is more efficient than the method of Smith based
entirely on the Schur decomposition.",
keywords = "Matrix $p$th root, principal $p$th root, matrix logarithm, inverse,
Newton's method, preprocessing, Schur decomposition, numerical
stability, convergence, Markov model, transition matrix"
}
@techreport{Elman:05:IFI,
author = "Howard Elman and Alison Ramage and David Silvester",
title = "IFISS: a {Matlab} Toolbox for Modelling Incompressible Flow",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 474",
month = oct,
year = 2005,
note = "Submitted to ACM Transactions on Mathematical Software",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep474.pdf",
abstract = "IFISS is a graphical Matlab package for the interactive numerical study
of incompressible flow problems. It includes algorithms for discretisation by
mixed finite element methods and a posteriori error estimation of the
computed solutions. The package can also be used as
a computational laboratory for experimenting with state-of-the-art
preconditioned iterative solvers for the discrete linear equation systems that
arise in incompressible flow modelling. A unique feature of the package is its
comprehensive nature; for each
problem addressed, it enables the study of both discretisation and iterative
solution algorithms as well as the interaction between the two and the
resulting effect on overall efficiency."
}
@techreport{Tisseur:05:SCN,
author = "Fran\c{c}oise Tisseur and Stef Graillat",
title = "Structured Condition Numbers and Backward Errors
in Scalar Product Spaces",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 473",
pages = "21",
month = sep,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep473.pdf",
abstract = "We investigate the effect of structure-preserving perturbations on the
solution to a linear system, matrix inversion, and distance to
singularity. Particular attention is paid to linear and nonlinear
structures that form Lie algebras, Jordan algebras and automorphism
groups of a scalar product. These include complex symmetric,
pseudo-symmetric, persymmetric, skew-symmetric, Hamiltonian, unitary,
complex orthogonal and symplectic matrices. We show that under mild
assumptions on the scalar product, there is little or no difference
between structured and unstructured condition numbers and distance to
singularity for matrices in Lie and Jordan algebras. Hence, for these
classes of matrices, the usual unstructured perturbation analysis is
sufficient. We show this is not true in general for structures in
automorphism groups. Bounds and computable expressions for the
structured condition numbers for a linear system and matrix inversion
are derived for these nonlinear structures.
Structured backward errors for the approximate solution of linear
systems are also considered. Conditions are given for the structured
backward error to be finite. We prove that for Lie and Jordan
algebras, whenever the structured backward error is finite, it is
within a small factor of the unstructured one. The same conclusion
holds for orthogonal and unitary structures but cannot easily be
extended to other matrix groups. For some nonlinear structures such as
complex orthogonal, we show that the structured backward error can be
rewritten in terms of a challenging Procrustes problem.
This work extends and unifies earlier analyses.",
keywords = "structured matrices, normwise structured perturbations, structured
linear systems, condition number, backward error, distance to
singularity, Lie algebra, Jordan algebra, automorphism group, scalar
product, bilinear form, sesquilinear form, orthosymmetric."
}
@techreport{MCCM:2005:AR4,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 2004",
type = t-NAREP,
number = "No. 472",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "25",
month = sep,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep472.pdf"
}
@techreport{Bhatia:2005:IDM,
author = "Rajendra Bhatia",
title = "Infinitely Divisible Matrices",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 471",
pages = "36",
month = aug,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep471.pdf"
}
@techreport{Lancaster:2005:NWS,
author = "Peter Lancaster and Panayiotis Psarrakos",
title = "A Note on Weak and Strong Linearizations of
Regular Matrix Polynomials",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 470",
pages = "6",
month = jun,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep470.pdf"
}
@techreport{Berhanu:05:PBH,
author = "Michael Berhanu",
title = "Perturbation Bounds for Hyperbolic Matrix Factorizations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 469",
pages = "24",
month = jun,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep469.pdf",
abstract = "Several matrix factorizations depend on orthogonal factors,
matrices that preserve the Euclidean scalar product. Some of these
factorizations can be extended and generalized to
$(J,\Jt)$-orthogonal factors, that is, matrices that satisfy
$H^TJH=\Jt$, where $J$ and $\Jt$ are diagonal with diagonal
elements $\pm1$. The purpose of this work is to analyze the
perturbation of matrix factorizations that have a
$(J,\Jt)$-orthogonal or orthogonal factor and to give first order
perturbation bounds. For each factorization analyzed, we give the
sharpest possible first order bound, which yields a condition
number. The cost of computing these condition numbers is high. It
is usually equivalent to computing the $2$-norm of an $n^2\times
n^2$ matrix for a problem of size $n$. Thus, we also propose less
sharp bounds that are less expensive to compute.",
keywords = "Condition number, hyperbolic matrix factorization, manifold"
}
@techreport{Higham:05:IPL,
author = "Nicholas J. Higham",
title = "An Interview with {Peter Lancaster}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 468",
pages = "10",
month = jun,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep468.pdf",
}
@techreport{Tisseur:05:SEC,
author = "Michael Karow and Daniel Kressner and Fran\c{c}oise Tisseur",
title = "Structured Eigenvalue Condition Numbers",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 467",
pages = "16",
month = apr,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep467.pdf",
abstract = "This paper investigates the effect of structure-preserving
perturbations on the eigenvalues of linearly and nonlinearly
structured eigenvalue problems. Particular attention is paid to
structures that form Jordan algebras, Lie algebras, and automorphism
groups of a scalar product. Bounds and computable expressions for
structured eigenvalue condition numbers are derived for these classes
of matrices, which include complex symmetric, pseudo symmetric,
persymmetric, skew-symmetric, Hamiltonian, symplectic, and orthogonal
matrices. In particular we show that under mild assumptions on the
scalar product, the structured and unstructured eigenvalue condition
numbers are equal for structures in Jordan algebras. For Lie
algebras, the effect on the condition number of incorporating
structure varies greatly with the structure. We identify Lie
algebras for which structure does not affect the eigenvalue condition
number.",
keywords = "Structured eigenvalue problem, condition number, Jordan algebra,
Lie algebra, automorphism group, symplectic, perplectic,
pseudo-orthogonal, pseudo-unitary, complex symmetric, persymmetric,
perskew-symmetric, Hamiltonian, skew-Hamiltonian, structure
preservation."
}
@techreport{Mackey:2005:PPE,
author = "D. Steven Mackey and Niloufer Mackey and Christian Mehl and
Volker Mehrmann",
title = "Palindromic Polynomial Eigenvalue Problems: {Good} Vibrations from
Good Linearizations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 466",
pages = 26,
month = apr,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep466.pdf",
abstract = "Palindromic polynomial eigenvalue problems and related classes of
structured eigenvalue problems are considered. These structures
generalize the concepts of symplectic and Hamiltonian matrices to
matrix polynomials. We discuss several applications where these
matrix polynomials arise, and show how linearizations can be
derived that re ect the structure of all these structured matrix
polynomials and therefore preserve symmetries in the spectrum.",
keywords = "nonlinear eigenvalue problem, palindromic matrix polynomial, even
matrix polynomial, odd matrix polynomial, Cayley transformation,
linearization, Hamiltonian matrix, symplectic matrix"
}
@techreport{Higham:2005:CLM,
author = "Nicholas J. Higham and D. Steven Mackey and Fran\c{c}oise Tisseur",
title = "The Conditioning of Linearizations of Matrix Polynomials",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 465",
pages = "25",
month = apr,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep465.pdf",
abstract = "The standard way of solving the polynomial eigenvalue problem of
degree $m$ in $n\times n$ matrices is to ``linearize'' to a pencil
in $mn\times mn$ matrices and solve the generalized eigenvalue
problem. For a given polynomial, $P$, infinitely many
linearizations exist and they can have widely varying eigenvalue
condition numbers. We investigate the conditioning of
linearizations from a vector space $\mathbb{DL}(P)$ of pencils
recently identified and studied by Mackey, Mackey, Mehl, and
Mehrmann. We look for the best conditioned linearization and
compare the conditioning with that of the original polynomial. Two
particular pencils are shown always to be almost optimal over
linearizations in $\mathbb{DL}(P)$ for eigenvalues of modulus
greater than or less than 1, respectively, provided that the
problem is not too badly scaled and that the pencils are
linearizations. Moreover, under this scaling assumption, these
pencils are shown to be about as well conditioned as the original
polynomial. For quadratic eigenvalue problems that are not too
heavily damped, a simple scaling is shown to convert the problem
to one that is well scaled. We also analyze the eigenvalue
conditioning of the widely used first and second companion
linearizations. The conditioning of the first companion
linearization relative to that of $P$ is shown to depend on the
coefficient matrix norms, the eigenvalue, and the left \ev s of
the linearization and of $P$. The companion form is found to be
potentially much more ill conditioned than $P$, but if the 2-norms
of the coefficient matrices are all approximately 1 then the
companion form and $P$ are guaranteed to have similar condition
numbers. Analogous results hold for the second companion form. Our
results are phrased in terms of both the standard relative
condition number and the condition number of Dedieu and Tisseur
for the problem in homogeneous form, this latter condition number
having the advantage of applying to zero and infinite
eigenvalues.",
keywords = "matrix polynomial, matrix pencil, linearization, companion form,
condition number, homogeneous form, quadratic eigenvalue problem,
vector space, scaling"
}
@techreport{Mackey:2005:VSL,
author = "D. Steven Mackey and Niloufer Mackey and Christian Mehl and
Volker Mehrmann",
title = "Vector Spaces of Linearizations for Matrix Polynomials",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 464",
pages = "32",
month = apr,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep464.pdf",
abstract = "The classical approach to investigating polynomial eigenvalue
problems is linearization, where the polynomial is converted into
a larger matrix pencil with the same eigenvalues. For any
polynomial there are in nitely many linearizations with widely
varying properties, but in practice the companion forms are
typically used. However, these companion forms are not always
entirely satisfactory, and linearizations with special properties
may sometimes be required. In this paper we develop a systematic
approach to generating large classes of linearizations for matrix
polynomials. Given a polynomial P, we show how to simply construct
two vector spaces of pencils that generalize the companion forms
of P, and prove that almost all of these pencils are
linearizations for P. Eigenvectors of these pencils are shown to
be closely related to those of P. A distinguished subspace is then
isolated, and the special properties of these pencils are
investigated. These spaces of pencils provide a convenient arena
in which to look for structured linearizations of structured
polynomials, as well as to try to optimize the conditioning of
linearizations, issues to be addressed in further work.",
keywords = "matrix polynomial, matrix pencil, linearization, strong
linearization, shifted sum, companion form"
}
@techreport{Lancaster:2005:CFS,
author = "Peter Lancaster and Leiba Rodman",
title = "Canonical Forms for Symmetric/Skew-symmetric Real Matrix Pairs
under Strict Equivalence and Congruence",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 463",
pages = "77",
month = mar,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep463.pdf",
abstract = "A systematic development is made of the simultaneous reduction of
pairs of quadratic forms over the reals, one of which is
skew-symmetric and the other is either symmetric or
skew-symmetric. These reductions are by strict equivalence and by
congruence, over the reals or over the complex numbers, and
essentially complete proofs are presented. Some closely related
results which can be derived from the canonical forms of pairs of
symmetric/skew-symmetric real forms are also included. They
concern simultaneously neutral subspaces, Hamiltonian and
skew-Hamiltonian matrices, and canonical structures of real
matrices which are selfadjoint or skew-adjoint in a regular
skew-symmetric indefinite inner product, and real matrices which
are skew-adjoint in a regular symmetric indefinite inner product.
The paper is largely expository, and continues the comprehensive
account of the reduction of pairs of matrices started in a
preceding paper.",
keywords = ""
}
@techreport{Lancaster:2005:ISP,
author = "Peter Lancaster",
title = "Inverse Spectral Problems for Semi-simple Damped Vibrating Systems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 462",
pages = "24",
month = mar,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep462.pdf",
abstract = "Computational schemes are investigated for the solution of inverse
spectral problems for $n\times n$ real systems of the form
$L(\la)=M\la^2 +D\la +K$. Thus, admissible sets of data concerning
systems of eigenvalues and eigenvectors are examined and
procedures for generating associated (isospectral) families of
systems are developed. The analysis includes symmetric systems,
systems with mixed real/non-real spectrum, systems with positive
definite coefficients, and hyperbolic systems (with real
spectrum). A one-to-one correspondence between Jordan pairs and
structure preserving similarities is clarified. An examination of
complex symmetric matrices is included.",
keywords = ""
}
@techreport{Hargreaves:2005:EAM,
author = "Gareth I. Hargreaves and Nicholas J. Higham",
title = "Efficient Algorithms for the Matrix Cosine and Sine",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "461",
pages = "17",
month = feb,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep461.pdf",
abstract = "Several improvements are made to an algorithm of Higham and Smith
for computing the matrix cosine. The original algorithm scales the
matrix by a power of 2 to bring the $\infty$-norm to 1 or less,
evaluates the [8/8] Pad\'e approximant, then uses the double-angle
formula $\cos(2A) = 2\cos^2A - I$ to recover the cosine of the
original matrix. The first improvement is to phrase truncation
error bounds in terms of $\norm{A^2}^{1/2}$ instead of the (no
smaller and potentially much larger quantity) $\norm{A}$. The
second is to choose the degree of the Pad\'e approximant to
minimize the computational cost subject to achieving a desired
truncation error. A third improvement is to use an absolute,
rather than relative, error criterion in the choice of Pad\'e
approximant; this allows the use of higher degree approximants
without worsening an a priori error bound. Our theory and
experiments show that each of these modifications brings a
reduction in computational cost. Moreover, because the
modifications tend to reduce the number of double-angle steps they
usually result in a more accurate computed cosine in floating
point arithmetic. We also derive an algorithm for computing both
$\cos(A)$ and $\sin(A)$, by adapting the ideas developed for the
cosine and intertwining the cosine and sine double angle
recurrences.",
keywords = "matrix function, matrix cosine, matrix sine, matrix exponential,
Taylor series, Pad\'e approximation, Pad\'e approximant,
double-angle formula, rounding error analysis, Schur--Parlett
method, MATLAB "
}
@techreport{Lancaster:2005:CFH,
author = "Peter Lancaster and Leiba Rodman",
title = "Canonical Forms for Hermitian Matrix Pairs
under Strict Equivalence and Congruence",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 460",
pages = "45",
month = jan,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep460.pdf",
abstract = "After a brief historical review and an account of the canonical
forms attributed to Jordan and Kronecker, a systematic development
is made of the simultaneous reduction of pairs of quadratic forms
over the complex numbers and over the reals. These reductions are
by strict equivalence and by congruence and essentially complete
proofs are presented. Some closely related results which can be
derived from the canonical forms are also included. They concern
simultaneous diagonalization, a new criterion for the existence of
positive definite linear combinations of a pair of hermitian
matrices, and the canonical structures of matrices which are
selfadjoint in an indefinite inner product. ",
keywords = "",
note = "To appear in SIAM Review."
}
@techreport{Lancaster:2005:IVS2,
author = "Uwe Prells and Peter Lancaster",
title = "Isospectral Vibrating Systems. {Part 2}: Structure Preserving
Transformations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 459",
pages = "23",
month = jan,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep459.pdf",
abstract = "The study of inverse problems for $n\times n$ systems of the form
$L(\la):=M\la^2 +D\la +K$ is continued. In this paper it is
assumed that one vibrating system is specified and the objective
is to generate isospectral families of systems, i.e. systems which
reproduce precisely the eigenvalues of the given system together
with their multiplicities. Two central ideas are developed and
used, namely, standard triples of matrices, and structure
preserving transformations.",
keywords = ""
}
@techreport{Lancaster:2005:IVS1,
author = "Peter Lancaster",
title = "Isospectral Vibrating Systems. {Part 1}: The Spectral Method",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 458",
pages = "17",
month = jan,
year = "2005",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep458.pdf",
abstract = "A study is made of inverse problems for $n\times n$ systems of the
form $L(\la)=M\la^2 +D\la +K$. This paper concerns the
determination of systems in an equivalence class defined by a
fixed $2n\times 2n$ admissible Jordan matrix, i.e. a class of
isospectral systems. Constructive methods are obtained for complex
or real systems with no symmetry constraints. It is also shown how
isospectral families of complex hermitian matrices can be formed.
The case of real symmetric matrices is more difficult. Some
partial solutions are obtained but, in this case, the theory
remains incomplete. Examples are given.",
keywords = "",
note = "To appear in Linear Algebra Appl."
}
@techreport{Mathias:2004:DGE,
author = "Roy Mathias and Chi-Kwong Li",
title = "The Definite Generalized Eigenvalue Problem:
{A} New Perturbation Theory",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 457",
pages = 51,
month = oct,
year = 2004,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep457.pdf",
abstract = "Let $(A,B)$ be a definite pair of $n \times n$ Hermitian matrices.
That is, $|x^*Ax| + |x^*Bx| \neq 0$ for all non-zero vectors
$x \in \IC^n$. It is possible to find an $n \times n$ non-singular
matrix $X$ with unit columns such that
$$
X^{*} (A + iB) X = {\rm diag}(\alpha_1 + i \beta_1, \dots, \alpha_n + i
\beta_n)
$$
where $\alpha_j$ and $\beta_j$ are real numbers. We call the pairs
$(\alpha_j, \beta_j)$ {\it normalized generalized eigenvalues} of the
definite pair $(A, B)$.
These pairs have not been studied previously. We rework the perturbation
theory for the eigenvalues and eigenvectors of the definite
generalized eigenvalue problem $\beta Ax = \alpha Bx$ in terms of
these normalized generalized eigenvalues and show that they play
a crucial rule in obtaining the best possible perturbation bounds.
In particular, in existing perturbation bounds, one can replace most
instances of the Crawford number
\[
c(A,B) = \min \{ |x^{*} (A + iB)x|: x \in \IC^n, x^{*}x = 1 \}
\]
with the larger quantity
\[
d_{\min} = \min\{ |\alpha_j + i\beta_j|: j = 1, \ldots, n \}.
\]
This results in bounds that can be stronger by an arbitrarily large
factor. We also give a new measure of the separation of the $j$th
eigenvalue from the $k$th:
\[
|(\alpha_j + i \beta_j) \sin (\arg(\alpha_j + i \beta_j)
- \arg(\alpha_k + i \beta_k))| .
\]
This asymmetric measure is entirely new, and again
results in bounds that can be arbitrarily stronger than
the existing bounds. We show that all but one of our bounds are attainable.
We also show that the Crawford number is the infimum of the distance
from a definite pencil, {\it a fortiori} diagonalizable, to a
non-diagonalizable pair."
}
@techreport{Shardlow:2004:GED,
author = "Shardlow, Tony and Yan, Yubin",
title = "Geometric Ergodicity for Dissipative Particle Dynamics",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 456",
pages = 29,
month = oct,
year = 2004,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep456.pdf",
abstract = "Dissipative particle dynamics is a system of stochastic
differential equations modelling complex fluid flows. We consider
the problem of $N$ particles evolving on the one dimensional
periodic domain of length $L$ and, if the density of particles is
large, prove geometric convergence to a unique invariant measure.
The proof uses minorization and drift arguments, but allows
elements of the drift and diffusion matrix to have compact support
where hypoellipticity arguments are not directly available."
}
@techreport{Shardlow:2004:MES,
author = "Shardlow, Tony",
title = "Modified Equations for Stochastic Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 455",
pages = 12,
month = oct,
year = 2004,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep455.pdf",
abstract = "We describe a backward error analysis for stochastic differential
equations with respect to weak convergence. Modified equations are
provided for forward and backward Euler approximations to Ito SDEs
with additive noise, and extensions to other types of equations
and approximation discussed."
}
@techreport{Bini:2004:AMP,
author = "Dario A. Bini and Nicholas J. Higham and Beatrice Meini",
title = "Algorithms for the Matrix {$p$}th Root",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 454",
pages = 26,
month = aug,
year = 2004,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep454.pdf",
abstract = "New theoretical results are presented about the principal matrix
$p$th root. In particular, we show that the $p$th root is related
to the matrix sign function and to the Wiener-Hopf factorization,
and that it can be expressed as an integral over the unit circle.
These results are used in the design and analysis of several new
algorithms for the numerical computation of the $p$th root. We
also analyze the convergence and numerical stability properties of
Newton's method for the inverse $p$th root. Preliminary
computational experiments are presented to compare the methods.",
keywords = "Matrix $p$th root, matrix sign function, Wiener-Hopf
factorization, Newton's method, Graeffe iteration, cyclic
reduction, Laurent polynomial"
}
@techreport{Powell:2004:PFP,
author = "Catherine Powell",
title = "Parameter-free $\mathbf{H(div)}$ preconditioning for mixed
finite element formulation of diffusion problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 453",
month = aug,
year = 2004,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep453.ps.gz",
abstract = "In this paper, we implement the lowest-order Raviart-Thomas scheme
for generalised diffusion problems and analyse the robustness of
so-called $H(div)$ preconditioning for the resulting saddle-point
systems. Properties of the exact version of the suggested
block-diagonal preconditioner were discussed in some previous
work, `Optimal preconditioning for Raviart-Thomas mixed
formulation of second-order elliptic problems', SIAM J. Matrix
Anal. Appl., 25, 3(2003). Here, new bounds are established for
the eigenvalue spectrum of the preconditioned system matrix when
a single V-cycle of any available multigrid scheme is used to
approximately invert the matrix corresponding to the discrete
weighted $H(div)$ operator."
}
@techreport{Higham:2004:SSM,
author = "Nicholas J. Higham",
title = "The Scaling and Squaring Method for the Matrix Exponential
Revisited",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 452",
pages = "15",
month = jul,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep452.pdf",
abstract = "The scaling and squaring method is the most widely used method for
computing the matrix exponential, not least because it is the
method implemented in MATLAB's \texttt{expm} function. The method
scales the matrix by a power of 2 to reduce the norm to order 1,
computes a Pad\'e approximant to the matrix exponential, then
repeatedly squares to undo the effect of the scaling. We give a
new backward error analysis of the method (in exact arithmetic)
that employs sharp bounds for the truncation errors and leads to
an implementation of essentially optimal efficiency. We also give
new rounding error analysis that shows the computed Pad\'e
approximant of the scaled matrix to be highly accurate. For IEEE
double precision arithmetic the best choice of degree of Pad\'e
approximant turns out to be 13, rather than the 6 or 8 used by
previous authors. Our implementation of the scaling and squaring
method always requires at least two fewer matrix multiplications
than \texttt{expm} when the matrix norm exceeds 1, which can
amount to a 37\% saving in the number of multiplications, and it
is typically more accurate owing to the fewer required squarings.
We also investigate a different scaling and squaring algorithm
proposed by Najfeld and Havel that employs a Pad\'e approximation
to the function $x \coth(x)$. This method is found to be
essentially a variation of the standard one with weaker supporting
error analysis.",
keywords = "matrix function, matrix exponential, Pad\'e approximation, matrix
polynomial evaluation, scaling and squaring method, MATLAB, expm,
backward error analysis, performance profile"
}
@techreport{Roberts:2004:SVO,
author = "Leonid E. Shaikhet and Jason A. Roberts",
title = "Stochastic {Volterra} Integro-Differential Equations:
Stability and Numerical Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 450",
pages = 38,
month = jun,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep450.pdf",
abstract = "We consider the reliability of some numerical methods in
preserving the stability properties of the linear stochastic
functional differential equation $$\dot{x}(t)=\alpha
x(t)+\beta\int^t_0x(s)ds+\sigma x(t-\tau)\dot{W}(t),$$ where
$\alpha, \beta, \sigma, \tau \geq 0$ are real constants, and
$W(t)$ is a standard Wiener process. We adopt the shorthand
notation of $\dot{x}(t)$ to represent the differential $dx(t)$
etc. Our choice of test equation is a stochastic perturbation of
the classical deterministic Brunner \& Lambert test equation for
$\sigma=0$ and so our investigation may be thought of as an
extension of their work. Sufficient conditions for the asymptotic
mean square stability of solutions to both the differential
equation and discrete analogues are derived using the general
method of Lyapunov functionals construction proposed by
Kolmanovskii \& Shaikhet which has previously been successfully
employed for deterministic and stochastic differential and
difference equations with delay. The areas of the regions of
asymptotic stability for each $\theta$ method, indicated by the
sufficient conditions for the discrete system, are shown to be
equal and we show that an upper bound can be put on the time-step
parameter for the numerical method fo which the system is
asymptotically mean-square stable. We illustrate our results by
means of numerical experiments and various stability diagrams. We
examine the extent to which the continuous system can tolerate
stochastic perturbations before losing its stability properties
and we illustrate how one may accurately choose a numerical method
to preserve the stability properties of the original problem in
the numerical solution. Our numerical experiments also indicate
that the quality of the sufficient conditions is very high."
}
@techreport{MCCM:2004:AR3,
author = "{Manchester Centre for Computational Mathematics}",
title = "Annual Report: {January--December} 2003",
type = t-NAREP,
number = "No. 449",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "25",
month = may,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep449.pdf",
}
@techreport{Baker:2004:HAL,
author = "Christopher T. H. Baker and Evelyn Buckwar",
title = "A note on {Halanay}-type stability results for the
{$\theta$}--{Maruyama} method for stochastic delay differential
equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 448",
pages = 13,
month = apr,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep448.pdf",
abstract = "Using an approach that has its origins in work of Halanay, we
consider stability in mean square of numerical solutions obtained
from the {\em $\theta$--Maruyama discretization} of a test
stochastic delay differential equation \[ dX(t) = \{f(t) -\alpha
X(t) + \beta X(t-\tau)\} {\rd}t + \{g(t) + \eta \ X(t) + \mu
X(t-\tau) \} \ {\rd}W(t) \] interpreted in the It\^o sense, where
$W(t)$ denotes a Wiener process (white noise). Our objective in
this report is limited to demonstrating that we may use
techniques advanced in a recent report by Baker and Buckwar to
obtain criteria for asymptotic and exponential stability, in mean
square, for the solutions of a recurrence \[ {\widetilde X}_{n+1}
- {\widetilde X}_n = \theta\{f_{n+1} -\A h {\widetilde X}_{n+1} +
\B h {\widetilde X}_{n+1-N}\} + (1-\theta)\{f_n -\A h{\widetilde
X}_{n} + \B h {\widetilde X}_{n-N}\}\] \[ + (g_n + \eta \sqrt{h}
\, {\widetilde X}_n + \mu \sqrt{h} \, {\widetilde X}_{n-N_{}})\
\xi_n \] where $\xi_n \in N(0,1)$ ($\xi_n$ is normally distributed
with zero mean and variance unity). This is the $\theta$-Maruyama
formula; recognizable cases arise from taking $\theta = 0$,
$\theta = \half$ or $\theta = 1$; for convenience we assume $
\theta \in [0,1] $."
}
@techreport{Hargreaves:2004:CCN,
author = "Gareth I. Hargreaves",
title = "Computing the Condition Number of Tridiagonal and
Diagonal-Plus-Semiseparable Matrices in Linear Time",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 447",
pages = 19,
month = apr,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep447.pdf",
abstract = "For an $n \times n$ tridiagonal matrix we exploit the structure of
its QR factorization to devise two new algorithms for computing the 1-norm
condition number in $O(n)$ operations. The algorithms avoid
underflow and overflow, and are simpler than existing algorithms since
tests are not required for degenerate cases. An error analysis of the
first algorithm is given, while the second algorithm is shown to be
competitive in speed with existing algorithms. We then turn our
attention to an $n \times n$ diagonal-plus-semiseparable matrix, $A$,
for which several algorithms have recently been developed to solve
$Ax=b$ in $O(n)$ operations. We again exploit the QR factorization of
the matrix to present an algorithm that computes the 1-norm condition
number in $O(n)$ operations. ",
}
@techreport{Higham:2004:FPM,
author = "Nicholas J. Higham and D. Steven Mackey and Niloufer Mackey and
Fran\c{c}oise Tisseur",
title = "Functions Preserving Matrix Groups
and Iterations for the Matrix Square Root",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "446",
pages = 29,
month = mar,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep446.pdf",
abstract = "For any matrix automorphism group $\G$ associated with a bilinear
or sesquilinear form, Mackey, Mackey, and Tisseur have recently
shown that the matrix sign decomposition factors of $A\in\G$ also
lie in $\G$; moreover, the polar factors of $A$ lie in $\G$ if the
matrix of the underlying form is unitary. Groups satisfying the
latter condition include the complex orthogonal, real and complex
symplectic, and pseudo-orthogonal groups. This work is concerned
with exploiting the structure of $\G$ when computing the polar and
matrix sign decompositions of matrices in $\G$. We give sufficient
conditions for a matrix iteration to preserve the group structure
and show that a family of globally convergent rational
Pad\'e-based iterations of Kenney and Laub satisfy these
conditions. The well-known scaled Newton iteration for computing
the unitary polar factor does not preserve group structure, but we
show that the approach of the iterates to the group is precisely
tethered to the approach to unitarity, and that this forces a
different and exploitable structure in the iterates. A similar
relation holds for the Newton iteration for the matrix sign
function. We also prove that the number of iterations needed for
convergence of the structure-preserving methods can be precisely
predicted by running an associated scalar iteration. Numerical
experiments are given to compare the cubically and quintically
converging iterations with Newton's method and to test stopping
criteria. The overall conclusion is that the structure-preserving
iterations and the scaled Newton iteration are all of practical
interest, and which iteration is to be preferred is
problem-dependent.",
keywords = "automorphism group, bilinear form, sesquilinear form, scalar
product, adjoint, Fr\'echet derivative, stability analysis,
perplectic matrix, pseudo-orthogonal matrix, generalized polar
decomposition, matrix sign function, matrix $p$th root, matrix
square root, structure preservation, matrix iteration, Newton
iteration"
}
@techreport{Lancaster:2004:OPM,
author = "Peter Lancaster and Panayiotis Psarrakos",
title = "On the Pseudospectra of Matrix Polynomials",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 445",
pages = "17",
month = feb,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep445.pdf",
abstract = "The pseudospectra of a matrix polynomial $P(\la)$ are sets of
complex numbers that are eigenvalues of matrix polynomials which
are near to $P(\la)$, i.e., their coefficients are within some
fixed magnitude of the coefficients of $P(\la)$. Pseudospectra
provide important insights into the sensitivity of eigenvalues
under perturbations, and have several applications. First,
qualitative properties concerning boundedness and connected
components of pseudospectra are obtained. Then an accurate
continuation algorithm for the numerical determination of the
boundary of pseudospectra of matrix polynomials is devised and
illustrated. This algorithm is based on a prediction-correction
scheme.",
keywords = "matrix polynomial, eigenvalue, singular value, perturbation,
$\eps$-pseudospectum, boundary, stability"
}
@techreport{Baker:2004:INP,
author = "Christopher T. H. Baker and Eugene I. Parmuzin",
title = "Identification of the initial function for delay differential
equations: Part III: Nonlinear DDEs \& computational results.",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 444",
pages = 27,
month = mar,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep444.pdf",
abstract = "In this report we consider the ``data assimilation problem'' for
nonlinear delay differential equations. This problem consists of
finding an initial function that gives rise to a solution of a
given nonlinear delay differential equation, which is a close fit
to observed data. A r\^ole for adjoint equations and fundamental
solutions in the nonlinear case is established. The
``Pseudo-Newton'' method to solve the ``data assimilation
problem'' for nonlinear DDE is presented. This is an extension of
results obtain in Nareport No.431 for linear delay differential
equations."
}
@techreport{Baker:2004:IDP,
author = "Christopher T. H. Baker and Eugene I. Parmuzin",
title = "Identification of the initial function for delay differential
equations: Part II: A discrete analogue of the data assimilation
problem \& computational results.",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 443",
pages = 29,
month = mar,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep443.pdf",
abstract = "In this report we consider a difference analogue of the ``data
assimilation problem'' for delay differential equations (DDEs)
presented in the first part (Numerical Analysis Report No. 431).
The problem consists of finding an initial function that gives rise
to a solution of a discretized DDE, which is a close fit to
observed data. A r\^ole for adjoint equations and fundamental
solutions in the discrete case is established, and related discrete
integral equations (summation equations) are obtained. The final
part of the report consists of a report of numerical experiments
that demonstrate the performance of the algorithm."
}
@techreport{Lucas:2004:LSC,
author = "Craig Lucas",
title = "{LAPACK}-Style Codes for Level 2 and 3
Pivoted {Cholesky} Factorizations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 442",
pages = "31",
month = feb,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep442.pdf",
abstract = "Fortran 77 codes exist in LAPACK for computing the Cholesky
factorization of a symmetric positive definite matrix using
Level 2 and 3 BLAS. In LINPACK there is a Level 1 BLAS
routine for computing the Cholesky factorization with complete
pivoting of a symmetric positive semi-definite matrix. We present
two new algorithms and Fortran 77 LAPACK-style codes for
computing this pivoted factorization: one using Level 2 BLAS
and one using Level 3 BLAS. We show that on modern machines the
new codes can be many times faster than the LINPACK code. Also,
with a new stopping criterion they provide more reliable rank
detection and can have a smaller normwise backward error.",
keywords = "pivoted Cholesky factorization, semi-definite matrices,
LAPACK, Level 3 BLAS."
}
@techreport{Davies:2004:SCM,
author = "Philip I. Davies",
title = "Structured Conditioning of Matrix Functions",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 441",
pages = "33",
month = jan,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep441.pdf",
abstract = "The existing theory of conditioning for matrix functions
$f(X) \colon \C^{\nbyn} \to \C^{\nbyn}$ does not cater for structure
in the matrix $X$. An extension of this theory is presented in which
when $X$ has structure, all perturbations of $X$ are required to
have the same structure. We consider two classes of structured
matrices, those comprising the Jordan algebra $\J$ and the Lie
algebra $\L$ associated with a nondegenerate bilinear or sesquilinear
form on $\R^n$ or $\C^n$. Examples of such classes are the symmetric,
skew-symmetric, Hamiltonian and skew-Hamiltonian matrices. Structured
condition numbers are defined for these two classes. Under certain
conditions on the underlying scalar product, explicit representations
are given for the structured condition numbers. Comparisons between
the unstructured and structured condition numbers are then made.
We show that when the underlying scalar product is a sesquilinear
form, there is no difference between the values of the two condition
numbers for (i) all functions of $X \in \J$, and (ii) odd and even
functions of $X \in \L$. When the underlying scalar product is a
bilinear form then equality is not guaranteed in all these cases.
Where equality is not guaranteed, bounds are obtained for the ratio
of the unstructured and structured condition numbers.",
keywords = "Matrix functions, Fr\'echet derivative, Condition numbers, Bilinear
forms, Sesquilinear forms, Structured Matrices, Jordan algebra,
Symmetric matrices, Lie algebra, Skew-symmetric matrices"
}
@techreport{Higham:2003:NSB,
author = "Nicholas J. Higham",
title = "The Numerical Stability of Barycentric {Lagrange} Interpolation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 440",
pages = "10",
month = dec,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep440.pdf",
abstract = "The Lagrange representation of the interpolating polynomial can be
rewritten in two more computationally attractive forms: a modified
Lagrange form and a barycentric form. We give an error analysis of
the evaluation of the interpolating polynomial using these two
forms. The modified Lagrange formula is shown to be backward
stable. The barycentric formula has a less favourable error
analysis, but is forward stable for any set of interpolating
points with a small Lebesgue constant. Therefore the barycentric
formula can be significantly less accurate than the modified
Lagrange formula only for a poor choice of interpolating points.
This analysis provides further weight to the argument of Berrut
and Trefethen that barycentric Lagrange interpolation should be
the polynomial interpolation method of choice.",
keywords = "polynomial interpolation, Lagrange interpolation, barycentric
formula, rounding error analysis, backward error, forward error,
Lebesgue constant"
}
@techreport{Buckwar:2003:WAS,
author = "Buckwar, Evelyn and Shardlow, Tony",
title = "Weak Approximation of Stochastic Delay Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 439",
month = dec,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep439.pdf"
}
@techreport{Shardlow:2003:NWE,
author = "Shardlow, Tony",
title = "Nucleation of Waves in Excitable Media by Noise",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 438",
month = dec,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep438.pdf"
}
@techreport{Shardlow:2003:NSS,
author = "Shardlow, Tony",
title = "Numerical Simulation of Stochastic {PDE}s for Excitable Media",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 437",
month = dec,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep437.pdf"
}
@techreport{Davies:2003:CFM,
author = "Philip I. Davies and Nicholas J. Higham",
title = "Computing {$f(A)b$} for Matrix Functions {$f$}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 436",
pages = "10",
month = nov,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep436.pdf",
abstract = "For matrix functions $f$ we investigate how to compute a
matrix-vector product $f(A)b$ without explicitly
computing $f(A)$. A general method is described that
applies quadrature to the matrix version of the Cauchy
integral theorem. Methods specific to the logarithm,
based on quadrature, and fractional matrix powers, based
on solution of an ordinary differential equation initial
value problem, are also described."
}
@techreport{Ford:2003:SGB,
author = "Judith M. Ford and Neville J. Ford and John Wheeler",
title = "Simulation of Grain Boundary Creep: Analysis of Some New Numerical
Techniques",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 435",
month = oct,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep435.pdf"
}
@techreport{Ford:2003:SLS,
author = "Judith M. Ford and Eugene E. Tyrtyshnikov",
title = "Solving Linear Systems using Wavelet Compression Combined with
{Kronecker} Product Approximation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 434",
month = oct,
pages = "11",
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep434.pdf",
note = "Submitted to special edition of Numerical Algorithms, Proceedings of
Quatrième séminaire sur l'algorithmique numérique appliquée aux
problèmes industriels, Calais, 2003"
}
@techreport{Alam:2003:OCN,
author = "Rafikul Alam",
title = "On the Construction of Nearest Defective Matrices to a Normal
Matrix",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 433",
pages = "6",
month = sep,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep433.pdf",
abstract = "Let $A$ be an $n$-by-$n$ normal matrix with $n$ distinct
eigenvalues. We describe a simple procedure to construct a
defective matrix whose distance from $A,$ among all the defective
matrices, is the shortest. Our construction requires only an
appropriate pair of eigenvalues of $A$ and their corresponding
eigenvectors. We also show that the nearest defective matrices
influence the evolution of spectral projections of $A$.",
keywords = "Defective matrix, multiple eigenvalue,
pseudospectra, eigenvector, spectral projection"
}
@techreport{Mackey:2004:SFS,
author = "D. Steven Mackey and Niloufer Mackey and Fran\c{c}oise Tisseur",
title = "Structured Factorizations in Scalar Product Spaces",
type = t-NAREP,
number = "No. 432",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "",
month = nov,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep432.pdf",
}
@techreport{Baker:2004:ICP,
author = "Christopher T. H. Baker and Eugene I. Parmuzin",
title = "Identification of the initial function for delay differential
equations: Part I: The continuous problem \& an integral equation
analysis.",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 431",
pages = 25,
month = jan,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep431.pdf",
abstract = "In this report, which is the first of three related reports, we
consider the ``data assimilation problem'' for delay differential
equations. This problem consists of finding an initial function
that gives rise to a solution which is a close fit to observed
data. A r\^ole for adjoint equations and fundamental solutions is
established, and related integral equations are obtained."
}
@techreport{Baker:2004:GTV,
author = "Christopher T. H. Baker and Eugene I. Parmuzin",
title = "A Guided Tour of Variation of Parameters Formulae for
Continuous and Discretized {DDE}s.",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 430",
pages = 21,
month = jan,
year = 2004,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep430.pdf",
abstract = "In this report we discuss variation of parameters formulae ($i$)
for systems of linear delay differential equations (DDEs), $$
\frac{\dss d y(t)}{\dss dt} -A(t) y(t) -B(t) y(t-\tau) = f(t),
\; \mbox{for}\ t\in [0,T], $$ subject to an initial condition
$y(t) =\varphi(t) \quad \mbox{for} \ t \in [-\tau,0]$, and ($ii$)
for the corresponding discretized equations that result from the
application of Euler methods. The explicit Euler method for the
above DDE, using a step $h = \tau / N$ with $T = Kh$ and $N,K \in
\Nset$, yields the equations $$ {\widetilde{y}}_{n+1} -
{\widetilde{y}}_{n} -A_n {\widetilde{y}}_n -B_n
{\widetilde{y}}_{n-N} =f_n, \quad \mbox{for}\ n \in \{0,1, \cdots,
K-1 \}, $$ subject to the initial condition $ {\widetilde{y}}_n =
\varphi_n \; \mbox{for} \ -N \leq n \leq 0, $ where $B_n = B(nh)$,
$A_n = A(nh)$ $f_n = f(nh)$ and $\varphi_n = \varphi(nh)$. Of
interest is the form of the solution to the DDE or its discretized
form, in a representation that depends upon the inhomogeneous term
$f$ or the initial function $\varphi$. Various ways to derive
variation of parameters formulae will be pursued. In the
continuous case, the fundamental solution can be obtained as a
solution of a DDE, a related integral equation, by seeking a
generalized Green's function or by considering adjoint
equations.(A number of results related to the continuous case are
presented in the literature and these are recalled in an
appendix.) We look for analogous results in the discretized case,
drawing on parallels in linear algebra."
}
@techreport{MCCM:2003:AR2,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 2002",
type = t-NAREP,
number = "No. 429",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "19",
month = jun,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep429.pdf",
}
@techreport{Tisseur:2003:EAM,
author = "Dario A. Bini and Luca Gemignani and Fran\c{c}oise Tisseur",
title = "The {Ehrlich-Aberth} Method for the Nonsymmetric
Tridiagonal Eigenvalue Problem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 428",
pages = "23",
month = jun,
year = "2003",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep428.pdf",
abstract = "An algorithm based on the Ehrlich-Aberth iteration is presented
for the computation of the zeros of $p(\l)=\det(T-\l I)$, where
$T$ is an irreducible tridiagonal matrix. The algorithm requires
the evaluation of $p(\l)/p'(\l)=-1/\trace(T-\l I)^{-1}$, which is
done here by exploiting the QR factorization of $T-\l I$ and the
semiseparable structure of $(T-\l I)^{-1}$. Two choices of the
initial approximations are considered; the most effective relies
on a divide-and-conquer strategy, and some results motivating this
strategy are given. A Fortran 95 module implementing the algorithm
is provided and numerical experiments that confirm the
effectiveness and the robustness of the approach are presented. In
particular, comparisons with the LAPACK subroutine \texttt{dhseqr}
show that our algorithm is faster for large dimensions.",
keywords = "nonsymmetric eigenvalue problem,
symmetric indefinite generalized eigenvalue problem,
tridiagonal matrix, root finder, QR decomposition,
divide and conquer."
}
@techreport{Mackey:SPA:2003,
author = "D. Steven Mackey and Niloufer Mackey and Daniel M. Dunlavy",
title = "Structure Preserving Algorithms for Perplectic Eigenproblems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 427",
pages = "30",
month = may,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep427.pdf"
}
@techreport{Higham:2003:CPD,
author = "Nicholas J. Higham and D. Steven Mackey and Niloufer Mackey and
Fran\c{c}oise Tisseur",
title = "Computing the Polar Decomposition and the Matrix Sign Decomposition
in Matrix Groups",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 426",
pages = "15",
month = apr,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep426.pdf",
abstract = "For any matrix automorphism group $\G$ associated with a
bilinear or sesquilinear form, Mackey, Mackey, and Tisseur have
recently shown that the matrix sign decomposition factors of
$A\in\G$ also lie in $\G$; moreover, the polar factors of $A$
lie in $\G$ if the matrix of the underlying form is unitary.
Groups satisfying the latter condition include the complex
orthogonal, real and complex symplectic, and pseudo-orthogonal
groups. This work is concerned with exploiting the structure of
$\G$ when computing the polar and matrix sign decompositions of
matrices in $\G$. We give sufficient conditions for a matrix
iteration to preserve the group structure and show that a family
of globally convergent rational Pad\'e-based iterations of
Kenney and Laub satisfy these conditions. The well-known scaled
Newton iteration for computing the unitary polar factor does not
preserve group structure, but we show that the approach of the
iterates to the group is precisely tethered to the approach to
unitarity, and that this forces a different and exploitable
structure in the iterates. A similar relation holds for the
Newton iteration for the matrix sign function. We also prove
that the number of iterations needed for convergence of the
structure-preserving methods can be precisely predicted by
running an associated scalar iteration. Numerical experiments
are given to compare the cubically and quintically converging
iterations with Newton's method and to test stopping criteria.
The overall conclusion is that the structure-preserving
iterations and the scaled Newton iteration are all of practical
interest, and which iteration is to be preferred is
problem-dependent.",
keywords = "automorphism group, bilinear form, sesquilinear form, adjoint,
complex orthogonal matrix, symplectic matrix, perplectic matrix,
pseudo-orthogonal matrix, polar decomposition, matrix sign
decomposition, structure preservation, matrix iteration, Newton
iteration, convergence tests"
}
@techreport{Baker:2003:MDC,
author = "Christopher T. H. Baker and Gennadii A. Bocharov and Christopher
A. H. Paul and Fathalla A. Rihan",
title = "Models with Delays for Cell Population Dynamics:
Identification, Selection and Analysis. Part I: Computational
Modelling with Functional Differential Equations:
Identification, Selection, and Sensitivity",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 425",
pages = "28",
month = feb,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep425.pdf",
abstract = "This is the first in a series of reports in which we discuss aspects
of the identification of, discrimination between, and sensitivity of,
mathematical models, and we illustrate with some examples.
Mathematical models based upon certain types of differential
equations, functional differential equations, or systems of
such equations, are often employed to represent the dynamics
of natural, in particular biological, phenomena. We present
some of the principles underlying the choice of a methodology
for the computational development of quantitatively consistent
models, using scientifically meaningful parameters, based on
observational data.
Exploiting the link between a (weighted) least-squares fit,
information theory, and maximum likelihood, we can select an
appropriate objective function which is minimized over a set
of parameters. To compare the best fit models from amongst a
hierarchy of possible models we can employ indicators that can
be regarded as taking parsimony into account. A sensitivity
analysis provides feedback on the covariances of the
parameters in relation to the best fit and on whether we need
to include all the parameters in the model. We attempt to
formulate a methodology for assessing the adequacy of
mathematical models, founded on this approach.
Much of our thinking is influenced by discussions that are
dispersed amongst the existing literature. However, we believe
that the value of our material is more than the sum of that of
its separate parts. Additionally, in a number of places we
extend or supplement or reformulate existing results. The
models that we consider generate infinite-dimensional
dynamical systems.",
keywords = " Cell growth, model selection, neutral delay
differential equation, parameter estimation, first \& second
order sensitivity analysis, nonlinear bias, objective
functions, methodologies."
}
@techreport{Higham:2003:SCS,
author = "Nicholas J. Higham and Mihail Konstantinov and Volker Mehrmann
and Petko Petkov",
title = "Sensitivity of Computational Control Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 424",
pages = "32",
month = mar,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep424.pdf",
abstract = "It is well-known that many factors contribute to the accurate and
efficient numerical solution of mathematical problems such as
those arising in computational control system design. In simple
terms these are the arithmetic of the machine on which the
calculations are carried out, sensitivity (or conditioning) of the
mathematical model to small changes of the data and the numerical
stability of the algorithms. It happens quite often that these
concepts are confused. We define these concepts and demonstrate
some of the subtleties that often lead to confusion. In particular
we demonstrate with several examples what may happen when a
problem is modularized, i.e., split into subproblems for which
computational modules are available. For three classical problems
in computational control, pole placement, linear quadratic control
and optimal $H_\infty$ control, we then discuss the conditioning
of the problems and point out sources of difficulties. We give
some ill-conditioned examples for which even numerically stable
methods fail. We also stress the need for condition and error
estimators that supplement the numerical algorithm and inform the
user about potential or actual difficulties, and we explain what
can be done to avoid these difficulties.",
keywords = "numerical stability, machine
arithmetic, pole placement, linear quadratic control,
algebraic Riccati equation, $H_\infty$ control"
}
@techreport{Mackey:2003:ODS,
author = "D. Steven Mackey and Niloufer Mackey",
title = "On the Determinant of Symplectic Matrices",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 422",
pages = "12",
month = feb,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep422.pdf",
abstract = "A collection of new and old proofs showing that the determinant of
any symplectic matrix is $+1$ is presented. Structured
factorizations of symplectic matrices play a key role in several
arguments. A constructive derivation of the symplectic analogue of
the Cartan-Dieudonn\'{e} theorem is one of the new proofs in this
essay.",
keywords = "symplectic, determinant, bilinear form, skew-symmetric,
structure-preserving factorizations, symmetries, transvections,
$\G$-reflector, Pfaffian."
}
@techreport{Tisseur:04:SFSPS,
author = "D. Steven Mackey and Niloufer Mackey and Fran\c{c}oise Tisseur",
title = "Structured Factorizations in Scalar Product Spaces",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 421",
pages = "30",
month = Nov,
year = "2004",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep421.pdf",
abstract = "
Let $A$ belong to an automorphism group, Lie algebra or Jordan
algebra of a scalar product. When $A$ is factored, to what extent
do the factors inherit structure from $A$? We answer this question
for the principal matrix square root, the matrix sign
decomposition, and the polar decomposition. For general $A$, we
give a simple derivation and characterization of a particular
generalized polar decomposition, and we relate it to other such
decompositions in the literature. Finally, we study
eigendecompositions and structured singular value decompositions,
considering in particular the structure in eigenvalues,
eigenvectors and singular values that persists across a wide range
of scalar products.
A key feature of our analysis is the identification of two
particular classes of scalar products, termed unitary and
orthosymmetric, which serve to unify assumptions for the existence
of %structured factors and structured factorizations. A variety of
different characterizations of these scalar product classes is
given.",
keywords = "automorphism group, Lie group, Lie algebra, Jordan algebra,
bilinear form, sesquilinear form, scalar product, indefinite inner
product, orthosymmetric, adjoint, factorization, symplectic,
Hamiltonian, pseudo-orthogonal, polar decomposition, matrix sign
function, matrix square root, generalized polar decomposition,
eigenvalues, eigenvectors, singular values, structure
preservation."
}
@techreport{Tisseur:2003:GRS,
author = "D. Steven Mackey and Niloufer Mackey
and Fran\c{c}oise Tisseur",
title = "$\mathbb{G}$-Reflectors in Scalar Product Spaces",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 420",
pages = "24",
month = feb,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep420.ps.gz",
abstract = " We characterize the analogues of Householder reflectors in matrix
groups associated with scalar products. Examples of such groups
include the symplectic and pseudo-unitary groups. We also
precisely delimit the mapping capabilities of these Householder
analogues: given a matrix group $\G$ and vectors $x, y$, we give
necessary and sufficient conditions for the existence of a
Householder-like analogue $G \in \G$ such that $Gx = y$. When $G$
exists, we show how it can be constructed from $x$ and $y$.",
keywords = "scalar product, bilinear, sesquilinear, isotropic, Householder
reflection, hyperbolic transformation, symmetries, transvections,
symplectic, pseudo-unitary, structure-preserving."
}
@techreport{Tisseur:2003:STS,
author = "D. Steven Mackey and Niloufer Mackey and Fran\c{c}oise Tisseur",
title = "Structured Tools for Structured Matrices",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 419",
pages = "36",
month = feb,
year = "2003",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep419.pdf",
abstract = "We present an extensive and unified collection of
structure-preserving transformations, organized for easy
reference. The structures we work with arise in the context of a
non-degenerate bilinear or sesquilinear form on $\R^n$ or $\C^n$.
We construct a variety of transformations belonging to the
automorphism groups of these forms, that imitate the action of
Givens rotations, Householder reflectors, and Gauss
transformations. We also describe transformations for performing
structured scaling actions. The matrix groups considered in this
paper are the complex orthogonal, real, complex and conjugate
symplectic, real perplectic, real and complex pseudo-orthogonal,
and pseudo-unitary groups. In addition to deriving new
transformations, this paper collects and unifies existing
structure-preserving tools.",
keywords = "structured matrices, matrix groups, Givens rotations, Householder
reflections, complex orthogonal, symplectic, complex symplectic,
conjugate symplectic, real perplectic, pseudo-orthogonal, complex
pseudo-orthogonal, pseudo-unitary, scalar product, bilinear form,
sesquilinear form, automorphism groups, Jordan algebra, Lie
algebra."
}
@techreport{Ford:2003:CKP,
author = "Judith M. Ford and Eugene E. Tyrtyshnikov",
title = "Combining {Kronecker} Product Approximation with Discrete Wavelet
Transforms to Solve Dense, Function-Related Linear Systems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 418",
month = jan,
year = 2003,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep418.pdf"
}
@techreport{Baker:2003:NDE,
author = "Christopher T. H. Baker and Christopher A. H. Paul",
title = "Piecewise Continuous Solutions of Neutral Delay
Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 417",
pages = 35,
month = Dec,
year = 2003,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep417.pdf",
abstract = "Examples of neutral delay differential equations (NDDEs) are \[
\frac{d}{dt} u(t) = F\big(t,u(t),u(t-\tau),\frac{d}{dt}
u(t-\tau)\big) \quad (t \ge t_0), \] for $\tau > 0$, and (a form
frequently called ``Hale's form'') \[ \frac{d}{dt}
\{u(t)-g\big(t,u(t),u(t-\tau)\big)\} = f\big(t,u(t),u(t-\tau)\big)
\quad (t \ge t_0) \] which is an NDDE when $g$ does not vanish
identically. A particular solution of such an equation is defined
by initial data on $[-\tau,0]$, and we observe in this report
that, when the problem is suitably interpreted, the solutions of
an NDDE need not be continuous. This fact, largely overlooked in
the numerical analysis literature (many of the texts on the
analysis of NDDEs admit a function as a solution only if it is
continuous), presents some difficulties when considering numerical
methods for approximating solutions. Our discussion of NDDEs
points to the need to be precise in the definition of the term
``solution'', and to consider questions of \emph{existence},
\emph{uniqueness} and \emph{smoothness} of any solutions of NDDEs.
Such questions are a precursor to addressing the problem of
constructing numerical methods. Numerical codes for solving
differential equations are generally based on the assumption that
a solution is continuous, and our discussion will indicate
measures that may be taken if one seeks a discontinuous solution
of an NDDE. First we show that the difficulties can sometimes be
alleviated by \emph{perturbing the initial function} to yield a
continuously differentiable solution. Alternatively,
\emph{tracking discontinuities} and converting the problem to a
\emph{delay differential algebraic equation} (DDAE) -- followed
either by direct solution of the DDAE or by treatment after
regularizing the DDAE to a singularly perturbed problem -- are
discussed in the Appendices. The investigation of the simple NDDE
that opens our discussion is followed by a number of results for
general NDDEs."
}
@techreport{Hargreaves:2002:IAM,
author = "Gareth I. Hargreaves",
title = "Interval Analysis in {MATLAB}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 416",
pages = 49,
month = dec,
year = 2002,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep416.pdf",
abstract = "The introduction of fast and efficient software for interval
arithmetic, such as the MATLAB toolbox INTLAB, has resulted in the
increased popularity of the use of interval analysis. We give an
introduction to interval arithmetic and explain how it is
implemented in the toolbox INTLAB. A tutorial is provided for
those who wish to learn how to use INTLAB. We then focus on the
interval versions of some important problems in numerical
analysis. A variety of techniques for solving interval linear
systems of equations are discussed, and these are then tested to
compare timings and accuracy. We consider univariate and
multivariate interval nonlinear systems and describe algorithms
that enclose all the roots. Finally, we give an application of
interval analysis. Interval arithmetic is used to take account of
rounding errors in the computation of Viswanath's constant, the
rate at which a random Fibonacci sequence increases.",
keywords = "interval analysis, interval arithmetic, INTLAB, MATLAB, tutorial,
interval linear equations, interval nonlinear equations,
Viswanath's constant"
}
@techreport{Powell:2002:BBP,
author = "Catherine Powell and David Silvester",
title = "Black-Box Preconditioning for Mixed Formulation of Self-Adjoint
Elliptic {PDE}s",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 415",
month = nov,
year = 2002,
note = "Submitted to the conference proceedings of CISC 2002 for publication
in Springer Lecture Notes in Computer Science and Engineering",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep415.ps.gz",
abstract = "Mixed finite element approximation of self-adjoint elliptic PDEs
leads to symmetric indefinite linear systems of equations.
Preconditioning strategies commonly focus on reduced symmetric
positive definite systems and require nested iteration. This
defficiency is avoided if preconditioned \textsc{minres} is
applied to the full indefinite system. We outline such a
preconditioning strategy, the key building block for which is a
fast solver for a scalar diffusion operator based on black-box
algebraic multigrid. Numerical results are presented for the
Stokes equations arising in incompressible flow modelling and a
variable diffusion equation that arises in modelling potential
flow. We prove that the eigenvalues of the preconditioned matrices
are contained in intervals that are bounded independently of the
discretisation parameter and the PDE coefficients."
}
@techreport{Agyingi:2003:VOP,
author = "Ephraim Agyingi and Christopher T. H. Baker",
title = "Variation of Parameters Formulae for {Volterra} Integral Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 414",
pages = 20,
month = Nov,
year = 2003,
url = "http://www.maths.manchester.ac.uk/~higham/narep/narep414.pdf",
abstract = "In this report, the authors obtain variation of parameters
formulae for nonlinear Volterra integral equations and
integro-differential equations. These are related to a variation
of parameters formula for ordinary differential equations that is
due to V.M.~Alekseev. The authors' results are obtained through
the use of an embedding technique. Some doubts have been cast on
previous results in the literature. Amongst other things, the
authors show that a result on which much of the numerical
analysis for Volterra equations has been founded in the past can
be obtained by a new approach. "
}
@techreport{Bojanczyk:2002:CIL,
author = "Adam Bojanczyk and Nicholas J. Higham and Harikrishna Patel",
title = "The Constrained Indefinite Least Squares Problem: {Theory} and
Algorithms",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 413",
pages = "11",
month = oct,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep413.pdf",
abstract = "We present theory and algorithms for the equality constrained
indefinite least squares problem, which requires minimization of
an indefinite quadratic form subject to a linear equality
constraint. A generalized hyperbolic QR factorization is
introduced and used in the derivation of perturbation bounds and
to construct a numerical method. An alternative method is obtained
by employing a generalized QR factorization in combination with a
Cholesky factorization. Rounding error analysis is given to show
that both methods have satisfactory numerical stability properties
and numerical experiments are given for illustration. This work
builds on recent work on the unconstrained indefinite least
squares problem by Chandrasekaran, Gu and Sayed and by the
present authors.",
keywords = "equality constrained indefinite least squares problem,
$J$-orthogonal matrix, hyperbolic rotation, hyperbolic QR
factorization, generalized hyperbolic QR factorization, rounding
error analysis, forward stability, perturbation theory, Cholesky
factorization"
}
@techreport{Ford:2002:IDP,
author = "Judith M. Ford",
title = "An Improved {DWT}-Based Preconditioner for Dense Matrix Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 412",
month = sep,
year = 2002,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep412.ps.gz",
abstract = "We present a new preconditioning method for a class of dense
matrices, based on sparse approximation in a discrete wavelet
basis. We first prove theoretical results that enable us to reduce
the cost of an existing wavelet-based preconditioner and then
incorporate those ideas into the design of our new preconditioner.
We demonstrate the effectiveness of our methods with numerical
examples drawn from physical problems including the
two-dimensional Helmholtz equation for which our preconditioner
gives savings of about 40\% compared with existing discrete
wavelet preconditioners and of up to 87\% compared with direct
solution."
}
@techreport{Higham:2002:CMC,
author = "Nicholas J. Higham and Matthew I. Smith",
title = "Computing the Matrix Cosine",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 411",
pages = 15,
month = sep,
year = 2002,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep411.pdf",
abstract = "An algorithm is developed for computing the matrix cosine,
building on a proposal of Serbin and Blalock. The algorithm scales
the matrix by a power of 2 to make the $\infty$-norm less than or
equal to 1, evaluates a Pad\'e approximant, and then uses the
double angle formula $\cos(2A) = 2\cos(A)^2-I$ to recover the
cosine of the original matrix. In addition, argument reduction and
balancing is used initially to decrease the norm. We give
truncation and rounding error analyses to show that an [8,8]
Pad\'e approximant produces the cosine of the scaled matrix
correct to machine accuracy in IEEE double precision arithmetic,
and we show that this Pad\'e approximant can be more efficiently
evaluated than a corresponding Taylor series approximation. We
also provide error analysis to bound the propagation of errors in
the double angle recurrence. Numerical experiments show that our
algorithm is competitive in accuracy with the Schur--Parlett
method of Davies and Higham, which is designed for general matrix
functions, and it is substantially less expensive than that method
for matrices of $\infty$-norm of order 1. The dominant
computational kernels in the algorithm are matrix multiplication
and solution of a linear system with multiple right-hand sides, so
the algorithm is well suited to modern computer architectures.",
keywords = "matrix function, matrix cosine, matrix exponential, Taylor series,
Pad\'e approximation, double angle formula, rounding error
analysis, Schur--Parlett method, MATLAB"
}
@techreport{Higham:2002:MCT,
author = "Nicholas J. Higham",
title = "The {Matrix Computation Toolbox} for {MATLAB} (Version 1.0)",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 410",
pages = "19",
month = aug,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep410.pdf",
abstract = "The Matrix Computation Toolbox is a collection of MATLAB M-files
containing functions for constructing test matrices,
computing matrix factorizations, visualizing matrices,
and carrying out direct search optimization.",
keywords = "test matrix, MATLAB, matrix factorizations, Gaussian elimination,
complete pivoting, rook pivoting, symmetric indefinite matrix,
Gram-Schmidt orthogonalization, polar decomposition, matrix sign
function, complete orthogonal decomposition,
generalized QR factorization, Gauss-Jordan elimination,
Gershgorin disks, pseudospectrum, field of values, visualization,
direct search optimization, Strassen's method, vec-permutation
matrix, Vandermonde matrix"
}
@techreport{Tisseur:2002:TDRSIP,
author = "Fran\c{c}oise Tisseur",
title = "Tridiagonal-Diagonal Reduction of Symmetric Indefinite Pairs",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 409",
pages = "20",
month = sep,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep409.pdf",
abstract = "We consider the reduction of a symmetric indefinite
matrix pair $(A,B)$, with $B$ nonsingular, to
tridiagonal-diagonal form by congruence transformations.
This is an important reduction in solving polynomial
eigenvalue problems with symmetric coefficient matrices
and in frequency response computations. First the pair
is reduced to symmetric-diagonal form. Then we describe
three methods reducing the symmetric-diagonal pair to
tridiagonal-diagonal form. Two of them employ more
stable versions of Brebner and Grad's pseudosymmetric
Givens and pseudosymmetric Householder reductions, while
the third is new and based on a combination of
Householder reflectors and hyperbolic rotations. We
prove an optimality condition for the transformations
used in the third reduction. We present numerical
experiments that compare the different approaches and
show improvements over Brebner and Grad's reductions.",
keywords = "symmetric indefinite generalized eigenvalue problem,
tridiagonalization, hyperbolic rotation, unified
rotation, hyperbolic Householder reflector."
}
@techreport{Higham:2002:JOM,
author = "Nicholas J. Higham",
title = "{$J$}-Orthogonal Matrices: {Properties} and Generation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 408",
pages = "15",
month = sep,
year = 2002,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep408.pdf",
abstract = "A real, square matrix $Q$ is $J$-orthogonal if $Q^TJQ = J$, where
the signature matrix $J = \diag(\pm 1)$. $J$-orthogonal matrices
arise in the analysis and numerical solution of various matrix
problems involving indefinite inner products, including, in
particular, the downdating of Cholesky factorizations. We present
techniques and tools useful in the analysis, application and
construction of these matrices, giving a self-contained treatment
that provides new insights. First, we define and explore the
properties of the exchange operator, which maps $J$-orthogonal
matrices to orthogonal matrices and vice-versa. Then we show how
the exchange operator can be used to obtain a hyperbolic CS
decomposition of a $J$-orthogonal matrix directly from the usual
CS decomposition of an orthogonal matrix. We employ the
decomposition to derive an algorithm for constructing random
$J$-orthogonal matrices with specified norm and condition number.
We also give a short proof of the fact that $J$-orthogonal
matrices are optimally scaled under two-sided diagonal scalings.
We introduce the indefinite polar decomposition and investigate
two iterations for computing the $J$-orthogonal polar factor: a
Newton iteration involving only matrix inversion and a Schulz
iteration involving only matrix multiplication. We show that these
iterations can be used to $J$-orthogonalize a matrix that is not
too far from being $J$-orthogonal.",
keywords = "$J$-orthogonal matrix, exchange operator, gyration operator,
sweep operator, principal pivot transform, hyperbolic CS
decomposition, two-sided scaling, indefinite least squares
problem, hyperbolic QR factorization, Newton's method, Schulz
iteration"
}
@techreport{Tisseur:2002:STTSM,
author = "Seamus. D. Garvey and Fran\c{c}oise Tisseur
and Mike I. Friswell and John E. T. Penny and
Uwe Prells",
title = "Simultaneous Tridiagonalization of Two Symmetric Matrices",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 407",
pages = "18",
month = aug,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep407.pdf",
abstract = "We show how to simultaneously reduce a pair of symmetric
matrices to tridiagonal form by congruence
transformations. No assumptions are made on the
nonsingularity or definiteness of the two matrices. The
reduction follows a strategy similar to the one used for
the tridiagonalization of a single symmetric matrix via
Householder reflectors. Two algorithms are proposed,
one using non-orthogonal rank-one modifications of the
identity matrix and the other, more costly but more
stable, using a combination of Householder reflectors
and non-orthogonal rank-one modifications of the
identity matrix with minimal condition numbers. Each of
these tridiagonalization processes requires $O(n^3)$
arithmetic operations and respects the symmetry of the
problem. We illustrate and compare the two algorithms
with some numerical experiments.",
keywords = "Symmetric matrices,
generalized eigenvalue problem,
tridiagonalization,
symmetric quadratic eigenvalue problem."
}
@techreport{Mihajlovic:2002:EPS,
author = "Milan Mihajlovic and David Silvester",
title = "Efficient Parallel Solvers for the Biharmonic Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 406",
month = jul,
year = 2002,
note = "Submitted to Parallel Computing",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep406.ps.gz",
abstract = "We examine the convergence characteristics and performance of
parallelised Krylov subspace solvers applied to the linear algebraic
systems that arise from low-order mixed finite element approximation of
the biharmonic problem. Our strategy results in preconditioned systems
that have nearly optimal eigenvalue distribution, which consists of a
tightly clustered set together with a small number of outliers. We
implement the preconditioner operator in a ``black-box'' fashion using
publicly available parallelised sparse direct solvers and multigrid
solvers for the discrete Dirichlet Laplacian. We present convergence and
timing results that demonstrate the efficiency and scalability of our
strategy when implemented on contemporary computer architectures."
}
@techreport{Davies:2002:USV,
author = "Philip I. Davies and Matthew I. Smith",
title = "Updating the Singular Value Decomposition",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 405",
pages = "30",
month = aug,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep405.ps.gz",
abstract = "The spectral decomposition of a symmetric matrix $A$
with small off-diagonal and distinct diagonal elements
can be approximated using a direct scheme of R. Davies and Modi
[\emph{Linear Algebra and Appl.,} 77:61-74, 1986].
In this paper a generalization of this method
for computing the singular value decomposition of
close-to-diagonal $A\in\R^{m \times n}$ is presented.
When $A$ has repeated or ``close'' singular values it is
possible to apply the direct method to split the problem
in two with one part containing the well-separated singular
values and one requiring the computation of the ``close''
singular values."
}
@techreport{Davies:2002:SPA,
author = "Philip I. Davies and Nicholas J. Higham",
title = "A {Schur--Parlett} Algorithm for Computing Matrix Functions",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 404",
pages = "22",
month = jul,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep404.pdf",
abstract = "An algorithm for computing matrix functions is presented. It
employs a Schur decomposition with reordering and blocking
followed by the block form of a recurrence of Parlett, with
functions of the nontrivial diagonal blocks evaluated via a Taylor
series. A parameter is used to balance the conflicting
requirements of producing small diagonal blocks and keeping the
separations of the blocks large. The algorithm is intended
primarily for functions having a Taylor series with an infinite
radius of convergence, but it can be adapted for certain other
functions, such as the logarithm. Novel features introduced here
include a convergence test that avoids premature termination of
the Taylor series evaluation and an algorithm for reordering and
blocking the Schur form. Numerical experiments show that the
algorithm is competitive with existing special-purpose algorithms
for the matrix exponential, logarithm, and cosine. Nevertheless,
the algorithm can be numerically unstable with the default choice
of its blocking parameter (or in certain cases for all choices),
and we explain why determining the optimal parameter appears to be
a very difficult problem. A MATLAB implementation is available
that is much more reliable than the existing MATLAB function
\texttt{funm}."
}
@techreport{Song:PTD:2002,
author = "Y. Song and C. T. H. Baker",
title = "Perturbation Theory for Discrete {Volterra} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 403",
pages = "18",
month = jun,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep403.ps.gz",
abstract = "Fixed point theory is used to investigate nonlinear discrete
Volterra equations that are perturbed versions of linear equations.
Sufficient conditions are established ($i$) to ensure that stability
(in a sense that is defined) of the solutions of the linear equation
implies a corresponding stability of the zero solution of the
nonlinear equation and ($ii$) to ensure the existence of
asymptotically periodic solutions",
keywords = "Fixed point theorem, perturbation, discrete Volterra equations,
periodic, asymptotically periodic."
}
@techreport{Song:SDV:2002,
author = "Y. Song and C. T. H. Baker",
title = "Stability in Discrete {Volterra} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 402",
pages = "19",
month = jun,
year = "2002",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep402.ps.gz",
abstract = "A linearized stability theory for discrete Volterra
equations of the type \[
x(n)=f(n)+\sum^n_{j=0}K\big(n, j, x(n)\big), \mbox{($n\ge 0$)}
\] is developed: Various types of stability are defined and
studied by using the fundamental and resolvent matrices that
are associated with linear equations of the form \[ x(n)=f(n)
+ \sum^n_{j=0}B(n, j)x(j), \mbox{($n\ge 0$)}, \] and several
necessary and sufficient conditions for stability are obtained
for solutions of this linear equation. In conclusion, a result
concerning the stability of a solution of the nonlinear
equation is provided under certain assumptions.
The results parallel corresponding results for classical
Volterra integral equations of the second kind",
keywords = "Stability, asymptotic stability, discrete Volterra equations,
resolvent matrix, fundamental matrix."
}
@techreport{MCCM:2002:AR1,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 2001",
type = t-NAREP,
number = "No. 401",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "21",
month = may,
year = "2002",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep401.pdf",
}
@techreport{Baker:2002:PSD,
author = "C. T. H. Baker and Y. Song",
title = "Periodic Solutions of Discrete {Volterra} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 400",
pages = "21",
month = may,
year = "2002",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep400.ps.gz",
abstract =
"In this paper we investigate periodic solutions of linear
and nonlinear discrete Volterra equations of convolution,
or non-convolution type with unbounded memory. For linear
discrete Volterra equations, we establish Fredholm's
alternative theorem for convolution equations and we show
that, under certain conditions, only one particular bounded
initial function can generate a unique periodic solution
and this unique periodic solution attracts all other
solutions with bounded initial function. In other words,
we show that all solutions of linear discrete Volterra
equations are asymptotically periodic under certain conditions.",
keywords =
"Periodic, asymptotically periodic, discrete Volterra
equations, resolvent matrices, Fredholm's alternative."
}
@techreport{Powell:2002:OPR,
author = "Catherine Powell and David Silvester",
title = "Optimal Preconditioning for {Raviart-Thomas} Mixed Formulation
of Second-Order Elliptic Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 399",
month = mar,
year = 2002,
note = "Submitted to the SIAM Journal on Matrix Analysis and Applications",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep399.ps.gz",
abstract = "We evaluate two preconditioning strategies for the indefinite
linear system obtained from Raviart-Thomas mixed finite element
formulation of a second-order elliptic problem with variable
coefficients. In contrast to other approaches, our emphasis is on
linear algebra; we establish the optimality of the
preconditioning using basic properties of the finite element
matrices. The underlying saddle-point problem is well-posed in
two function spaces, $H(div)\times L^{2}$ and $L^{2} \times
H^{1}$, leading to the possibility of two distinct types of
preconditioner. For homogeneous Dirichlet boundary conditions,
the discrete problems are identical. This motivates the use of
Raviart-Thomas approximation in both frameworks yielding a
non-conforming method in the second case. We construct two
block-diagonal preconditioners and establish a new uniform
eigenvalue bound. Trials of preconditioned MINRES illustrate that
both preconditioners are robust with respect to the mesh
parameter, and with respect to jumps and anisotropies in the
diffusion coefficients. "
}
@techreport{Baker:2002:DVO,
author = "C. T. H. Baker and Y. Song",
title = "Discrete Volterra Operators, Fixed Point Theorems \& their
Application",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 398",
pages = "23",
month = mar,
year = "2002",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep398.ps.gz",
abstract =
"The existence of solutions of nonlinear discrete Volterra
equations is established.
We define discrete Volterra operators on normed spaces of
infinite sequences of finite-dimensional vectors. and present
some of their basic properties (continuity, boundedness, and
representation). The treatment relies upon the use of
coordinate functions, and the existence results are obtained
using fixed point theorems for discrete Volterra operators on
infinite-dimensional spaces based on fixed point theorems of
Schauder, Rothe, and Altman, and Banach's contraction mapping
theorem, for finite-dimensional spaces.",
keywords =
"Fixed point theorem, discrete Volterra equations, discrete
Volterra operators."
}
@techreport{Bojanczyk:2002:SIL,
author = "Adam Bojanczyk and Nicholas J. Higham and Harikrishna Patel",
title = "Solving the Indefinite Least Squares Problem by Hyperbolic {QR}
Factorization",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 397",
pages = "19",
month = jan,
year = "2002",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep397.pdf",
abstract = "The indefinite least squares (ILS) problem is to minimize a
certain type of indefinite quadratic form. We develop
perturbation theory for the problem and identify a condition
number. We describe and analyze a method for solving the ILS
problem based on hyperbolic QR factorization. This method is
faster than one recently proposed by Chandrasekaran, Gu and Sayed
that employs both QR and Cholesky factorizations. We give a
rounding error analysis of the new method and use the
perturbation theory to show that under a reasonable assumption
the method is forward stable. Our analysis is quite general and
sheds some light on the stability properties of hyperbolic
transformations. Our numerical experiments suggest that the new
method is in practice just as accurate as the method of
Chandrasekaran, Gu and Sayed.",
keywords = "indefinite least squares problem, downdating, hyperbolic
rotation, hyperbolic QR factorization, rounding error analysis,
forward stability, perturbation theory, condition number"
}
@techreport{Baker:2002:BSD,
author = "C. T. H. Baker and J. M. Ford and N. J. Ford",
title = "Bifurcations in Stochastic Delay Differential Equations---{I}:
{Numerical} Investigation ",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 396",
pages = "18",
month = mar,
year = "2002",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep396.ps.gz",
abstract =
"We consider {\em stochastic delay differential equations} of
the form \[ dY(t)=F(t,Y(t),Y(t-\tau))dt + G(t,Y(t),Y(t-\tau))
dW(t) \quad (t \geq t_0), \] interpreted in the It\^{o} sense
where $W(t)$ is a standard {\em Wiener process}, with $ Y(t) =
\Phi(t)$ for $t \in [-\tau,0]$ (where $\tau > 0$ is the
constant lag, or `time-lag'). We are interested in {\em
bifurcations} (that is, changes in the qualitative behaviour
of the solutions to these equations) and we draw on insights
from the deterministic counterpart \[
y'(t)=f(t,y(t),y(t-\tau)), \quad \mbox{ for $t \geq t_0$}, \]
with $y(t) = \phi(t)$ for $ t \in [t_0-\tau,t_0]$ and constant
lag $\tau$. For these deterministic problems we can exploit
known theory and numerical results that enable us to predict
where changes occur in the behaviour of the solutions (exact
and approximate) of the equation.
For those unfamiliar with the area, rather diverse components
of the mathematical background are necessary to understand the
questions of interest. In this introductory report we first
review some deterministic results and some basic elements of
the stochastic analysis that ($i$) suggests lines of
investigation for the stochastic case and ($ii$) are expected
to facilitate the theoretical investigation of the stochastic
problem. We then give numerical evidence that the presence of
noise, corresponding to the change from the deterministic to
the stochastic form, may change the qualitative behaviour of
the solutions in an interesting way.",
keywords =
"Bifurcation and stability, stochastic and deterministic delay
equations with fixed lag, Euler-type methods with fixed step,
numerical experiments."
}
@techreport{Tisseur:2001:CBE,
author = "Fran\c{c}oise Tisseur",
title = "A Chart of Backward Errors and Condition Numbers for
Singly and Doubly Structured Eigenvalue Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 395",
pages = "23",
month = dec,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep395.ps.gz",
abstract = "We present a chart of structured backward errors for
approximate eigenpairs of singly and doubly structured
eigenvalue problems. We aim to give, wherever possible,
formulae that are inexpensive to compute so that they
can be used routinely in practice. We identify a number
of problems for which the structured backward error is
within a factor $\sqrt{2}$ of the unstructured backward
error. This paper collects, unifies and extends existing
work on this subject.",
}
@techreport{Tisseur:2001:IGT,
author = "Jean-Pierre Dedieu and Myong-Hi Kim and Michael Shub
and Fran\c{c}oise Tisseur",
title = "Implicit Gamma Theorems {(I)}: {Pseudoroots} and Pseudospectra",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 394",
pages = "25",
month = Nov,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep394.ps.gz",
abstract = "Let $g: \E \rightarrow \F $ be an analytic function
between two Hilbert spaces $\E$ and $\F$. We study the
set $g(B(x,\eps ))\subset \F$, the image under $g$ of
the closed ball about $x\in\E$ with radius $\eps$. When
$g(x)$ expresses the solution of an equation depending
on $x$ then the elements of $g(B(x,\eps ))$ are
$\eps$-pseudosolutions . Our aim is to investigate the
size of the set $g(B(x,\eps ))$. We derive upper and
lower bounds of the following form $$ g(x) + Dg(x)\left
( B(0, c_1 \eps ) \right ) \subseteq g(B(x,\eps ))
\subseteq g(x) + Dg(x)\left ( B(0, c_2 \eps ) \right ),
$$ where $Dg(x)$ denotes the derivative of $g$ at
$x$. We consider both the case where $g$ is given
explicitly and the case where $g$ is given
implicitly. We apply our results to the implicit
function associated with the evaluation map, namely the
solution map, and to the polynomial eigenvalue
problem. Our results are stated in terms of an invariant
$\gamma$ which has been extensively used by various
authors in the study of Newton's method. The main tool
used here is an implicit $\gamma$ theorem, which
estimates the $\gamma$ of an implicit function in terms
of the $\gamma$ of the function defining it.",
}
@techreport{Cheng:2001:ILBA,
author = "Sheung Hun Cheng and Nicholas J. Higham",
title = "Implementation for {LAPACK} of a Block Algorithm for Matrix 1-Norm
Estimation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 393",
pages = "19",
month = aug,
year = "2001",
note = "LAPACK Working Note 152",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep393.ps.gz",
abstract = "We describe double precision and complex*16 Fortran~77
implementations, in LAPACK style, of a block matrix 1-norm
estimator of Higham and Tisseur. This estimator differs from that
underlying the existing LAPACK code, \texttt{xLACON}, in that it
iterates with a matrix with $t$ columns, where $t\ge 1$ is a
parameter, rather than with a vector, and so the basic
computational kernel is level 3 BLAS operations. Our experiments
with random matrices on a Sun SPARCStation Ultra-5 show that with
$t=2$ or $4$ the new code offers better estimates than
\texttt{xLACON} with a similar execution time. Moreover, with
$t>2$, estimates exact over $95\%$ and $75\%$ of the time are
achieved for the real and complex version respectively, with
execution time growing much slower than $t$. We recommend this
new code be included as an auxiliary routine in LAPACK to
complement the existing LAPACK routine \texttt{xLACON}, upon
which the various drivers should still be based for compatibility
reasons."
}
@techreport{Smith:2001:ASAC,
author = "Matthew I. Smith",
title = "A {Schur} Algorithm for Computing Matrix $p$th Roots",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 392",
month = jul,
year = "2001",
pages = "18",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep392.ps.gz",
abstract = "Any nonsingular matrix has $p$th roots,
and they can be classified into two groups, those that are
functions of $A$ and those that are not. Matrix $p$th roots can be
computed by a specialized version of Newton's method, but we show
that this iteration has poor convergence and stability properties
in general. We present a Schur algorithm for computing a matrix
$p$th root that generalizes methods of Bj{\"{o}}rck and Hammarling
[\emph{Linear Algebra and Appl.,} 52/53:127-140, 1983] and Higham
[\emph{Linear Algebra and Appl.,} 88/89:405-430, 1987] for the
square root. Our algorithm forms a Schur decomposition of $A$ and
computes a $p$th root of the (quasi)triangular factor by a
recursion. The backward error associated with our Schur method is
examined, and we find that the method has excellent numerical
stability.",
keywords = "matrix $p$th root, Schur algorithm, Newton's method,
commutativity, stability, real arithmetic, rounding error
analysis"
}
@techreport{MCCM:2001:AR0,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 2000",
type = t-NAREP,
number = "No. 391",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "23",
month = mar,
year = "2001",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep391.pdf",
}
@techreport{FordJ:2001:PFWT,
author = "J. M. Ford and K. Chen and N. J. Ford",
title = "Parallel Implementation of Fast Wavelet Transforms",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 389",
pages = "15",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep389.ps.gz",
abstract = "We look at the use of parallel techniques for fast wavelet transforms, focusing
particularly on how to make best use of any given number of available processors.
Efficient algorithms for parallel FWT have been established in the case where the
lengths of the vectors to be transformed and the number of processors are both powers of 2.
We show that a na{\"}{\i}ve extension to arbitrary vector length and number of processors
may give poor performance. We present new algorithms for the distribution of matrix
elements between processors that overcome these difficulties. We have implemented our
algorithms on a multi-processor Sun Sparc machine, and we present analytical and
experimental results demonstrating significant improvements in performance of FWT
calculation.",
keywords = "parallel, FWT, implementation, MPI"
}
@techreport{FordJ:2001:SPFW,
author = "J. M. Ford and K. Chen and N. J. Ford",
title = "Small-Scale Parallel Implementation of Fast Wavelet Transforms",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 388",
pages = "7",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep388.ps.gz",
abstract = "We look at the use of parallel techniques for Fast Wavelet Transforms, focusing
particularly on how to make best use of a very limited (and, perhaps, variable)
number of available processors. Efficient algorithms for parallel FWT have been
established in the case where the lengths of the vectors to be transformed and the
number of processors are both powers of 2. We show that a na{\"}{\i}ve extension to
arbitrary vector length and number of processors may give poor performance or, in
some cases, be impossible. We present new algorithms for the distribution of matrix
elements between processors that overcome these difficulties. We have implemented our
algorithms on a local area network of inexpensive PCs using MPI, and present
experimental results demonstrating significant improvements in performance of FWT
calculation.",
keywords = "PC, parallel, FWT, MPI"
}
@techreport{Ford:2001:NAFDE,
author = "N. J. Ford and A. C. Simpson",
title = "Numerical and Analytical Treatment of Differential Equations of
Fractional Order",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 387",
pages = "7",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep387.ps.gz",
abstract = "We begin with a brief survey of differential equations of fractional order and
their applications. We focus on key issues in the exact and numerical solution
of the equations. We summarise our recent results: We describe the importance
of the appropriate choice of initial conditions. We show how the behaviour of
solutions changes with small changes in the fractional order. We discuss the use
of {\em systems} of fractional order equations as a tool to solve equations of
higher order. We give results that show how the computational effort required to
solve an equation of fractional order can be reduced, either through careful
application of the {\em short memory} principle or through the use of schemes
of varying step-length.",
keywords = "short memory, systems, fractional order"
}
@techreport{Ford:2001:AFDG1,
author = "N. J. Ford and A. C. Simpson",
title = "The Approximate Solution of Fractional Differential Equations of Order
Greater Than 1",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 386",
pages = "6",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep386.ps.gz",
abstract = "Differential equations of fractional order arise, for example, in the generalised
viscoelastic constitutive equations, the generalised Basset force, and
in fractional Brownian motion. Numerical methods for solution of
equations of fixed order $\alpha$ are well established, particularly
for $0<\alpha<1$, however many of the analytical results depend on the
assumption that the equation has a particularly simple form. Recent
work (by Diethelm and Ford and others) has considered approaches for
solving more complicated and multi-term equations. In this paper we
present an alternative approach to numerical solution of order greater
than one and we conclude the paper by comparing the numerical results
for our proposed method with known numerical and analytical solutions
for prototype nonlinear problems.",
keywords = "systems, fractional order"
}
@techreport{Ford:2001:SVA,
author = "N. J. Ford and A. C. Simpson",
title = "The Numerical Solution of Fractional Differential Equations: Speed
Versus Accuracy",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 385",
pages = "12",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep385.ps.gz",
abstract = "This paper is concerned with the development of efficient algorithms for the
approximate solution of fractional differential equations of the
form $D^\alpha y(t)=f(t,y(t)), \mathbb{R}^+-\mathbb{N}$. We
briefly review standard numerical techniques for the solution of
($\dagger$) and we consider how the computational cost may be
reduced by taking into account the structure of the calculations
to be undertaken. We analyse the {\it fixed memory principle} and
present an alternative {\it nested mesh} variant that gives a good
approximation to the true solution at reasonable computational
cost. We conclude with some numerical examples.",
keywords = "short memory, finite memory, logarithmic memory"
}
@techreport{Edwards:2001:BSDE,
author = "J. T. Edwards and N. J. Ford",
title = "Boundedness and Stability of Difference Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 384",
pages = "14",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep384.ps.gz",
abstract = "This paper is concerned with the qualitative behaviour of solutions to
difference equations. We focus on boundedness and stability of solutions
and we present a unified theory that applies both to autonomous and
non-autonomous equations and to nonlinear equations as well as linear
equations. Our presentation brings together new, established, and
hard-to-find results from the literature and provides a theory that is both
memorable and easy to apply. We show how the theoretical results given here
relate to some of those in the established literature and by means of simple
examples we indicate how the use of Lipschitz constants in this way can provide
useful insights into the qualitative behaviour of solutions to some nonlinear
problems including those arising in numerical analysis.",
keywords = "boundedness, stability, Lipschitz"
}
@techreport{Ford:2001:SHQ,
author = "N. J. Ford and P. D. Crofts and R. H. T. Edwards",
title = "Sensitivity of Hospital Clinic Queues to Patient Non-Attendance",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "383",
month = feb,
pages = "6",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep383.ps.gz",
abstract = "The recently introduced Patients' Charter offers patients in the United
Kingdom a guaranteed minimum quality of service when they require hospital
treatment. For example, the following guarantees are offered: 1. No
patient should be required to spend more than one year awaiting an offer
of an appointment with a Consultant 2. Patients should not be expected to
wait in clinic for more than 30 minutes without seeing a doctor. Health
economists are active in devising strategies and systems to deal with these
enhanced patient expectations. In this paper, we describe the work of an
interdisciplinary team, funded by the UK National Health Service Research
and Development which investigated computer simulation of clinic queues to
provide further insight into the problem and to produce computer software
that can assist in clinic optimisation.",
keywords = "optimisation, modelling, queues"
}
@techreport{Ford:2001:NDSS,
author = "Neville J Ford and Sjoerd M Verduyn Lunel",
title = "Numerical approximation of delay differential equations with small
solutions",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "382",
month = feb,
pages = "6",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep382.ps.gz",
abstract = "We are concerned with the detection of small solutions of delay differential equations.
We consider, as prototype, an equation of the form $\dot{y}(t)=b(t)y(t-\tau)$ for
which conditions on the function $b$ that govern the existence (or otherwise) of small
solutions are well-known. We apply simple numerical methods to the problem and
investigate the characteristic values of the solution operator. We show how these
characteristic roots may be used to detect the existence of small solutions.",
keywords = "small solutions, floquet theory, characteristic values"
}
@techreport{Ford:2001:CSS,
author = "Neville J. Ford and Sjoerd M. Verduyn Lunel",
title = "Characterising Small Solutions in Delay Differential Equations
Through Numerical Approximations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "381",
month = feb,
pages = "15",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep381.ps.gz",
abstract = "The existence of small solutions, i.e., solutions that decay
faster than any exponential, for linear time-dependent
differential delay equations with bounded coefficients depends on
specific properties of the coefficients. Although small solutions
do not occur in the finite dimensional approximations of the
differential delay equation we show that the existence of small
solutions for differential delay equations can be predicted from
the behaviour of the spectrum of the finite dimensional
approximations.",
keywords = "small solutions, floquet theory"
}
@techreport{Edwards:2001:IDBP,
author = "J. T. Edwards, J. A. Roberts and N. J. Ford",
title = "The numerical Solution of an Integro-Differential Equation Close to
Bifurcation Points",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 380",
pages = "6",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep380.ps.gz",
abstract = "In this paper we investigate the qualitative behaviour of numerical
approximations to a Volterra integro-differential equation. We consider (as
prototype) a linear problem with fading memory kernel of the form
$$y'(t)=-\int^t_0e^{-\lambda(t-s)}y(s)ds, \qquad \qquad y(0)=1$$ and we consider
the performance of simple numerical schemes applied to solve the equation. We
are concerned with the preservation (or otherwise) of qualitative properties of
the analytical solution in the numerical approximation. We outline the known
stability behaviour and derive the values of $\lambda$ at which the true solution
bifurcates. We give the corresponding analysis for the discrete schemes and we show
that, as the step size of the numerical scheme decreases, the bifurcation points
tend towards those of the continuous scheme. We illustrate our results with some
numerical examples.",
keywords = "bifurcations, numerical approximations, integro-differential equations"
}
@techreport{Ford:2001:FESO,
author = "N. J. Ford and K. Diethelm",
title = "The numerical Solution of Linear and Non-Linear Fractional
Differential Equations Involving Fractional Derivatives of
several orders",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 379",
month = feb,
pages = 14,
year = 2001,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep379.ps.gz",
abstract = "We consider fractional differential equations of the very general
form $y^{(\alpha)}(t)= f(t,y(t),y^{(\beta_1)}(t),y^{(\beta_2)}(t),
\ldots,y^{(\beta_n)}(t))$ with $\alpha>\beta_1>\beta_2>\ldots>\beta_n$
and $\alpha-\beta_1\le1$,$\beta_j-\beta_{j+1}\le1$, $0\le\beta_n\le1$,
and where the derivatives are understood in Caputo's sense.For equations of
this type, we discuss the questions of existence and uniqueness of solutions,
and we investigate how the solutions depend on the given data. We propose
convergent and stable numerical methods based on a nearly equivalent system
of fractional differential equations of order not exceeding $\beta_n$. We
give particular emphasis to the practically important linear case and also
present results for nonlinear problems.",
keywords = "milti-term equation, fractional order, fractional Adams method"
}
@techreport{Ford:2001:NBT,
author = "N. J. Ford and K. Diethelm",
title = "Numerical Solution of the {Bagley Torvik} Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 378",
month = feb,
pages = 12,
year = 2001,
note = "Submitted to BIT",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep378.ps.gz",
abstract = "We consider the numerical solution of the Bagley-Torvik
equation $$ A y''(t) + B D_*^{3/2}y(t) + C y(t) = f(t)$$
as a prototype fractional differential equation with two
derivatives. Approximate solutions have recently been proposed in
the book and papers of Podlubny in which the solution obtained with
approximate methods is compared to the exact solution. In this paper
we consider the reformulation of the Bagley-Torvik equation as a
system of fractional differential equations of order $1/2$. This
allows us to propose numerical methods for its solution which are
consistent and stable and have arbitrarily high order.",
keywords = "Bagley Torvik, multi-term, fractional order"
}
@techreport{Ford:2001:AFDE,
author = "N. J. Ford and K. Diethelm",
title = "Analysis of Fractional Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 377",
month = feb,
pages = 17,
year = 2001,
note = "To appear in Journal of Mathematical Analysis and Applications",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep377.ps.gz",
abstract = "We discuss existence, uniqueness and {\it structural stability}
of solutions of nonlinear differential equations of fractional
order. The differential operators are taken in the
Riemann-Liouville sense and the initial conditions are specified
according to Caputo's suggestion, thus allowing for interpretation
in a physically meaningful way. We investigate in particular the
dependence of the solution on the order of the differential
equation and on the initial condition and we relate our results
to the selection of appropriate numerical schemes for the solution
of fractional differential equations.",
keywords = "fractional order, stability, existence, uniqueness, numerical schemes"
}
@techreport{Bolton:2001:MCLS,
author = "P. Bolton and J. Stratakis and R. W. Thatcher",
title = "Mass Conservation in Least Squares Methods for {Stokes} Flow",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 376",
pages = "22",
month = jun,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep376.pdf"
}
@techreport{Basebi:2001:ASMM,
author = "Thebe Basebi and Ruth M. Thomas",
title = "A Study of Moving Mesh Methods Applied to a Thin Flame
Propagating in a Detonator Delay Element",
type = t-NAREP,
number = "No. 375",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "2001",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep375.ps.gz",
abstract = "We study the application of moving mesh methods to a
one-dimensional (time dependent) detonator delay element
problem. We consider moving mesh methods based on the
equidistribution principle derived by
Huang $et$ $al.$ (1994). Adaptive mesh methods have been widely
used recently to solve time dependent partial differential
equations having large solution gradients. Significant
improvements in accuracy and efficiency are achieved by
adapting the nodes (mesh points) so that they are
concentrated about areas of large solution variations.
Each system of equations for the moving mesh methods is
solved in conjunction with the detonator problem. In this
paper, the system of ordinary differential equations that
results (after discretising in space) is solved using the
double precision version of the stiff ordinary differential
equation solver DASSL. The numerical results clearly
demonstrate that the moving mesh methods are capable of
tracking the deflagration wave as it travels down the
detonator delay element more accurately and more efficiently
than a fixed mesh method.",
keywords = "moving mesh methods, detonator delay element, time dependent
partial differential equations, scaling, monitor functions."
}
@techreport{Cheng:2001:PIB,
author = "Sheung Hun Cheng and Nicholas J. Higham",
title = "Parallel Implementation of a Block Algorithm for Matrix 1-Norm
Estimation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "No. 374",
pages = "9",
month = feb,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep374.pdf",
abstract = "We describe a parallel Fortran~77 implementation, in ScaLAPACK
style, of a block matrix 1-norm estimator of Higham and Tisseur.
This estimator differs from that underlying the existing
ScaLAPACK code, \texttt{PxLACON}, in that it iterates with a
matrix with $t$ columns, where $t\ge 1$ is a parameter, rather
than with a vector, and so the basic computational kernel is
level 3 BLAS operations. Our experiments on an SGI Origin2000
show that with $t=2$ or $4$ the new code offers better estimates
than \texttt{PDLACON} with a similar execution time. Moreover,
with $t>4$, estimates exact over $90\%$ of the time are achieved
with execution time growing much slower than $t$.",
keywords = ""
}
@techreport{Higham:2001:DDH,
author = "Nicholas J. Higham and Fran\c{c}oise Tisseur and
Paul M. Van Dooren",
title = "Detecting a Definite {Hermitian} Pair
and a Hyperbolic or Elliptic Quadratic Eigenvalue Problem,
and Associated Nearness Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "373",
month = feb,
pages = "18",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep373.ps.gz",
abstract = "An important class of generalized eigenvalue problems $Ax =
\lambda Bx$ is those in which $A$ and $B$ are Hermitian and some
real linear combination of them is definite. For the quadratic
eigenvalue problem (QEP) $(\l^2 A + \l B + C)x = 0$ with
Hermitian $A$, $B$ and $C$ and positive definite $A$, particular
interest focuses on problems in which $(x^*Bx)^2 - 4
(x^*Ax)(x^*Cx)$ is one-signed for all nonzero $x$---for the
positive sign these problems are called hyperbolic and for the
negative sign elliptic. The important class of overdamped
problems arising in mechanics is a sub-class of the hyperbolic
problems. For each of these classes of generalized and quadratic
eigenvalue problems we show how to check that a putative member
has the required properties and we derive the distance to the
nearest problem outside the class. For definite pairs $(A,B)$ the
distance is the Crawford number, and we derive bisection and
level set algorithms both for testing its positivity and for
computing it. Testing hyperbolicity of a QEP is shown to reduce
to testing a related pair for definiteness. The distance to the
nearest non-hyperbolic or non-elliptic $n\times n$ QEP is shown
to be the solution of a global minimization problem with $n-1$
degrees of freedom. Numerical results are given to illustrate the
theory and algorithms.",
keywords = "Generalized eigenvalue problem, definite pair, Crawford number,
quadratic eigenvalue problem, hyperbolic system, elliptic system,
overdamped system, gyroscopic system, bisection algorithm, level
set algorithm, nearness problems"
}
@techreport{Higham:2001:MPP,
author = "Nicholas J. Higham and Fran\c{c}oise Tisseur",
title = "More on Pseudospectra for Polynomial Eigenvalue Problems
and Applications in Control Theory",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "372",
month = jan,
pages = "21",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep372.ps.gz",
abstract = "Definitions and characterizations of pseudospectra are given for
rectangular matrix polynomials expressed in homogeneous form:
$P(\a,\b) = (\a^dA_d + \a^{d-1}\b A_{d-1} + \cdots + \b^d A_0)$.
It is shown that problems with infinite (pseudo)eigenvalues are
elegantly treated in this framework. For such problems
stereographic projection onto the Riemann sphere is shown to
provide a convenient way to visualize pseudospectra. Lower bounds
for the distance to the nearest non-regular polynomial and the
nearest uncontrollable $d$th order system (with equality for
standard state-space systems) are obtained in terms of
pseudospectra, showing that pseudospectra are a fundamental tool
for reasoning about matrix polynomials in areas such as control
theory. How and why to incorporate linear structure into
pseudospectra is also discussed by example.",
keywords = "polynomial eigenvalue problem, $\lambda$-matrix, matrix
polynomial, homogeneous form, pseudospectrum, stereographic
projection, Riemann sphere, nearest non-regular polynomial,
nearest uncontrollable system, structured perturbations"
}
@techreport{Tisseur:2001:BEM,
author = "Nicholas J. Higham and Fran\c{c}oise Tisseur",
title = "Bounds for Eigenvalues of Matrix Polynomials",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = t-NAREP,
number = "371",
month = jan,
pages = "16",
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep371.pdf",
abstract = "Upper and lower bounds are derived for the absolute values of the
eigenvalues of a matrix polynomial (or $\lambda$-matrix). The
bounds are based on norms of the coefficient matrices and involve
the inverses of the leading and trailing coefficient matrices.
They generalize various existing bounds for scalar polynomials
and single matrices. A variety of tools are used in the
derivations, including block companion matrices, Gershgorin's
theorem, the numerical radius, and associated scalar polynomials.
Numerical experiments show that the bounds can be surprisingly
sharp on practical problems.",
keywords = "polynomial eigenvalue problem, $\lambda$-matrix, matrix
polynomial, block companion matrix, Gershgorin's theorem,
numerical radius"
}
@techreport{Tisseur:2000:SQEP,
author = "Fran\c{c}oise Tisseur and Karl Meerbergen",
title = "The Quadratic Eigenvalue Problem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 370",
pages = "49",
month = nov,
year = "2000",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep370.ps.gz",
abstract = "We survey the quadratic eigenvalue problem,
treating its many applications, its
mathematical properties, and a variety of numerical
solution techniques. Emphasis is given to exploiting
both the structure of the matrices in the problem
(dense, sparse, real, complex, Hermitian,
skew-Hermitian) and the spectral properties of the
problem. We classify the available choices of methods
and catalogue available software.",
keywords = "quadratic eigenvalue problem, eigenvalue, eigenvector,
$\lambda$-matrix, matrix polynomial, second-order
differential equation, overdamped system, gyroscopic
system, linearization, backward error, pseudospectrum,
condition number, Krylov methods, Arnoldi method, Lanczos
method, Jacobi-Davidson method"
}
@techreport{Higham:2000:CNC,
author = "Nicholas J. Higham",
title = "Computing the Nearest Correlation Matrix---{A} Problem from Finance",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 369",
month = oct,
pages = 14,
year = 2000,
note = "Revised July 2001",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep369.pdf",
abstract = "Given a symmetric matrix what is the nearest correlation matrix,
that is, the nearest symmetric positive semidefinite matrix with
unit diagonal? This problem arises in the finance industry, where
the correlations are between stocks. For distance measured in the
Frobenius norm, we characterize the solution using convex
analysis. We show how the modified alternating projections method
can be used to compute the solution. In the finance application
the original matrix has many zero or negative eigenvalues; we
show that the nearest correlation matrix has correspondingly many
zero eigenvalues and that this fact can be exploited in the
computation.",
keywords = "correlation matrix, positive semidefinite matrix, nearness
problem, convex analysis, alternating projections method"
}
@techreport{Paul:2000:DES,
author = "Christopher Paul",
title = "Designing Efficient Software for Solving Delay Differential
Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 368",
month = oct,
pages = 13,
year = 2000,
note = "To appear in Journal of Computational Applied Mathematics",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep368.ps.gz",
abstract = "In this paper the efficient implementation of numerical software
for solving delay differential equations is addressed. Several
strategies that have been developed over the past 25 years for
improving the efficiency of delay differential equation solvers
are described. Of particular interest is a new method of
automatically constructing the network dependency graph used in
tracking derivative discontinuities."
}
@techreport{Baker:2000:DAE,
author = "Christopher Baker and Christopher Paul and Hongjiong Tian",
title = "Differential Algebraic Equations with After-Effect",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 367",
month = oct,
pages = 20,
year = 2000,
note = "Submitted to Journal of Computational Applied Mathematics",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep367.ps.gz",
abstract = "We consider the numerical solution of delay differential
algebraic equations - they are differential algebraic equations
with after-effect, or constrained delay differential equations.
The general semi-explicit form of the problem consists of a set
of delay differential equations along with a set of constraints
that may involve retarded arguments. Even simply-stated problems
of this type can give rise to difficult analytical and numerical
problems. The more tractable examples can be shown to be
equivalent to systems of delay or neutral delay differential
equations. We shall explore, in particular through examples, some
of the complexities and obstacles that can arise when solving
these problems."
}
@techreport{MCCM:2001:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1999",
type = "Numerical Analysis Report",
number = "No. 364",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "24",
month = mar,
year = "2001",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep364.ps.gz",
}
@techreport{Dedieu:2001:PTH,
author = "Jean-Pierre Dedieu and Fran\c{c}oise Tisseur",
title = "Perturbation Theory for Homogeneous Polynomial Eigenvalue Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 363",
pages = "21",
month = mar,
year = "2001",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep363.ps.gz",
abstract = "We consider polynomial eigenvalue problems
$P(A,\alpha,\beta)x=0$ in which the matrix polynomial is
homogeneous in the eigenvalue $(\alpha,\beta)\in\mathbb{C}^2$.
In this framework infinite eigenvalues are on the same
footing as finite eigenvalues. We view the problem in
projective spaces to avoid normalization of the
eigenpairs. We show that a polynomial eigenvalue problem
is well-posed when its eigenvalues are simple. We define
the condition numbers of a simple eigenvalue
$(\a,\beta)$ and a corresponding eigenvector $x$ and
show that the distance to the nearest ill-posed problem
is equal to the reciprocal of the condition number of
the eigenvector $x$. We describe a bihomogeneous Newton
method for the solution of the homogeneous polynomial
eigenvalue problem.",
keywords = "polynomial eigenvalue problem, matrix polynomial,
quadratic eigenvalue problem,condition number"
}
@techreport{Silvester:00:EPB,
author = "David Silvester and Milan Mihajlovic",
title = "A black-box multigrid preconditioner for the biharmonic equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 362",
month = aug,
year = 2002,
note = "Submitted to BIT",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep362.ps.gz",
abstract = "We examine the convergence characteristics of a preconditioned
Krylov subspace solver applied to the linear systems arising from low-order
mixed finite element approximation of the biharmonic problem. The key
feature of our approach is that the preconditioning can be realized using
any ``black-box'' multigrid solver designed for the discrete Dirichlet
Laplacian operator. This leads to preconditioned systems having an
eigenvalue distribution consisting of a tightly clustered set together
with a small number of outliers. Numerical results show that the
performance of the methodology is competitive with that of specialized
fast iteration methods that have been developed in the context of
biharmonic problems."
}
@techreport{Baker:2000:CTM,
author = "Christopher T. H. Baker and Evelyn Buckwar",
title = "Continuous $\Theta$-methods for the Stochastic Pantograph
Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 361",
month = may,
year = 2000,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep361.ps.gz",
abstract = "We consider a stochastic version of the pantograph equation:
\begin{eqnarray}\nonumber dX(t) &= & \Big\{ a X(t)+ b X (qt)
\Big\} dt + \Big\{\sigma_1 + \sigma_2\ X(t) + \sigma_3 X
(qt)\Big\}dW(t), \\[-1mm]\nonumber && \label{spanto}
\\[-1mm]\nonumber X(0) &= & X_0, \nonumber \end{eqnarray} for $
t \in [0,T]$, a given Wiener noise $W$ and $0 < q < 1$. This is
an example of an It\^{o} stochastic delay differential equation
with unbounded memory.
We give the necessary analytical theory for existence and
uniqueness of a strong solution of ($\ddagger$), and of strong
approximations to the solution obtained by a continuous extension
of the $\Theta$-Euler scheme ($\Theta \in [0,1]$). We establish
${\mathcal O}(h^\half)$ mean-square convergence of approximations
obtained using a bounded mesh of uniform step $h$, rising in the
case of additive noise only to ${\mathcal O}(h)$. Illustrative
numerical examples are provided.",
keywords = "Stochastic delay differential equation, continuous
$\Theta$-method, mean-square convergence."
}
@techreport{Davies:2000:ACM,
author = "Philip I. Davies and Nicholas J. Higham and Fran\c{c}oise Tisseur",
title = "Analysis of the {Cholesky} Method with Iterative Refinement for
Solving the Symmetric Definite Generalized Eigenproblem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 360",
month = jun,
pages = 21,
year = "2000",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep360.pdf",
abstract = "A standard method for solving the symmetric definite generalized
eigenvalue problem $Ax = \lambda Bx$, where $A$ is symmetric and
$B$ is symmetric positive definite, is to compute a Cholesky
factorization $B = LL^T$ (optionally with complete pivoting) and
solve the equivalent standard symmetric eigenvalue problem $C y =
\l y$ where $C = L^{-1} A L^{-T}$. Provided that a stable
eigensolver is used, standard error analysis says that the
computed eigenvalues are exact for $A+\dA$ and $B+\dB$ with
$\max( \normt{\dA}/\normt{A}, \normt{\dB}/\normt{B} )$ bounded by
a multiple of $\kappa_2(B)u$, where $u$ is the unit roundoff. We
take the Jacobi method as the eigensolver and give a detailed
error analysis that yields backward error bounds potentially much
smaller than $\kappa_2(B)u$. To show the practical utility of our
bounds we describe a vibration problem from structural
engineering in which $B$ is ill conditioned yet the error bounds
are small. We show how, in cases of instability, iterative
refinement based on Newton's method can be used to produce
eigenpairs with small backward errors. Our analysis and
experiments also give insight into the popular Cholesky--QR
method, in which the QR method is used as the eigensolver. We
argue that it is desirable to augment current implementations of
this method with pivoting in the Cholesky factorization.",
keywords = "symmetric definite generalized eigenvalue problem, Cholesky
method, Cholesky factorization with complete pivoting, Jacobi
method, backward error analysis, rounding error analysis,
iterative refinement, Newton's method, LAPACK, MATLAB."
}
@techreport{Tisseur:2000:SPP,
author = "Fran\c{c}oise Tisseur and Nicholas J. Higham",
title = "Structured Pseudospectra for Polynomial Eigenvalue Problems,
with Applications",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 359",
month = apr,
pages = 22,
year = "2000",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep359.pdf",
abstract = "Pseudospectra associated with the standard and generalized
eigenvalue problems have been widely investigated in recent
years. We extend the usual definitions in two respects, by
treating the polynomial eigenvalue problem and by allowing
structured perturbations of a type arising in control theory. We
explore connections between structured pseudospectra, structured
backward errors, and structured stability radii. Two main
approaches for computing pseudospectra are described. One is
based on a transfer function and employs a generalized Schur
decomposition of the companion form pencil. The other, specific
to quadratic polynomials, finds a solvent of the associated
quadratic matrix equation and thereby factorizes the quadratic
$\lambda$-matrix. Possible approaches for large, sparse problems
are also outlined. A collection of examples from vibrating
systems, control theory, acoustics and fluid mechanics is given
to illustrate the techniques.",
keywords = "polynomial eigenvalue problem, $\lambda$-matrix, matrix
polynomial, pseudospectrum, stability radius, backward error,
transfer function, quadratic matrix equation, solvent, structured
perturbations, Orr--Sommerfeld equation"
}
@techreport{Higham:2000:EPA,
author = "Nicholas J. Higham",
title = "Evaluating {Pad\'e} Approximants of the Matrix Logarithm",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 358",
month = mar,
pages = 10,
year = 2000,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep358.pdf",
abstract = "The inverse scaling and squaring method for evaluating the
logarithm of a matrix takes repeated square roots to bring the
matrix close to the identity, computes a Pad\'e approximant, and
then scales back. We analyze several methods for evaluating the
Pad\'e approximant, including Horner's method (used in some
existing codes), suitably customized versions of the
Paterson--Stockmeyer method and Van Loan's variant, and methods
based on continued fraction and partial fraction expansions. The
computational cost, storage, and numerical accuracy of the
methods are compared. We find the partial fraction method to be
the best method overall and illustrate the benefits it brings to
a transformation-free form of the inverse scaling and squaring
method recently proposed by Cheng, Higham, Kenney and Laub. We
comment briefly on how the analysis carries over to the matrix
exponential.",
keywords = "matrix logarithm, Pad\'e approximation, inverse scaling and
squaring method, Horner's method, Paterson--Stockmeyer method,
continued fraction, partial fraction expansion"
}
@techreport{Tisseur:2000:SSHE,
author = "Fran\c{c}oise Tisseur",
title = "Stability of Structured {Hamiltonian} Eigensolvers",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 357",
pages = "23",
month = feb,
year = "2000",
URL = "ftp://ftp.ma.man.ac.uk/pub/narep/narep357.ps.gz",
abstract = "Various applications give rise to eigenvalue problems
for which the matrices are Hamiltonian or
skew-Hamiltonian and also symmetric or skew-symmetric.
We define structured backward errors that are useful for
testing the stability of numerical methods for the
solution of these four classes of structured
eigenproblems. We introduce the symplectic quasi-QR
factorisation and show that for three of the classes it
enables the structured backward error to be efficiently
computed. We also give a detailed rounding error
analysis of some recently developed Jacobi-like
algorithms of Fa{\ss}bender, Mackey \& Mackey for these
eigenproblems. Based on the direct solution of $4\times
4$, and in one case $8\times 8$, structured subproblems
these algorithms produce a complete basis of symplectic
orthogonal eigenvectors for the two symmetric cases and
a symplectic orthogonal basis for all the real invariant
subspaces for the two skew-symmetric cases. We prove
that, when the rotations are implemented using suitable
formulae, the algorithms are strongly backward stable
and we show that the QR algorithm does not have this
desirable property",
keywords = "Backward error, Hamiltonian, skew-Hamiltonian,
symmetric-Hamiltonian, skew-symmetric skew-Hamiltonian,
structure-preserving, rounding error, symplectic,
quaternion rotation"
}
@techreport{Sturgeon:2000:SSD,
author = "J. A. Sturgeon and R. M. Thomas and I. Gladwell",
title = "Solving a Singular DAE Model of Unconfined Detonation",
type = "Numerical Analysis Report",
number = "No. 356",
institution = inst-mccm,
address = inst-mccm:adr,
month = apr,
year = "2000",
pages = "27",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep356.ps.gz",
abstract = "We consider a simplified model of an unconfined one-dimensional
detonation problem, giving a brief survey of the history of the
problem and of its numerical solution. This problem with its
mathematical features is typical of those solved commercially
by ICI plc, and the specific values used for the chemical
constants in the example are typical of those of interest.
Unfortunately, not all obvious methods work well, because of the
singular nature of the problem at the Chapman-Jouguet shock
front. We concentrate on shooting methods for the detonation
problem based on backward differentiation formula integrators,
and present a new analysis which explains how these methods
work. Finally, we outline some possibilities for further work,
including discussing a more general detonation problem,
previous solutions and potential future solution methods",
keywords = "detonation problem, differential-algebraic equations, backward
differentiation formulae, shooting methods, numerical analysis,
Chapman-Jouguet shock front"
}
@techreport{Langlois:1999:ALC,
author = "Philippe Langlois",
title = "Automatic Linear Correction of Rounding Errors",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 355",
month = nov,
pages = "24",
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep355.ps.gz",
abstract = "A new automatic method to correct the first-order effect of
floating point rounding errors on the result of a numerical
algorithm is presented. A correcting term and a confidence
threshold are computed using automatic differentiation,
computation of elementary rounding error and running error
analysis. Algorithms for which the accuracy of the result is not
affected by higher order terms are identified. The correction is
applied to the final result or to sensitive intermediate results.
The properties and the efficiency of the method are illustrated
with a sample numerical example.",
keywords = "automatic error analysis, rounding error, floating point
arithmetic"
}
@techreport{Davies:1999:NSG,
author = "Philip I. Davies and Nicholas J. Higham",
title = "Numerically Stable Generation of
Correlation Matrices and their Factors",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 354",
month = nov,
pages = "15",
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep354.pdf",
abstract = "Correlation matrices---symmetric positive semidefinite matrices
with unit diagonal---are important in statistics and in numerical
linear algebra. For simulation and testing it is desirable to be
able to generate random correlation matrices with specified
eigenvalues (which must be nonnegative and sum to the dimension
of the matrix). A popular algorithm of Bendel and Mickey takes a
matrix having the specified eigenvalues and uses a finite
sequence of Given rotations to introduce $1$s on the diagonal. We
give improved formulae for computing the rotations and prove that
the resulting algorithm is numerically stable. We show by example
that the formulae originally proposed, which are used in certain
existing Fortran implementations, can lead to serious
instability. We also show how to modify the algorithm to generate
a rectangular matrix with columns of unit 2-norm. Such a matrix
represents a correlation matrix in factored form, which can be
preferable to representing the matrix itself, for example when
the correlation matrix is nearly singular to working precision.",
keywords = "random correlation matrix, Bendel--Mickey algorithm, eigenvalues,
singular value decomposition, test matrices, forward error
bounds, relative error bounds, IMSL, NAG Library, Jacobi method"
}
@techreport{Cheng:1999:ALM,
author = "Sheung Hun Cheng and Nicholas J. Higham and Charles S. Kenney
and Alan J. Laub",
title = "Approximating the Logarithm of a Matrix to Specified Accuracy",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 353",
pages = "14",
month = nov,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep353.ps.gz",
abstract = "The standard inverse scaling and squaring algorithm for computing
the matrix logarithm begins by transforming the matrix to Schur
triangular form in order to facilitate subsequent matrix square
root and Pad\'e approximation computations. A transformation-free
form of this method is presented that exploits incomplete
Denman--Beavers square root iterations and aims for a specified
accuracy. The error introduced by using approximate square roots
is accounted for by a novel splitting lemma for logarithms of
matrix products. The number of square root stages and the degree
of the final Pad\'e approximation are chosen to minimize the
computational work. This new method is attractive for
high-performance computation since it uses only the basic
building blocks of matrix multiplication, LU factorizati on and
matrix inversion.",
keywords = "matrix logarithm, Pad\'e approximation, inverse scaling and
squaring method, matrix square root, Denman--Beavers iteration"
}
@techreport{Silvester:99:EPL,
author = "David Silvester and Howard Elman and David Kay and Andrew Wathen",
title = "Efficient Preconditioning of the Linearized {Navier-Stokes}
Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 352",
month = oct,
year = "1999",
note = "Solicited by the Journal of Computational and Applied Mathematics",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep352.ps.gz",
abstract = "We outline a new class of robust and efficient methods for
solving subproblems that arise in the linearization and
operator splitting of Navier-Stokes equations. We describe
a very general strategy for preconditioning that has two
basic building blocks; a multigrid V-cycle for the
scalar convection-diffusion operator, and a multigrid V-cycle
for a pressure Poisson operator. We present numerical
experiments illustrating that a simple implementation
of our approach leads to an effective and robust solver
strategy in that the convergence rate is independent of the grid,
robust with respect to the time-step, and only deteriorates
very slowly as the Reynolds number is increased."
}
@techreport{Ford:1999:HDN,
author = "Neville J. Ford and Volker Wulf",
title = "How Do Numerical Methods Perform for Delay Differential Equations
Undergoing a {Hopf} Bifurcation?",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 351",
pages = "10",
month = sep,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep351.ps.gz",
abstract = "In this report we consider the numerical solution of delay
differential equations that undergo a Hopf bifurcation. We show
that, under suitable conditions on the choice of method, the Hopf
bifurcation is maintained in the approximation, and that the
class of bifurcation is also preserved.",
keywords = "Delay differential equations, numerical methods, Hopf
bifurcation"
}
@techreport{Ford:1999:Charroots,
author = "Neville J. Ford",
title = "Numerical Approximation of the Characteristic Values for a Delay
Differential Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 350",
pages = "11",
month = sep,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep350.ps.gz",
abstract = "In this report we consider the characteristic roots of numerical
approximations of delay differential equations and their
relationship to the characteristic values of the original
problem. We are able to show that, as h -> 0, the characteristic
roots are approximated to the order of the method.",
keywords = "Delay differential equations, characteristic roots, numerical
methods, stability coefficient"
}
@techreport{Rihan:99:SAP,
author = "Christopher T. H. Baker and Fathalla A. Rihan",
title = "Sensitivity Analysis of Parameters in Modelling With
Delay-Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 349",
month = aug,
pages = 22,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep349.ps.gz",
abstract = "Many problems in bioscience for which
observations are reported in the literature can be modelled by
suitable functional differential equations incorporating a delay,
parameterized by parameters $ p_1$,$p_2$,$\dots$,$p_L$. Given such
observations (which usually contain error or 'noise'), we may
determine the parameters $\{p_i\}$ by fitting the model equations to
the data and optimizing a measure of best fit.
Our aim in this paper is to produce a new method to estimate (i) the
sensitivity of the state variables to the parameter estimates $\{
p_i\}$, (ii) the sensitivity of the parameter estimates to the
observations and (iii) the nonlinearity effects for delay differential
models. The sensitivity of the parameter estimate to the observation
is {\it low} if the sensitivity of the state variable to the parameter
estimate is {\it high}. Sensitivity coefficients are used to
determine the covariance matrix of parameter estimates and hence to
determine the standard deviations. Numerical results are used to
illustrate the results.",
keywords = "Sensitivity analysis, parameter estimates, neutral
delay differential equation, time-lag, nonlinearity effect."
}
@techreport{Norburn:99:FAS,
author = "Sean Norburn and David Silvester ",
title = "Fourier Analysis of Stabilised {Q1-Q1} Mixed
Finite Element Approximation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 348",
month = sep,
year = 1999,
note = "Submitted to the SIAM Journal on Numerical Analysis",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep348.ps.gz",
abstract = "We use Fourier analysis to investigate the instability
of an equal-order mixed finite element approximation
method for elliptic incompressible flow equations.
The lack of stability can be attributed to the fact that
the associated discrete LBB (Ladyzhenskaya-Babuska-Brezzi)
constant tends to zero as the mesh size is reduced.
We develop a stabilisation approach that is appropriate
to the periodic setting, and deduce optimal choices of
the associated stabilisation parameter."
}
@techreport{Higham:99:NAQ,
author = "Nicholas J. Higham and Hyun-Min Kim",
title = "Numerical Analysis of a Quadratic Matrix Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 347",
month = aug,
pages = 26,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep347.pdf",
abstract = "The quadratic matrix equation $AX^2 + BX + C = 0$ in $n\times n$
matrices arises in applications and is of intrinsic interest as
one of the simplest nonlinear matrix equations. We give a
complete characterization of solutions in terms of the
generalized Schur decomposition and describe and compare various
numerical solution techniques. In particular, we give a thorough
treatment of functional iteration methods based on Bernoulli's
method. Other methods considered include Newton's method with
exact line searches, symbolic solution and continued fractions.
We show that functional iteration applied to the quadratic matrix
equation can provide an efficient way to solve the associated
quadratic eigenvalue problem $(\lambda^2 A + \lambda B +
C)x=0$.",
keywords = "quadratic matrix equation, solvent, generalized Schur
decomposition, scaling, functional iteration, Bernoulli's method,
Newton's method, exact line searches, continued fractions,
quadratic eigenvalue problem",
}
@techreport{Tisseur:99:NMFPA,
author = "Fran\c{c}oise Tisseur",
title = "Newton's Method in Floating Point Arithmetic
and Iterative Refinement of Generalized Eigenvalue Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 346",
pages = "26",
month = aug,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep346.ps.gz",
abstract = "We examine the behaviour of Newton's method in floating
point arithmetic, allowing for extended precision in
computation of the residual, inaccurate evaluation of the
Jacobian and unstable solution of the linear systems. We
bound the limiting accuracy and the smallest norm of the
residual. The application that motivates this work is
iterative refinement for the generalized eigenvalue
problem. We show that iterative refinement by Newton's
method can be used to improve the forward and backward
errors of computed eigenpairs.",
keywords = " Newton's method, generalized eigenvalue problem, iterative
refinement, backward error, forward error, rounding error
analysis, limiting accuracy, limiting residual"
}
@techreport{Baker:99:INA,
author = "Christopher T. H. Baker and Evelyn Buckwar",
title = "Introduction to the Numerical Analysis of Stochastic Delay
Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 345",
month = aug,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep345.ps.gz",
abstract = "We consider the problem of strong approximations of
the solution of stochastic delay differential equations
of It\^{o} form
\[
\begin{array}{rcl}
dX(t) &= & f(t, X(t),X (t- \tau) ) \; dt
+ g(t, X(t),X (t- \tau) )\; dW(t),
\ t \in [0,T] \\
X(t) &= & \Psi(t), \qquad t \in [-\tau,0],
\end{array}
\]
for given $f, g$, Wiener noise $W$ and given $\tau > 0$,
with a prescribed initial function $\Psi$. We indicate the
nature of the equations of interest and the problems
that arise in a discussion of their numerical treatment,
provide necessary background material, and give a
convergence proof for an Euler-Maruyama scheme. Some
illustrative numerical examples are provided."
}
@techreport{MCCM:2000:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1998",
type = "Numerical Analysis Report",
number = "No. 344",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "24",
month = mar,
year = "2000",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep344.ps.gz",
}
@techreport{Rihan:99:RUD,
author = "Christopher T. H. Baker and Gennadii A. Bocharov and
Fathalla A. Rihan",
title = "A Report on the Use of Delay Differential Equations
in Numerical Modelling in the Biosciences",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 343",
month = aug,
pages = 45,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep343.ps.gz",
abstract = "We review the application of numerical techniques to investigate
mathematical models of phenomena in the biosciences using delay
differential equations. We show that there are {\em prima facie}
reasons for using such models: $(i)$ they have a richer mathematical
framework (compared with ordinary differential equations) for the
analysis of biosystems dynamics, $(ii)$ they display better
consistency with the nature of the underlying processes and predictive
results. We now have suitable computational techniques to treat
numerically the emerging models for the biosciences.",
keywords = "Delay differential equations, dynamical systems,
biological systems, deterministic and stochastic models,
numerical modelling, parameter estimation, optimization."
}
@techreport{Edwards:1999:EBS,
author = "John T. Edwards and Jason A. Roberts",
title = "On the Existence of Bounded Solutions of Discrete Analogues for a
Nonlinear Integrodifferential Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 342",
pages = "14",
month = sep,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep342.ps.gz",
abstract = "This work is concerned with the boundedness and ultimately the
asymptotic stability of solutions of discrete analogues of a
nonlinear integrodifferential equation with convolution kernel.
In previous work, the stability analysis of the nonlinear
equation required the assumption that bounded solutions exist. We
prove in this work that, for a certain choice of discretization
of the equation, all solutions are bounded (and
hence asymptotically stable) provided the equation's parameters
fall within certain ranges.",
keywords = "Volterra integrodifferential equations, numerical methods,
difference equations, stability analysis"
}
@techreport{Higham:99:BAM,
author = "Nicholas J. Higham and Fran\c{c}oise Tisseur",
title = "A Block Algorithm for Matrix 1-Norm Estimation,
with an Application to 1-Norm Pseudospectra",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 341",
month = apr,
pages = 32,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep341.ps.gz",
abstract = "The matrix 1-norm estimation algorithm used in LAPACK and various
other software libraries and packages has proved to be a valuable
tool. However, it has the limitations that it offers the user no
control over the accuracy and reliability of the estimate and
that it is based on level~2 BLAS operations. A block
generalization of the 1-norm power method underlying the
estimator is derived here and developed into a practical
algorithm applicable to both real and complex matrices. The
algorithm works with $n\times t$ matrices, where $t$ is a
parameter. For $t=1$ the original algorithm is recovered, but
with two improvements (one for real matrices and one for complex
matrices). The accuracy and reliability of the estimates
generally increases with $t$ and the computational kernels are
level~3 BLAS operations for $t>1$. The last $t-1$ columns of the
starting matrix are randomly chosen, giving the algorithm a
statistical flavour. As a by-product of our investigations we
identify a matrix for which the 1-norm power method takes the
maximum number of iterations. As an application of the new
estimator we show how it can be used to efficiently approximate
1-norm pseudospectra.",
keywords = "matrix 1-norm, matrix norm estimation, matrix condition number,
condition number estimation, $p$-norm power method, 1-norm
pseudospectrum, LAPACK, level 3 BLAS"
}
@techreport{Ford:1999:NHBClass,
author = "Neville J. Ford and Volker Wulf",
title = "Numerical {Hopf} Bifurcation for a Class of
Delay Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 340",
pages = "17",
month = feb,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep340.ps.gz",
abstract = "In this report we consider discretisation of parameter-dependent
delay differential equations. We show that, if the delay
differential equation undergoes a Hopf bifurcation, then the
discrete scheme undergoes a Hopf bifurcation of the same type.
The results of this report extend our previous results for the
delay logistic equation to a wider class of problems.",
keywords = "Delay differential equations, Hopf bifurcation, numerical methods,
stability coefficient"
}
@techreport{Higham:99:SQM,
author = "Nicholas J. Higham and Hyun-Min Kim",
title = "Solving a Quadratic Matrix Equation by
{Newton's} Method with Exact Line Searches",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 339",
month = jan,
pages = 18,
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep339.pdf",
abstract = "We show how to incorporate exact line searches into Newton's
method for solving the quadratic matrix equation $AX^2 + BX + C =
0$, where $A$, $B$ and $C$ are square matrices. The line searches
are relatively inexpensive and improve the global convergence
properties of Newton's method in theory and in practice. We also
derive a condition number for the problem and show how to compute
the backward error of an approximate solution.",
keywords = "quadratic matrix equation, solvent, Newton's method, generalized
Sylvester equation, exact line searches, quadratic eigenvalue
problem, condition number, backward error"
}
@techreport{Davies:99:GTM,
author = "Philip I. Davies and Nicholas J. Higham",
title = "Generating Test Matrices for the One- and Two-Sided {Jacobi} Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 338",
month = jan,
pages = "13",
year = 1999,
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep338.ps.gz",
abstract = "For a symmetric positive definite matrix the relative error in
the eigenvalues computed by the two-sided Jacobi method is
bounded in terms of the condition number of the matrix scaled to
have unit diagonal. Similarly, for a general matrix the relative
error in the singular values computed by the one-sided Jacobi
method is bounded in terms of the condition number of the matrix
scaled to have rows or columns of unit-2 norm. We show how to
generate random matrices having these scalings and given
eigenvalues and singular values, respectively. For the two-sided
Jacobi method we apply an algorithm of Bendel and Mickey for
generating random correlation matrices, with an improved formula
for the rotations. We show how to modify the algorithm to
generate matrices for the one-sided Jacobi method. Using these
test matrices we show empirically that the forward error bounds
for the one- and two-sided Jacobi methods are sharp.",
keywords = "Jacobi method, correlation matrix, eigenvalues, singular value
decomposition, test matrices, forward error bounds, relative
error bounds"
}
@techreport{Paul:99:TDDDE,
author = "Christopher A.H. Paul",
title = "The Treatment of Derivative Discontinuities in Differential
Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 337",
month = jan,
pages = 11,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep337.ps.gz",
abstract = "The assumption of sufficiently smooth derivatives underlies much
of the analysis of numerical methods for both ordinary and delay
differential equations. However, derivative discontinuities can
arise in ordinary differential equations and usually do arise in
delay differential equations. In this paper, I review two of the
approaches for treating derivative discontinuities, ``tracking''
using the discontinuity tracking equations and ``detection and
location'' using defect error control. I conclude that neither
approach is ideal when it comes to the treatment of derivative
discontinuities in delay differential algebraic equations.",
keywords = "differential equations, discontinuities, numerical solution"
}
@techreport{Higham:99:NSM,
author = "Nicholas J. Higham",
title = "A New \texttt{sqrtm} for \textsc{Matlab}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 336",
month = jan,
pages = 11,
year = "1999",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep336.ps.gz",
abstract = "\Matlab's function \t{sqrtm} computes a square root of a matrix.
We propose a replacement for the \t{sqrtm} in \Matlab~5.2 that is
more accurate and returns useful information about the stability
and conditioning of the problem.",
keywords = "matrix square root, \Matlab, Schur decomposition, condition
number, stability"
}
@techreport{Tshelametse:98:ANT,
author = "Ronald Tshelametse and Jack Williams",
title = "A New Termination Criterion for Nonlinear Iterations in {ODE} Codes",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 334",
month = oct,
pages = 23,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep334.ps.gz",
abstract = "Many codes that solve systems of stiff initial value problems for
ordinary differential equations implement implicit linear
multistep methods. This yields nonlinear equations which are
commonly solved using some form of Newton iteration. For linear
multistep methods we apply the theory of Dorsselaer and Spijker
\cite{dorss94} to justify a new stopping criterion for the Newton
iteration. The ideas are tested on the \textsc{Matlab} ODE suite
of Shampine and Reichelt \cite{shamp97} and are shown to lead to
a significant improvement in overall efficiency for some
problems.",
keywords = "stiff problems, IVPs, ODEs, BDFs, Newton method"
}
@techreport{Higham:98:NAS,
author = "Nicholas J. Higham",
title = "Notes on Accuracy and Stability of Algorithms in
Numerical Linear Algebra",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 333",
month = aug,
pages = 42,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep333.ps.gz",
note = "To appear in proceedings of EPSRC Numerical Analysis Summer School,
Leicester University, July 1998."
}
@techreport{Tisseur:1998:BEC,
author = "Fran\c{c}oise Tisseur",
title = "Backward Error and Condition of Polynomial Eigenvalue Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 332",
pages = "20",
month = aug,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep332.ps.gz",
abstract = "We develop normwise backward errors and condition
numbers for the polynomial eigenvalue problem (PEP).
The standard way of dealing
with the PEP is to reformulate it as a generalized
eigenvalue problem (GEP). For
the special case of the quadratic eigenvalue problem (QEP), we
show that solving the QEP by applying the QZ algorithm to a
corresponding GEP can be backward unstable. The QEP can
be reformulated as a GEP in many ways. We investigate
the sensitivity of a given eigenvalue to perturbations
in each ofthe GEP formulations and identify which
formulations are to be preferred for large and small
eigenvalues respectively.",
keywords = "Polynomial eigenvalue problem,
quadratic eigenvalue problem, generalized eigenvalue
problem, backward error, condition number"
}
@techreport{Barlow:1998:MAB,
author = "Jesse L. Barlow",
title = "More Accurate Bidiagonal Reduction for Computing the Singular Value
Decomposition",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 331",
month = aug,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep331.ps.gz",
abstract = "Bidiagonal reduction is the preliminary stage for the fastest
stable algorithms for computing the singular value decomposition.
However, the best error bounds on bidiagonal reduction methods
are of the form \[ A + \delta A = UBV^T , \] \[ \normtwo{\delta A
} \leq \macheps f(n) \normtwo{A} \] where $B$ is bidiagonal, $U$
and $V$ are orthogonal, $\macheps$ is machine precision, and
$f(n)$ is a modestly growing function of the dimensions of $A$.
A Givens-based bidiagonal reduction procedure is proposed that satisfies
\[
A + \delta A = U (B + \delta B ) V^T,
\]
where $\delta B$ is bounded {\em componentwise} and $\delta A$
satisfies a tighter columnwise bound. Thus the routine obtains
more accurate singular values for matrices that have poor column
scaling or those arising from rank revealing decompositions.",
keywords = ""
}
@techreport{Cheng:1998:NDP,
author = "Sheung Hun Cheng and Nicholas J. Higham",
title = "The Nearest Definite Pair for the
{Hermitian} Generalized Eigenvalue Problem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 325",
pages = "15",
month = may,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep325.ps.gz",
abstract = "The generalized eigenvalue problem $Ax = \lambda Bx$ has special
properties when $(A,B)$ is a Hermitian and definite pair. Given a
general Hermitian pair $(A,B)$ it is of interest to find the
nearest definite pair having a specified Crawford number $\delta
> 0$. We solve the problem in terms of the inner numerical radius
associated with the field of values of $A+iB$. We show that once
the problem has been solved it is trivial to rotate the perturbed
pair $(A+\dA,B+\dB)$ to a pair $(\widetilde{A},\widetilde{B})$
for which $\lambda_{\min}(\widetilde{B})$ achieves its maximum
value $\delta$, which is a numerically desirable property when
solving the eigenvalue problem by methods that convert to a
standard eigenvalue problem by ``inverting $B$''. Numerical
examples are given to illustrate the analysis.",
keywords = "Nearest definite pair, Crawford number, Hermitian pair,
generalized eigenvalue problem, field of values, inner numerical
radius, numerical radius"
}
@techreport{Higham:1998:QRF,
author = "Nicholas J. Higham",
title = "{QR} Factorization with Complete Pivoting
and Accurate Computation of the {SVD}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 324",
month = sep,
pages = 26,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep324.ps.gz",
abstract = "A new algorithm of Demmel et al.\ for computing the singular
value decomposition (SVD) to high relative accuracy begins by
computing a rank-revealing decomposition. Demmel et al.\ analyse
the use of Gaussian elimination with complete pivoting (GECP) for
computing the rank-revealing decomposition. We investigate the
use of QR factorization with complete pivoting (that is, column
pivoting together with row sorting or row pivoting) as an
alternative to GECP, since this leads to a faster SVD algorithm.
We derive a new componentwise backward error result for
Householder QR factorization and combine it with the theory of
Demmel et al.\ to show when high relative accuracy in the
computed SVD can be expected. An a posteriori error bound is
derived that gives useful estimates of the relative accuracy of
the computed singular values. Numerical experiments confirm the
theoretical predictions.",
keywords = "QR factorization, Householder matrix, row pivoting, row sorting,
column pivoting, complete pivoting, backward error analysis,
singular value decomposition, relative accuracy"
}
@techreport{Ford:1998:NHB,
author = "Neville J. Ford and Volker Wulf",
title = "Numerical {Hopf} Bifurcation for the Delay Logistic Equation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 323",
pages = "20",
month = apr,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep323.ps.gz",
abstract = "This report is concerned with the approximate solution of the
delay logistic equation close to the Hopf bifurcation point. We
show that, for sufficiently small step sizes the bifurcation
point of the original problem is approximated by a bifurcation
point in the discrete problem and that furthermore, the nature of
the bifurcation is preserved.",
keywords = "Delay differential equations, Hopf bifurcation, numerical
methods, stability coefficient"
}
@techreport{Ford:1998:BLP,
author = "Neville J. Ford and Volker Wulf",
title = "The Use of Boundary Locus Plots in the Identification of Bifurcation
Points in Numerical Approximation of Delay Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 322",
pages = "15",
month = mar,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep322.ps.gz",
abstract = "We use the boundary locus method as a tool to determine precise
parameter values at which discrete analogues of delay
differential equations may have a Hopf bifurcation. We prove that,
for strictly stable multistep methods, the boundary of the
stability region for the discrete equation approximates the true
stability region to the order of the method and that Hopf
bifurcation points in the discrete scheme approximate the
bifurcation points for the original equation to the same order.",
keywords = "Delay differential equations, Hopf bifurcations,
Boundary locus method"
}
@techreport{Cox:1998:BEB,
author = "Anthony J. Cox and Nicholas J. Higham",
title = "Backward Error Bounds for Constrained Least Squares Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 321",
pages = "20",
month = apr,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep321.ps.gz",
abstract = "We derive an upper bound on the normwise backward error of an
approximate solution to the equality constrained least squares
problem $\min_{Bx=d}\|b-Ax\|_2$. Instead of minimizing over the
four perturbations to $A$, $b$, $B$ and $d$, we fix those to $B$
and $d$ and minimize over the remaining two; we obtain an
explicit solution of this simplified minimization problem. Our
experiments show that backward error bounds of practical use are
obtained when $B$ and $d$ are chosen as the optimal normwise
relative backward perturbations to the constraint system, and we
find that when the bounds are weak they can be improved by direct
search optimization. We also derive upper and lower backward
error bounds for the problem of least squares minimization over a
sphere: $\min_{\|x\|_2\le\alpha}\|b-Ax\|_2$.",
keywords = "Equality constrained least squares problem, least squares
minimization over a sphere, null space method, elimination
method, method of weighting, backward error, backward stability"
}
@techreport{MCCM:1998:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1997",
type = "Numerical Analysis Report",
number = "No. 320",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "20",
month = mar,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep320.ps.gz",
}
@techreport{Cox:1998:RWB,
author = "Anthony J. Cox and Nicholas J. Higham",
title = "Row-Wise Backward Stable Elimination Methods
for the Equality Constrained Least Squares Problem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 319",
pages = "18",
month = mar,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep319.ps.gz",
abstract = " It is well known that the solution of the equality constrained
least squares (LSE) problem $\min_{Bx=d}\|b-Ax\|_2$ is the limit
of the solution of the unconstrained weighted least squares
problem $$ \min_x\left\| \bmatrix{ \mu d \cr b } - \bmatrix{\mu
B \cr A } x \right\|_2 $$ as the weight $\mu$ tends to infinity,
assuming that $\bmatrix{B^T & A^T \cr}^T$ has full rank. We
derive a new method for the LSE problem by applying Householder
QR factorization with column pivoting to this weighted problem
and taking the limit analytically, with an appropriate rescaling
of rows. The method obtained is a type of direct elimination
method. We adapt existing error analysis for the unconstrained
problem to obtain a row-wise backward error bound for the
method. The bound shows that, provided row pivoting or row
sorting is used, the method is well-suited to problems in which
the rows of $A$ and $B$ vary widely in norm. As a by-product of
our analysis, we show that the standard elimination method for
solving the LSE problem satisfies a row-wise backward error
bound of precisely the same form as the new method. We
illustrate our results with numerical tests.",
keywords = "Constrained least squares problem, weighted least squares
problem, Householder QR factorization, Gaussian elimination,
elimination method, rounding error analysis, backward stability,
row pivoting, row sorting, column pivoting"
}
@techreport{Tisseur:1998:PDC,
author = "Fran\c{c}oise Tisseur and Jack J. Dongarra",
title = "Parallelizing the Divide and Conquer Algorithm for
the Symmetric Tridiagonal Eigenvalue Problem on
Distributed Memory Architectures",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 317",
pages = "28",
month = mar,
year = "1998",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep317.ps.gz",
abstract = "We present a new parallel implementation of a divide and
conquer algorithm for computing the spectral
decomposition of a symmetric tridiagonal matrix on
distributed memory architectures. The implementation we
develop differs from other implementations in that we use a two
dimensional block cyclic distribution of the data, we
use the L{\"o}wner theorem approach to compute orthogonal
eigenvectors, and we introduce permutations before the
back transformation of each rank-one update in order to
make good use of deflation. This algorithm yields the
first scalable, portable and numerically stable parallel
divide and conquer eigensolver. Numerical results
confirm the effectiveness of our algorithm. We compare
performance of the algorithm with that of the QR
algorithm and of bisection followed by inverse iteration
on an IBM SP2 and a cluster of Pentium PII's.",
keywords = "Divide and conquer, symmetric eigenvalue problem,
tridiagonal matrix, rank-one modification, parallel algorithm,
ScaLAPACK, LAPACK, distributed memory architecture"
}
@techreport{kay:97:APE,
author = "David Kay and David Silvester",
title = "A-Posteriori Error Estimation for Stabilised Mixed Approximations of
the {Stokes} Equations.",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 316",
month = dec,
year = 1997,
note = "Submitted to the SIAM Journal on Scientifc Computing",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep316.ps.gz",
abstract = "The practical implementation of the lowest-order \plpo\ (linear
velocity, constant pressure) finite element method for the
steady-state incompressible (Navier-)Stokes equations is
addressed in this work. Three different types of a-posteriori
error indicator are introduced and each is shown to be equivalent
to the discretisation error. Our numerical results show that
these indicators can be used to drive an adaptive refinement
process which is specially tailored to create grids which
conform to the requirements of the local stabilisation. It is
also shown that the indicators provide an effective method for
detecting local singularities in the flow solution."
}
@techreport{Baker:1997:MMI2,
author = "Christopher T. H. Baker and Gennadii A. Bocharov and
Christopher A. H. Paul",
title = "Mathematical Modelling Of The Interleukin-2 T-Cell System: A
Comparative Study Of Approaches Based On Ordinary And Delay
Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 314",
pages = "17",
month = nov,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep314.ps.gz",
abstract = "Cell proliferation and differentiation phenomena are key issues
in immunology, tumour growth and cell biology. We study the
kinetics of cell growth in the immune system using mathematical
models formulated in terms of ordinary and delay differential
equations. We study how the suitability of the mathematical
models depends on the nature of the cell growth data and the
types of differential equations by minimizing an objective
function to give a best-fit parameterized solution. We show that
mathematical models that incorporate a time-lag in the cell
division phase are more consistent with certain reported data.
They also allow various cell proliferation characteristics to be
estimated directly, such as the average cell-doubling time and
the rate of commitment of cells to cell division. Specifically,
we study the Interleukin-2-dependent cell division of
phytohemagglutinin stimulated T-cells -- the model of which can
be considered to be a general model of cell growth. We also
review the numerical techniques available for solving delay
differential equations and calculating the least-squares
best-fit parameterized solution.",
keywords = "Cell proliferation, Interleukin-2, mathematical modelling,
parameter estimation, time-lag"
}
@techreport{Baker:1997:MATL,
author = "Christopher T. H. Baker and Gennadii A. Bocharova and
Christopher A. H. Paul and Fathalla A. Rihan",
title = "Modelling and Analysis of Time-Lags in Cell Proliferation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 313",
pages = "16",
month = nov,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep313.ps.gz",
abstract = "In this paper, we present a systematic approach for obtaining
qualitatively and quantitatively correct mathematical models of
some biological phenomena with time-lags. Features of our
approach are the development of a hierarchy of related models
and the estimation of parameter values, along with their
non-linear biases and standard deviations, for sets of
experimental data.
We demonstrate our method of solving parameter estimation
problems for neutral delay differential equations by analyzing
some models of cell growth that incorporate a time-lag in the
cell division phase. We show that these models are more
consistent with certain reported data than the classic
exponential growth model. Although the exponential growth model
provides estimates of some of the growth characteristics, such
as the population-doubling time, the time-lag growth models can
additionally provide estimates of: (i) the fraction of cells
that are dividing, (ii) the rate of commitment of cells to cell
division, (iii) the initial distribution of cells in the cell
cycle, and (iv) the degree of synchronization of cells in the
(initial) cell population.",
keywords = "Cell proliferation, mathematical modelling, time-lag, neutral
delay differential equation"
}
@techreport{Ford:1997:SDA,
author = "Neville J. Ford and John T. Edwards and Jason A. Roberts and
Leonid E. Shaikhet",
title = "Stability of a difference analogue for a nonlinear
integro differential equation of convolution type",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 312",
pages = "15",
month = oct,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep312.ps.gz",
abstract = "This paper is concerned with the stability of discrete
analogues of nonlinear integro-differential equations.
We apply the general method of Lyapunov functional
construction to give sufficient conditions for
the asymptotic stability of the zero solution",
keywords = "Integro-differential equations, numerical stability,
Lyapunov stability"
}
@techreport{Ford:1997:NVI,
author = "Neville J. Ford and Christopher T. H. Baker and Jason A. Roberts",
title = "Nonlinear {Volterra} integro-differential equations -
stability and numerical stability of theta methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 311",
pages = "15",
month = oct,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep311.ps.gz",
abstract = "This paper considers whether existing stability results
for a non-linear integro-differential equation are
preserved when a solution is found using numerical
approximations. We choose to analyse theta quadrature methods
and we apply the direct method of Lyapunov for the stability analysis",
keywords = "Integro-differential equations, numerical stability, Lyapunov stability"
}
@techreport{Ford:1997:QBA,
author = "Neville J. Ford and John T. Edwards and Kurt Frischmuth",
title = "Qualitative behaviour of approximate solutions of some {Volterra}
integral equations with non-{Lipschitz} nonlinearity",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 310",
pages = "17",
month = oct,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep310.ps.gz",
abstract = "In some recent work the long-term behaviour of numerical
solutions of the nonlinear convolution equation has been
considered. In the present paper, we consider examples
which do not satisfy classical conditions guaranteeing
existence and uniqueness of the exact solutions and
suitable behaviour of approximate solutions. We are able
to give a strengthened version of a theorem given
originally by Corduneanu for certain kernels and
nonlinearities. On that basis we consider how
certain numerical codes may fail. We explore and test methods
known to preserve properties of the solutions in the linear
case",
keywords = "Volterra integral equations, non-Lipschitz kernel, numerical
methods"
}
@techreport{Ford:1997:ADM,
author = "John T. Edwards and Jason A. Roberts and Neville J. Ford",
title = "A comparison of {Adomian's} decomposition method and {Runge Kutta}
methods for approximate solution of some predator prey
model equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 309",
pages = "17",
month = oct,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep309.ps.gz",
abstract = "Adomian's decomposition method (ADM) has been presented
for example, by Bellman in 1986 as a significant powerful method
for solving systems of nonlinear equations. A recent paper by
Olek indicates that ADM is a powerful tool in the solution
of some predator prey model equations and that it compares
favourably with alternative approximate methods (both
analytical and numerical). In this report we investigate
whether this property holds more generally",
keywords = "Adomian's Decomposition Method, Predator Prey equations"
}
@techreport{Higham:1997:SBF,
author = "Nicholas J. Higham",
title = "Stability of Block $\mathrm{LDL^T}$ Factorization of a
Symmetric Tridiagonal Matrix",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 308",
month = sep,
pages = "8",
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep308.ps.gz",
abstract = "For symmetric indefinite tridiagonal matrices, block
$\mathrm{LDL^T}$ factorization without interchanges is shown to
have excellent numerical stability when a pivoting strategy of
Bunch is used to choose the dimension (1 or 2) of the pivots.",
keywords = "tridiagonal matrix, symmetric indefinite matrix, diagonal
pivoting method, $\mathrm{LDL^T}$ factorization, growth factor,
numerical stability, rounding error analysis, LAPACK,
LINPACK."
}
@techreport{Norburn:1997:SSM,
author = "Sean Norburn and David Silvester",
title = "Stabilised Vs Stable Mixed Methods for Incompressible Flow",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 307",
month = sep,
year = "1997",
note = "Submitted to Computer Methods in Applied Mechanics and Engineering",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep307.ps.gz",
abstract = "The accuracy of low-order mixed finite element methods for the
incompressible (Navier-)Stokes equations is investigated in this
work. Some numerical experiments suggest that the lowest-order
stabilised $P_1$--$P_0$ method (linear velocity, constant
pressure) is more efficient than the alternative a-priori stable
non-conforming Crouzeix-Raviart ($P_{-1}$--$P_0$) approach. The
relative accuracy of stabilised $P_1$--$P_0$ and $P_1$--$P_1$
(linear velocity, continuous linear pressure) is also assessed
herein."
}
@techreport{Cox:1997:ASN,
author = "Anthony J. Cox and Nicholas J. Higham",
title = "Accuracy and Stability of the Null Space Method for Solving the
Equality Constrained Least Squares Problem",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 306",
pages = "20",
month = aug,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep306.ps.gz",
abstract = "The null space method is a standard method for solving the linear
least squares problem subject to equality constraints (the LSE
problem). We show that three variants of the method, including
one used in LAPACK that is based on the generalized QR
factorization, are numerically stable. We derive two perturbation
bounds for the LSE problem: one of standard form that is not
attainable, and a bound that yields the condition number of the
LSE problem to within a small constant factor. By combining the
backward error analysis and perturbation bounds we derive an
approximate forward error bound suitable for practical
computation. Numerical experiments are given to illustrate the
sharpness of this bound.",
keywords = "Constrained least squares problem, null space method,
rounding error analysis, condition number,
generalized QR factorization, LAPACK"
}
@techreport{Higham:1997:SIM,
author = "Nicholas J. Higham",
title = "Stable Iterations for the Matrix Square Root",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 305",
month = apr,
pages = "20",
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep305.pdf",
abstract = "Any matrix with no nonpositive real eigenvalues has a unique
square root for which every eigenvalue lies in the open right
half-plane. A link between the matrix sign function and this
square root is exploited to derive both old and new iterations
for the square root from iterations for the sign function. One
new iteration is a quadratically convergent Schulz iteration
based entirely on matrix multiplication; it converges only
locally, but can be used to compute the square root of any
nonsingular $M$-matrix. A new Pad\'e iteration well suited to
parallel implementation is also derived and its properties
explained. Iterative methods for the matrix square root are
notorious for suffering from numerical instability. It is shown
that apparently innocuous algorithmic modifications to the Pad\'e
iteration can lead to instability, and a perturbation analysis is
given to provide some explanation. Numerical experiments are
included and some advice is offered on the choice of iterative
method for computing the matrix square root.",
keywords = "Matrix square root, matrix logarithm, matrix sign function,
$M$-matrix, symmetric positive definite matrix, Pad\'e
approximation, numerical stability, Newton's method, Schulz
method"
}
@techreport{MCCM:1997:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1996",
type = "Numerical Analysis Report",
number = "No. 304",
institution = inst-MCCM,
address = inst-MCCM:adr,
pages = "16",
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep304.ps.gz",
}
@techreport{Braconnier:1997:CBE,
author = "Thierry Braconnier and Fran\c{c}oise Chaitin-Chatelin",
title = "Chaotic Behavior for Eigensolvers Applied on
Highly Nonnormal Matrices in Finite Precision",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 303",
pages = "15",
month = may,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep303.ps.gz",
abstract = "In this paper, we provide examples of nonnormal matrices where
the power method is shown to be backward unstable. Investigating
the behavior of the computed sequence of Rayleigh quotients, we
show via two measures of chaos, i.e, the computation of the
Hausdorff dimension (more precisely of the correlation dimension)
and the computation of the Lyapunov exponent, that the computed
dominant eigenvalue lies on an attractor which has a dimension
larger than the dimension predicted by the theoretical analysis
and which increases with the nonnormality of the matrix.",
keywords = "Backward stability, Hausdorff dimension, correlation dimension,
Lyapunov exponents, eigenvalues, departure from normality."
}
@techreport{Williams:1997:LHC,
author = "Jack Williams and Z. Kalogiratou",
title = "The Local {Haar} Condition in Parameter
Estimation for Second Order Ordinary Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 302",
month = feb,
pages = "17",
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep302.ps.gz"
}
@techreport{Cox:1997:SHQ,
author = "Anthony J. Cox and Nicholas J. Higham",
title = "Stability of {Householder QR} Factorization
for Weighted Least Squares Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 301",
pages = "17",
month = feb,
year = "1997",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep301.ps.gz",
abstract = "For least squares problems in which the rows of the coefficient
matrix vary widely in norm, Householder QR factorization (without
pivoting) has unsatisfactory backward stability properties.
Powell and Reid showed in 1969 that the use of both row and
column pivoting leads to a desirable row-wise backward error
result. We give a reworked backward error analysis in modern
notation and prove two new results. First, sorting the rows by
decreasing $\infty$-norm at the start of the factorization
obviates the need for row pivoting. Second, row-wise backward
stability is obtained for only one of the two possible choices of
sign in the Householder vector.",
keywords = "Weighted least squares problem, Householder matrix, QR
factorization, row pivoting, column pivoting, backward error
analysis"
}
@techreport{Usman:1996:ESP,
author = "Anila Usman and George Hall",
title = "Equilibrium States for Predictor-Corrector Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 300",
month = dec,
pages = "35",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep300.ps.gz"
}
@techreport{Baker:1996:VCT,
author = "Christopher T. H. Baker and Arsalang Tang",
title = "Volterra Centennial Meetings---Invited talks at {Arlington and
Tempe}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 299",
month = nov,
pages = "28",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep299.ps.gz"
}
@techreport{Higham:1996:FCS,
author = "Nicholas J. Higham",
title = "Factorizing Complex Symmetric Matrices with
Positive Definite Real and Imaginary Parts",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 298",
month = nov,
pages = "12",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep298.ps.gz",
abstract = "Complex symmetric matrices whose real and imaginary parts are
positive definite are shown to have a growth factor bounded by 2
for LU factorization. This result adds to the classes of matrix
for which it is known to be safe not to pivot in LU
factorization. Block $\mathrm{LDL^T}$ \fact\ with the pivoting
strategy of Bunch and Kaufman is also considered, and it is shown
that for such matrices only $1\times 1$ pivots are used and the
same growth factor bound of 2 holds, but that interchanges that
destroy band structure may be made. The latter results hold
whether the pivoting strategy uses the usual absolute value or
the modification employed in LINPACK and LAPACK.",
keywords = "Complex symmetric matrices, LU factorization, diagonal pivoting
factorization, block $\mathrm{LDL^T}$ factorization,
Bunch--Kaufman pivoting strategy, growth factor, band matrix,
LINPACK, LAPACK"
}
@techreport{Higham:1996:SBE,
author = "Desmond J. Higham and Nicholas J. Higham",
title = "Structured Backward Error and Condition of
Generalized Eigenvalue Problems",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 297",
month = nov,
pages = "24",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep297.pdf",
abstract = "Backward errors and condition numbers are defined and evaluated
for eigenvalues and eigenvectors of generalized eigenvalue
problems. Both normwise and componentwise measures are used.
Unstructured problems are considered first, and then the basic
definitions are extended so that linear structure in the
coefficient matrices (for example, Hermitian, Toeplitz or band
structure) is preserved by the perturbations.",
keywords = "Generalized eigenvalue problem, backward error, condition number,
structured matrices"
}
@techreport{Barlow:1996:GGE,
author = "Jesse L. Barlow and Hongyuan Zha",
title = "Growth in {Gaussian} Elimination, Orthogonal Matrices, and the
{Euclidean} Norm",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 296",
month = sep,
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep296.ps.gz",
abstract = "It is shown that maximal growth for Gaussian elimination as
measured in the Euclidean norm is achieved by orthogonal
matrices. A new, sharp bound on that growth is given.",
keywords = "LU factorization, orthogonal invariance, triangular matrix"
}
@techreport{Higham:1996:MIM,
author = "Nicholas J. Higham and Sheung Hun Cheng",
title = "Modifying the Inertia of Matrices Arising in Optimization",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 295",
month = sep,
pages = "17",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep295.ps.gz",
abstract = "Applications in constrained optimization (and other areas)
produce symmetric matrices with a natural block $2\times 2$
structure. An optimality condition leads to the problem of
perturbing the $(1,1)$ block of the matrix to achieve a specific
inertia. We derive a perturbation of minimal norm, for any
unitarily invariant norm, that increases the number of
nonnegative eigenvalues by a given amount, and we show how it can
be computed efficiently given a factorization of the original
matrix. We also consider an alternative way to satisfy the
optimality condition based on a projection approach. Theoretical
tools developed here include an extension of Ostrowski's theorem
on congruences and some lemmas on inertias of block $2\times 2$
symmetric matrices.",
keywords = "Inertia, optimization, nonlinear programming, unitarily
invariant norm"
}
@techreport{Higham:1996:TLA,
author = "Nicholas J. Higham",
title = "Testing Linear Algebra Software",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 294",
month = aug,
pages = "14",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep294.ps.gz",
abstract = "How can we test the correctness of a computer implementation of
an algorithm such as Gaussian elimination, or the QR algorithm
for the eigenproblem? This is an important question for program
libraries such as LAPACK, that are designed to run on a wide
range of systems. We discuss testing based on verifying known
backward or forward error properties of the algorithms, with
particular reference to the test software in LAPACK. Issues
considered include the choice of bound to verify, computation of
the backward error, and choice of test matrices. Some examples of
bugs in widely used linear algebra software are described.",
keywords = "Mathematical software, testing, linear algebra, backward error,
LAPACK.",
note = "To appear in
{\em The Quality Of Numerical Software: Assessment and Enhancement},
Ronald F. Boisvert, editor,
Chapman and Hall, 1997, ISBN 0-412-80530-8"
}
@techreport{Braconnier:1996:FAF,
author = "Thierry Braconnier",
title = "Fvpspack: {A Fortran} and {PVM} Package to Compute the Field of
Values and Pseudospectra of Large Matrices",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 293",
month = aug,
year = "1996",
pages = "34",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep293.ps.gz",
abstract = "The field of values and pseudospectra are tools which yield
insight into the spectral behavior of a matrix. For large sparse
matrices, both sets can be efficiently computed using a Lanczos
type method. Since both computations can be done in a natural
parallel way, we have developed a package including Fortran and
PVM routines. Experiments show that the PVM codes achieve
excellent speed-ups and efficiency.",
keywords = "Field of values, pseudospectra, PVM, parallel algorithm,
speed-up."
}
@techreport{Baker:1996:NAV,
author = "Christopher T. H. Baker",
title = "Numerical Analysis of {Volterra} Functional and Integral
Equations---{State} of the Art",
type = "Numerical Analysis Report",
number = "No. 292",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = sep,
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep292.ps.gz",
abstract = "Volterra equations are, broadly speaking, evolutionary
equations incorporating memory. We indicate where they arise
in practice, discuss their significant features (notably
smoothness properties of the solutions), describe numerical
methods for their approximate solution, and indicate the
mathematical foundations of numerical procedures.",
}
@techreport{Smith:1996:IAL,
author = "Antony Smith and David Silvester",
title = "Implicit Algorithms and their Linearisation for the
Transient Incompressible {Navier-Stokes} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 290",
month = oct,
year = "1996",
note = "Submitted to the IMA Journal of Numerical Analysis",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep290.ps.gz",
abstract = "The issue of appropriate time discretisation methods for the
unsteady incompressible Navier-Stokes equations is considered
from a practical perspective here. Conventional implicit
time-stepping algorithms are not feasible for long time
simulations since they inherit the quadratic nonlinearity of the
steady-state equations. As a result linearised versions of the
``pure'' algorithms are analysed herein. These have similar
stability properties and comparable accuracy to the underlying
nonlinear methods. "
}
@techreport{Cheng:1996:MCA,
author = "Sheung Hun Cheng and Nicholas J. Higham",
title = "A Modified {Cholesky} Algorithm Based on a Symmetric Indefinite
Factorization",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 289",
pages = "18",
month = apr,
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep289.pdf",
abstract = "Given a symmetric and not necessarily positive definite matrix
$A$, a modified Cholesky algorithm computes a Cholesky
factorization $P(A+E)P^T = R^T R$, where $P$ is a permutation
matrix and $E$ is a perturbation chosen to make $A+E$ positive
definite. The aims include producing a suitable small-normed $E$
and making $A+E$ reasonably well conditioned. Modified Cholesky
factorizations are widely used in optimization. We propose a new
modified Cholesky algorithm based on a symmetric indefinite
factorization computed using a new pivoting strategy of Ashcraft,
Grimes and Lewis. We analyze the effectiveness of the algorithm,
both in theory and practice, showing that the algorithm is
competitive with the existing algorithms of Gill, Murray and
Wright, and Schnabel and Eskow. Attractive features of the new
algorithm include easy-to-interpret inequalities that explain the
extent to which it satisfies its design goals, and the fact that
it can be implemented in terms of existing software.",
keywords = "Modified Cholesky factorization, optimization, Newton's method,
symmetric indefinite factorization"
}
@techreport{Higham:1996:RDN,
author = "Nicholas J. Higham",
title = "Recent Developments in Dense Numerical Linear Algebra",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 288",
pages = "26",
month = apr,
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep288.ps.gz",
abstract = "We survey recent developments in dense numerical linear algebra,
covering linear systems, least squares problems and
eigenproblems. Topics considered include the design and analysis
of block, partitioned and parallel algorithms, condition number
estimation, componentwise error analysis, and the computation of
practical error bounds. Frequent reference is made to LAPACK, the
state of the art package of Fortran software designed to solve
linear algebra problems efficiently and accurately on
high-performance computers.",
keywords = "Numerical linear algebra, linear system,
least squares problem, eigenvalue problem, LAPACK",
note = "Revised August 1996.
To appear in
{\em The State of the Art in Numerical Analysis},
I. S. Duff and G. A. Watson, editors,
Oxford University Press",
}
@techreport{Blank:1996:NTD,
author = "Luise Blank",
title = "Numerical Treatment of Differential Equations of Fractional Order",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 287",
pages = "18",
month = mar,
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep287.ps.gz",
abstract = "A brief introduction to derivatives of fractional order is given
and results on the qualitative behaviour of solutions of basic
linear differential equations of fractional order are cited.
The collocation approximation with polynomial splines is applied
to differential equations of fractional order and the systems of
equations characterizing the numerical solution are determined.
In particular, the weight matrices resulting from the fractional
derivative of the spline are deduced and decomposed for
numerical implementation. The main result of this paper is the
simplification of the numerical method under a specific
smoothness condition on the chosen splines. Numerical results
conclude the work and show that the expected qualitative
behaviour is given by collocation approximation.",
keywords = "Differential equations, fractional order, numerical treatment"
}
@techreport{MCCM:1996:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1995",
type = "Numerical Analysis Report",
number = "No. 286",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
pages = "18",
year = "1996",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep286.ps.gz",
}
@techreport{Ford:1995:PTV,
author = "Neville J. Ford and Christopher T. H. Baker",
title = "Preserving transience in numerical solutions of {Volterra}
integral equations of convolution type",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 284",
pages = "13",
month = nov,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep284.ps.gz",
abstract = "We explore the property of transience in solutions of a nonlinear
integral equation of convolution type under discretisation. We
show that, under suitable conditions on the kernel function and
with the choice of a numerical method based on a positive
quadrature, transient solutions are approximated by transient
solutions. We show how the analysis can be extended to a wider
class of kernels",
keywords = "Volterra integral equations, numerical methods, transient solution, stability
analysis, positive quadrature"
}
@techreport{Paul:1995:UGA,
author = "Christopher A. H. Paul",
title = "A User-Guide to {Archi}---An Explicit {Runge-Kutta} Code for Solving
Delay and Neutral Differential Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 283",
pages = "20",
month = dec,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep283.ps.gz",
abstract = "Archi is based on the fifth-order Dormand and Prince explicit
Runge-Kutta method with a fifth-order Hermite interpolant due to
Shampine. The choice of a Hermite interpolant was influenced by:
1. The conclusion of Gladwell, Shampine, Baca and Brankin that
for non-monotonic solutions, quintic Hermite interpolants are
required in order to preserve the shape of a solution.
2. In order to maintain the asymptotic correctness of a $p$-th
order local error estimator, the local error in the approximation
scheme used to evaluate delay terms must be a least order $p+1$.
Archi has also been designed to track the propagation of
discontinuities in a solution using the discontinuity tracking
theory developed by Wille and Baker, and to solve vanishing-lag
DDEs using either extrapolation or the predictor-corrector
approach developed by Baker and Paul. In addition, Archi can
solve a limited class of delay-integro-differential equations,
specifically those equations that have a sufficiently smooth
integrand, using the adaptive quadrature algorithm developed
by Paul.",
keywords = "Delay differential equations, numerical solution, user-guide"
}
@techreport{Blank:1995:STR,
author = "Luise Blank",
title = "Stability-Type Results for Collocation Methods for {Volterra}
Integral Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 282",
pages = "19",
month = dec,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep282.ps.gz",
abstract = "Stability behaviour is investigated for polynomial spline
collocation applied to Volterra integral equations with special
emphasis on a weakly singular test equation. The characterization
of the corresponding stability domain is related to stability
results for solutions of finite recursion relations, as they
occur for methods applied to ordinary differential equations.
Estimates of the stability domains are established and, as a
consequence, conditions for $A(\pi/2)$-stability are obtained.
Exploiting these estimates, collocation approximations with
constant, linear, and continuous splines are considered in more
depth and several numerical illustrations are presented.",
keywords = "Stability, Volterra integral equation, weakly singular kernel,
collocation method"
}
@techreport{Braconnier:1995:IOB,
author = "Thierry Braconnier",
title = "Influence of Orthogonality on the Backward Error
and the Stopping Criterion for Krylov Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 281",
month = dec,
year = "1995",
pages = "30",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep281.ps.gz",
abstract = "Many algorithms for solving linear systems, least squares
problems or eigenproblems need to compute an orthonormal basis.
The computation is commonly performed using a QR factorization
computed using the classical or the modified Gram-Schmidt
algorithm, the Householder algorithm, the Givens algorithm or the
Gram-Schmidt algorithm with iterative reorthogonalization. For
linear systems, it is well-known that the backward stability of
the process depends crucially on the algorithm used for the QR
factorization. For the eigenproblem, although textbooks warn
users about the possible instability of eigensolvers due to loss
of orthogonality, few theoretical results exist. In this paper we
show that the loss of orthogonality of the computed basis can
affect the reliability of the computed eigenpair. We also show
that the classical residual norm $\norm{Ax-\lambda x}$ and the
specific computed one using a Krylov method can differ because of
the loss of orthogonality of the computed basis of the Krylov
subspace. We give a bound which quantifies the difference between
both residuals in terms of the loss of orthogonality.",
keywords = "QR factorization, backward error, eigenvalues, Krylov methods"
}
@techreport{Braconnier:1995:CFV,
author = "Thierry Braconnier and Nicholas J. Higham",
title = "Computing the Field of Values and Pseudospectra
Using the Lanczos Method with Continuation",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 279",
month = nov,
year = "1995",
pages = "20",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep279.ps.gz",
abstract = "The field of values and pseudospectra are useful tools for
understanding the behaviour of various matrix processes. To
compute these subsets of the complex plane it is necessary to
estimate one or two eigenvalues of a large number of parametrized
Hermitian matrices; these computations are prohibitively
expensive for large, possibly sparse, matrices, if done by use of
the QR algorithm. We describe an approach based on the Lanczos
method with selective reorthogonalization and Chebyshev
acceleration that, when combined with continuation and a shift
and invert technique, enables efficient and reliable computation
of the field of values and pseudospectra for large matrices. The
idea of using the Lanczos method with continuation to compute
pseudospectra is not new, but in experiments reported here our
algorithm is faster and more accurate than existing algorithms of
this type.",
keywords = "Field of values, pseudospectra, Lanczos method, Chebyshev
acceleration, continuation."
}
@techreport{Higham:1995:IRL,
author = "Nicholas J. Higham",
title = "Iterative Refinement and {LAPACK}",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 277",
month = sep,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep277.ps.gz",
abstract = "The technique of iterative refinement for improving the computed
solution to a linear system was used on desk calculators and
computers in the 1940s and has remained popular. In the 1990s
iterative refinement is well supported in software libraries,
notably in LAPACK. Although the behaviour of iterative refinement
in floating point arithmetic is reasonably well understood, the
existing theory is not sufficient to justify the use of fixed
precision iterative refinement in all the LAPACK routines in
which it is implemented. We present analysis that provides the
theoretical support needed for LAPACK. The analysis covers both
mixed and fixed precision iterative refinement with an arbitrary
number of iterations, makes only a general assumption on the
underlying solver, and is relatively short. We identify some
remaining open problems.",
keywords = "iterative refinement, rounding error analysis, backward error,
condition number, LAPACK"
}
@techreport{Higham:1995:TMT,
author = "Nicholas J. Higham",
title = "The {Test Matrix Toolbox} for \textsc{Matlab} (Version 3.0)",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 276",
month = sep,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep276.ps.gz",
abstract = "We describe version 3.0 of the Test Matrix Toolbox for
Matlab~4.2. The toolbox contains a collection of test matrices,
routines for visualizing matrices, routines for direct search
optimization, and miscellaneous routines that provide useful
additions to Matlab's existing set of functions. There are 58
parametrized test matrices, which are mostly square, dense,
nonrandom, and of arbitrary dimension. The test matrices include
ones with known inverses or known eigenvalues; ill-conditioned or
rank deficient matrices; and symmetric, positive definite,
orthogonal, defective, involutary, and totally positive matrices.
The visualization routines display surface plots of a matrix and
its (pseudo-) inverse, the field of values, Gershgorin disks, and
two- and three-dimensional views of pseudospectra. The direct
search optimization routines implement the alternating directions
method, the multidirectional search method and the Nelder--Mead
simplex method. We explain the need for collections of test
matrices and summarize the features of the collection in the
toolbox. We give examples of the use of the toolbox and explain
some of the interesting properties of the Frank matrix and magic
square matrices. The leading comment lines from all the toolbox
routines are listed.",
keywords = "test matrix, Matlab, pseudospectrum, visualization, Frank matrix,
magic square matrix, random matrix, direct search optimization"
}
@techreport{MCCM:1995:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report: {January--December} 1994",
type = "Numerical Analysis Report",
number = "No. 275",
institution = inst-MCCM,
address = inst-MCCM:adr,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep275.ps.gz",
}
@techreport{Kalogiratou:1995:BCA,
author = "Z. Kalogiratou and Jack Williams",
title = "Best {Chebyshev} Approximation by Families of {ODEs} with a
Fixed Initial Condition",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 274",
month = jul,
year = "1995",
ftpaddress = "ftp.ma.man.ac.uk",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep274.ps.gz",
abstract = "Best Chebyshev approximation of real-valued data is treated by
approximations obtained from solutions of parameter dependent
initial value problems in ordinary differential equations, in
which the initial conditions are specified. The problem is a
modified form of the problem treated by the authors in
\cite{JH1}, \cite{JH2}, and \cite{JH3}. The fixing of the initial
condition at $t=a$ requires that approximation be carried out on
a set which excludes this point. Numerical examples illustrating
the theory are presented."
}
@techreport{Silvester:1995:FRS,
author = "David Silvester and Andrew Wathen ",
title = "Fast and Robust Solvers for Time-Discretised
Incompressible {Navier-Stokes} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 273",
month = jul,
year = "1995",
note = "To appear in proceedings of the 16th Dundee Bienniel
Numerical Analysis Conference",
ftpaddress = "ftp.ma.man.ac.uk",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep273.ps.gz",
abstract = "We consider the design of robust and efficient methods for
solving the Navier-Stokes equations governing laminar flow of a
viscous incompressible fluid. Three fundamental issues will be
assessed: the discretisation of the convective transport terms,
the weak enforcement of the incompressibility constraint in a
mixed finite element setting, and the solution of the indefinite
(Stokes-like) systems arising at each time-level. Our aim is to
prescribe a framework for adaptive error control. The essential
ingredients are: an unconditionally stable time-discretisation;
``natural'' spatial discretisations which are (inf-sup) stable;
and a fast iterative solution strategy generating iterates
converging monotonically in an appropriate norm (which mimics the
dissipation inherent in the continuous system). A distinguishing
feature of our methodology is the use of multigrid
preconditioning to accelerate the convergence of our Krylov
subspace iterative solver. We motivate this with some analysis
showing that the contraction rate is bounded away from unity
independently of the choice of the mixed finite element method
and the subdivision parameter. Analysis and implementation of
``pure'' multigrid methods seems to be relatively complicated and
(discretisation-) method dependent by comparison. "
}
@techreport{Williams:1995:EUS,
author = "Jack Williams",
title = "Existence and Uniqueness of Solutions
of the Algebraic Equations in the {BDF} Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 272",
month = jul,
year = "1995",
ftpaddress = "ftp.ma.man.ac.uk",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep272.ps.gz",
abstract = "The paper presents a new result for the existence and uniqueness
of solutions of the system of nonlinear algebraic equations
obtained from the application of the BDF methods to stiff initial
value problems in ordinary differential equations. Expressed in
terms of the local truncation error, starting errors in the BDF
and contractivity properties of the differential equation, the
result is used to explain how with a certain form of local error
control existence and uniqueness is guaranteed. Although the form
of local error control is a theoretical procedure it relates well
to the error control procedures used in practical codes and
provides insight into how at a typical step the BDF yields
solution values. A potential difficulty in trying to compute low
accuracy numerical solutions is also identified."
}
@techreport{Baker:1995:BNS,
author = "C. T. H. Baker and C. A. H. Paul and D. R. Wille",
title = "A Bibliography on the Numerical Solution of Delay
Differential Equations",
type = "Numerical Analysis Report",
number = "No. 269",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep269.ps.gz",
abstract = "The aim of this bibliography is to provide an introduction
to papers and technical reports in the field of delay
differential equations and related differential equations.
In addition to the title, authors and reference of an
article, we provide the abstract which, if the article has
previously appeared as a technical report, comes from the
published paper unless indicated by a `+'. The main interest
in this bibliography derives from the references to early
papers and technical reports in the field, as nowadays
on-line search facilities (such as BIDS in the U.K.) provide
access to the most recent publications. Although it is hoped
to keep the bibliography up-to-date, most immediate effort
will be invested in extending the collection of earlier
references -- as it is far from being exhaustive. The
up-to-date bibliography is only available by anonymous ftp,
since it is hoped to update it regularly.",
keywords = "Delay differential equations, numerical solution,
stability, applications"
}
@techreport{Hall:1995:ESM,
author = "George Hall",
title = "Equilibrium States for Multistep Methods",
type = "Numerical Analysis Report",
number = "No. 268",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep268.ps.gz",
abstract = "When the stepsize in non-stiff ODE codes is restricted by
stability, an uneven pattern of stepsizes with many step
rejections is frequently observed. Results analysing this
behaviour have been obtained for Runge-Kutta methods, leading
to several papers attempting to improve stepsize control. It
is shown here that a similar analysis can be carried out for
multistep methods. The explicit Adams 2-step method is used
to illustrate the techniques required.",
keywords = "Multistep methods, stepsize selection, stability"
}
@techreport{Baker:1995:PPE,
author = "Christopher T. H. Baker and Christopher A. H. Paul",
title = "Pitfalls in Parameter Estimation for Delay Differential
Equations",
type = "Numerical Analysis Report",
number = "No. 267",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep267.ps.gz",
abstract = "Given a set of data
$\{U(\gamma_{i}) \approx u(\gamma_{i};p^{*})\}$
corresponding to the delay differential equation (DDE)
$u'(t;p) = f(t,u(t;p),u(\alpha(t;p);p);p)$ for
$t \ge t_{0}(p)$, the basic problem addressed here is that
of calculating the vector $p^{*}$. (We also consider neutral
differential equations.) Most approaches to parameter
estimation calculate $p^{*}$ by minimizing a suitable
objective function that is assumed to be sufficiently smooth.
In this paper, we use the derivative discontinuity tracking
theory for DDEs to analyze how jumps can arise in the
derivatives of a natural objective function. These jumps can
occur when estimating parameters in lag functions and
estimating the position of the initial point, and as such are
not expected to occur in parameter estimation problems for
ordinary differential equations.",
keywords = "Parameter estimation, delay differential equations,
derivative discontinuities"
}
@techreport{Baker:1995:SND,
author = "C. T. H. Baker and G. A. Bocharov and C. A. H. Paul and
A. A. Romanyukha",
title = "A Short Note on Delay Effects in Cell Proliferation",
type = "Numerical Analysis Report",
number = "266",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep266.ps.gz",
abstract = "We show that a growth model for cell proliferation that
incorporates a time-lag in the cell division phase is more
consistent with certain reported data than the classical
exponential growth model. Although both models provide
estimates of some of the growth characteristics, such as
the population doubling-time, the time-lag growth model
additionally provides estimates of: $(i)$ the cell-doubling
time, $(ii)$ the fraction of the cells that are dividing,
$(iii)$ the rate of commitment to cell division and, $(iv)$
the initial distribution of cells in the cell cycle.",
keywords = "Parameter estimation, delay differential equations,
mathematical modelling"
}
@techreport{Higham:1995:SDP,
author = "Nicholas J. Higham",
title = "Stability of the Diagonal Pivoting Method with Partial Pivoting",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 265",
month = jul,
year = "1995",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep265.ps.gz",
abstract = "LAPACK and LINPACK both solve symmetric indefinite linear systems
using the diagonal pivoting method with the partial pivoting
strategy of Bunch and Kaufman (1977). No proof of the stability
of this method has appeared in the literature. It is tempting to
argue that the diagonal pivoting method is stable for a given
pivoting strategy if the growth factor is small. We show that
this argument is false in general, and give a sufficient
condition for stability. This condition is not satisfied by the
partial pivoting strategy, because the multipliers are unbounded.
Nevertheless, using a more specific approach we are able to prove
the stability of partial pivoting, thereby filling a gap in the
body of theory supporting LAPACK and LINPACK.",
keywords = "symmetric indefinite matrix, diagonal pivoting method,
$\mathrm{LDL^T}$ factorization, partial pivoting, growth factor,
numerical stability, rounding error analysis, LAPACK, LINPACK."
}
@techreport{Elman:1995:FNI,
author = "Howard Elman and David Silvester",
title = "Fast Nonsymmetric Iterations and Preconditioning for
{Navier-Stokes} Equations",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 263",
month = jun,
year = "1995",
note = "To appear in SIAM Journal of Scientific Computing",
keywords = "Preconditioning, Krylov subspace iterations,
Navier-Stokes equations, convection-diffusion problems",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep263.ps.gz",
abstract = "Discretization and linearization of the steady-state
Navier-Stokes equations gives rise to a nonsymmetric indefinite
linear system of equations. In this paper, we introduce
preconditioning techniques for such systems with the property
that the eigenvalues of the preconditioned matrices are bounded
independently of the mesh size used in the discretization. We
confirm and supplement these analytic results with a series of
numerical experiments indicating that Krylov subspace iterative
methods for nonsymmetric systems display rates of convergence
that are independent of the mesh parameter. In addition, we show
that preconditioning costs can be kept small by using iterative
methods for some intermediate steps performed by the
preconditioner."
}
@techreport{Silvester:95:SMF,
author = "David Silvester",
title = "Stabilised Mixed Finite Element Methods",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 262",
month = aug,
year = "1995",
note = "To appear in Incompressible Flow and the Finite Element
Method, by P. M. Gresho",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep262.ps.gz",
abstract = "In this article we review a variety of techniques for stabilising
mixed finite element methods for solving incompressible flow
problems. Our emphasis is on low order finite element
approximations, typically based on piecewise linear velocity with
equal order or piecewise constant pressure. The optimal choice of
the stabilisation/regularisation parameter is discussed in
detail. "
}
@techreport{Ford:1994:QBS,
author = "Neville J. Ford and Christopher T. H. Baker",
title = "Qualitative behaviour and stability of solutions of discretised
non-linear {Volterra} integral equations of convolution type",
institution = inst-MCCM,
address = inst-MCCM:adr,
type = "Numerical Analysis Report",
number = "No. 261",
pages = "11",
month = aug,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep261.ps.gz",
abstract = "We provide a discrete analogue of a theorem given by Corduneanu
for a nonlinear Volterra equation of convolution type. We are
able to demonstrate the stability behaviour of some simple
quadrature rules applied to an example equation and show that the
qualitative behaviour of solutions is preserved under the
discretisation for certain families of quadrature rule",
keywords = "Volterra integral equations, numerical methods, stability analysis"
}
@techreport{Paul:1994:PPC,
author = "Christopher A. H. Paul",
title = "Performance and Properties of a Class of Parallel Continuous
Explicit Runge-Kutta Methods for Ordinary and Delay
Differential Equations equations",
type = "Numerical Analysis Report",
number = "No. 260",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep260.ps.gz",
abstract = "In this paper we examine the parallel implementation of the
iterated continuous extensions (ICEs) of Baker \& Paul. We
indicate how to construct arbitrarily high-order ICEs, and
discuss some of the strategies for choosing the `free'
parameters of the methods. The numerical results that we
present suggest that ICEs implemented in parallel provide an
easy and efficient way of writing dense-output ordinary
differential equation codes and delay differential equation
codes, even in the case that the lag vanishes and/or is
state-dependent.",
keywords = "Ordinary differential equations, delay differential
equations, parallel algorithms, numerical performance,
stability"
}
@techreport{Griffiths:1994:UME,
author = "D. F. Griffiths and D. J. Silvester",
title = "Unstable modes of the {$Q_1$--$P_0$} element",
type = "Numerical Analysis Report",
number = "No. 257",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = sep,
year = "1994",
note = "Submitted to SIAM J. Numer. Anal.",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep257.ps.gz",
abstract = "In this paper the unstable eigenmodes of $Q_1$--$P_0$
velocity/pressure finite element approximation for
incompressible flow problems are characterised. It is
shown that the inf-sup stability constant is $O(h)$ in
two dimensions and $O(h^2)$ in three dimensions. The
basic tool for our analysis is the method of modified
equations which is applied to finite difference
representations of the underlying finite element
equations. The asymptotic estimates are confirmed and
supplemented by numerical experiments.",
keywords = "mixed finite elements, inf-sup stability,
incompressible flow"
}
@techreport{Baxter:1994:NEI,
author = "B. J. C. Baxter and C. A. Micchelli",
title = "Norm Estimates for the {$l^2$}-Inverses of
Multivariate {Toeplitz} Matrices",
type = "Numerical Analysis Report",
number = "No. 255",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep255.ps.gz",
abstract = "We bound the $l^2$-norms of inverses of certain
Toeplitz matrices arising from P\'olya frequency
functions.",
keywords = "Radial basis functions, Toeplitz forms, Polya
frequency functions",
}
@techreport{Baxter:1994:RNR,
author = "B. J. C. Baxter and N. Sivakumar and J. D. Ward",
title = "Regarding the {$p$}-Norms of Radial Basis
Interpolation Matrices",
type = "Numerical Analysis Report",
number = "No. 254",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep254.ps.gz",
abstract = "Radial basis functions are linear combinations of
translates of a given radially symmetric function. In
this paper we provide some upper bounds on
$\|A^{-1}\|_p$ for $p \ge 1$, where $A = (\phi(x_j -
x_k))_{j,k=1}^n$ and $\phi$ is the radial basis
function. We also study some new applications of total
positivity in this context.",
keywords = "Radial basis functions, p-norms, total positivity",
}
@techreport{Wille:1994:ESC,
author = "David Richard Will\'e",
title = "Experiments in Stepsize Control for {Adams} Linear
Multistep Methods",
type = "Numerical Analysis Report",
number = "No. 253",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep253.ps.gz",
abstract = "In this paper we consider stepsize selection in one class
of Adams linear multistep methods for ordinary differential
equations. In particular, the exact form of the local error
for a variable step method is considered and a class of new
direct approximations proposed. The implications of this
approach are then discussed and illustrations provided with
numerical results. Intended applications include differential
equations with derivative discontinuities and initial
stepsize strategies.",
keywords = "Adams methods, linear multistep methods, error estimators,
stepsize control",
}
@techreport{Gladwell:1994:IPS,
author = "I. Gladwell and J. Wang and R. M. Thomas",
title = "Iterations and Predictors for Second Order Problems",
type = "Numerical Analysis Report",
number = "No. 252",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep252.ps.gz",
abstract = "This paper is concerned with the application of
implicit Runge-Kutta methods to initial value problems
consisting of second order ordinary differential
equations without first derivative terms. In
particular, we concentrate on implementing modified
Newton iterations and providing predictors for these
iterations.",
keywords = "Ordinary differential equations, initial value
problems, implicit Runge-Kutta methods, predictors,
iteration schemes",
}
@techreport{MCCM:1994:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report 1993",
type = "Numerical Analysis Report",
number = "No. 251",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep251.ps.gz",
}
@techreport{Thomas:1994:FNT,
author = "R. M. Thomas and T. E. Simos and G. V. Mitsou",
title = "A Family of {Numerov}-Type Exponentially Fitted
Predictor-Corrector Methods for the Numerical
Integration of the Radial {Schr{\"o}dinger} Equation",
type = "Numerical Analysis Report",
number = "No. 249",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep249.ps.gz",
abstract = "A family of predictor-corrector exponential
Numerov-type methods is developed for the numerical
integration of the one-dimensional Schr{\"o}dinger
equation. The formula considered contains certain free
parameters which allow it to be fitted automatically to
exponential functions. The new methods are very simple
and integrate more exponential functions than both the
well known fourth order Numerov type exponentially
fitted methods and the sixth algebraic order
Runge-Kutta type methods. Numerical results also
indicate that the new methods are much more accurate
than the other exponentially fitted methods mentioned
above.",
keywords = "Schr{\"o}dinger equation, predictor-corrector methods,
Numerov-type methods, exponentially-fitted methods,
resonance problem",
}
@techreport{Baker:1994:INS,
author = "Christopher T. H. Baker and Christopher A. H. Paul and
David R. Wille",
title = "Issues in the Numerical Solution of Evolutionary Delay
Differential Equations",
type = "Numerical Analysis Report",
number = "No. 248",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = apr,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep248.ps.gz",
abstract = "Delay differential equations are of sufficient
importance in modelling real-life phenomena to merit
the attention of numerical analysts. In this paper, we
discuss key features of delay differential equations
and consider the main issues to be addressed when
constructing robust numerical codes for their solution.
We provide an introduction to the existing literature,
and in particular we indicate the approaches adopted by
the authors at Manchester.",
keywords = "Numerical solution, delay differential equations",
}
@techreport{Wille:1994:NSE,
author = "David R. Wille",
title = "New Stepsize Estimators for Linear Multistep Methods",
type = "Numerical Analysis Report",
number = "No. 247",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep247.ps.gz",
abstract = "The selection of appropriate stepsizes for linear
multistep methods requires in general the solution, or
approximation, of a non-trivial polynomial root-finding
problem. Here we show how this can be reduced to the
integration of a simple ODE. Results are presented for
Adams-Bashforth-Moulton and backward differentiation
formulae using both `error-per-step' and
`error-per-unit-step' controls.",
keywords = "Linear multistep methods, error estimators, stepsize
control",
}
@techreport{Hanby:1994:CCS,
author = "R. F. Hanby and D. J. Silvester and J. W. Chew",
title = "A Comparison of Coupled and Segregated Iterative
Solution Techniques for Incompressible Swirling Flow",
type = "Numerical Analysis Report",
number = "No. 246",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep246.ps.gz",
abstract = "In many popular solution algorithms for the
incompressible Navier-Stokes equations the coupling
between the momentum equations is neglected when the
linearized momentum equations are solved to update the
velocities. This is known to lead to poor convergence
in highly swirling flows where coupling between the
radial and tangential momentum equations is strong.
Here we propose a coupled solution algorithm in which
the linearized momentum and continuity equations are
solved simultaneously. Comparisons between the new
method and the well-known SIMPLEC method are
presented.",
keywords = "Navier-Stokes equations; finite differences;
unsymmetric linear systems; Krylov subspace methods",
}
@techreport{Hall:1994:NSS,
author = "George Hall",
title = "A New Stepsize Strategy for {Runge-Kutta} codes",
type = "Numerical Analysis Report",
number = "No. 245",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep245.ps.gz",
abstract = "When the stepsize in Runge-Kutta codes is restricted
by stability, an uneven pattern of stepsizes with many
step rejections is frequently observed. A modified
strategy is proposed to smooth out this type of
behaviour. Several new estimates for the dominant
eigenvalue of the Jacobian are derived. It is shown
that such estimates can be used, in a strictly
controlled way, to improve the stepsize strategy. Some
numerical evidence is presented to show that the
modified strategy is effective on a set of widely used
test problems.",
keywords = "Runge-Kutta, stepsize selection, stability",
}
@techreport{Paul:1994:TSF,
author = "Christopher A. H. Paul",
title = "A Test Set of Functional Differential Equations",
type = "Numerical Analysis Report",
number = "No. 243",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = feb,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep243.ps.gz",
abstract = "This document is a collection of delay, neutral and
functional differential equations (mostly with
analytical solutions) taken from the mathematical
literature. Also included is the original source of the
equation, and other useful information. Further test
equations are welcomed, and will appear in the
anonymous ftp version of this document. The reference
solutions quoted were obtained using an explicit
fifth-order continuous Runge-Kutta method based on the
fifth-order Dormand and Prince method with a Hermite
interpolant.",
keywords = "Test set, functional differential equations",
}
@techreport{Papadimitriou:1993:KNA,
author = "Pythagoras Papadimitriou",
title = "The {KSR1}---{A} Numerical Analyst's Perspective",
type = "Numerical Analysis Report",
number = "No. 242",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = dec,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep242.ps.gz",
abstract = "The Kendall Square Research KSR1 is a virtual shared
memory MIMD computer. We give a description of the KSR1
aimed at a numerical analyst who wishes to use the KSR1
for research. The basic architecture of the KSR1 is
described. Parallel constructs and language extensions
provided in KSR Fortran are discussed, and numerical
software issues are also considered. We describe our
practical experiences in using the KSR1 and draw some
conclusions.",
keywords = "Kendall Square Research KSR1, Virtual shared memory,
ALLCACHE memory system, KSR Fortran, parallel
constructs, LAPACK, BLAS",
}
@techreport{Higham:1994:SCP,
author = "Nicholas J. Higham",
title = "A Survey of Componentwise Perturbation Theory in
Numerical Linear Algebra",
type = "Numerical Analysis Report",
number = "No. 241",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = feb,
year = "1994",
note = "In W.~Gautschi, editor, {\em {Mathematics of Computation}
1943--1993: {A} Half Century of Computational Mathematics},
volume~48 of {\em Proceedings of Symposia in Applied
Mathematics}, pages 49--77. American Mathematical Society,
Providence, RI, USA, 1994.",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep241.ps.gz",
abstract = "Perturbation bounds in numerical linear algebra are
traditionally derived and expressed using norms. Norm
bounds cannot reflect the scaling or sparsity of a
problem and its perturbation, and so can be unduly
weak. If the problem data and its perturbation are
measured componentwise, much smaller and more revealing
bounds can be obtained. A survey is given of
componentwise perturbation theory in numerical linear
algebra, covering linear systems, the matrix inverse,
matrix factorizations, the least squares problem, and
the eigenvalue and singular value problems. Most of the
results described have been published in the last five
years.",
keywords = "Componentwise perturbation bounds, componentwise
backward error, linear systems, matrix inverse, matrix
factorizations, least squares problem, underdetermined
system, eigenvalue problem, singular value problem",
}
@techreport{Higham:1993:PSV,
author = "Nicholas J. Higham and Pythagoras Papadimitriou",
title = "Parallel Singular Value Decomposition via the Polar
Decomposition",
type = "Numerical Analysis Report",
number = "No. 239",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep239.ps.gz",
abstract = "A new method is described for computing the singular
value decomposition (SVD). It begins by computing the
polar decomposition and then computes the spectral
decomposition of the Hermitian polar factor. The method
is particularly attractive for shared memory parallel
computers with a relatively small number of processors,
because the polar decomposition can be computed
efficiently on such machines using an iterative method
developed recently by the authors. This iterative polar
decomposition method requires only matrix
multiplication and matrix inversion kernels for its
implementation and is designed for full rank matrices;
thus the proposed SVD method is intended for matrices
that are not too close to being rank-deficient. On the
Kendall Square KSR1 virtual shared memory computer the
new method is up to six times faster than a
parallelized version of the LAPACK SVD routine,
depending on the condition number of the matrix.",
keywords = "singular value decomposition, polar decomposition,
numerical stability, LAPACK, level 3 BLAS, Kendall
Square Research KSR1 computer",
}
@techreport{Wille:1994:SID,
author = "David R. Wille and Christopher T. H. Baker",
title = "Some Issues in the Detection and Location of
Derivative Discontinuities in Delay Differential
Equations",
type = "Numerical Analysis Report",
number = "No. 238",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep238.ps.gz",
abstract = "The detection and location of derivative
discontinuities is a central issue in the design of
robust solvers for delay differential problems. In this
paper we discuss a number of particular features
associated with one common discontinuity tracking
strategy before addressing a particular problem arising
for a class of state-dependent problems.",
keywords = "Delay differential equations, derivative
discontinuities",
}
@techreport{Higham:1993:TMT,
author = "Nicholas J. Higham",
title = "The {Test Matrix Toolbox} for {MATLAB}",
type = "Numerical Analysis Report",
number = "No. 237",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = dec,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep237.ps.gz",
abstract-1 = "We describe version 2.0 of the Test Matrix Toolbox for
Matlab 4. The toolbox contains a collection of test
matrices, routines for visualizing matrices, and
miscellaneous routines that provide useful additions to
Matlab's existing set of functions. There are 58
parametrized test matrices, which are mostly square,
dense, nonrandom, and of arbitrary dimension. The test
matrices include ones with known inverses or known
eigenvalues; ill-conditioned or rank deficient
matrices; and symmetric, positive definite, orthogonal,
defective, involutary, and totally positive matrices.",
abstract-2 = "We describe version 2.0 of the Test Matrix Toolbox for
Matlab The visualization routines display surface plots
of a matrix and its (pseudo-) inverse, the field of
values, Gershgorin disks, and two- and
three-dimensional views of pseudospectra. We explain
the need for collections of test matrices and summarize
the features of the collection in the toolbox. We give
examples of the use of the toolbox and explain some of
the interesting properties of the Frank and Pascal
matrices, and of random, magic square and companion
matrices. The leading comment lines from all the
toolbox routines are listed.",
keywords = "test matrix, Matlab, pseudospectrum, visualization,
Frank matrix, Pascal matrix, companion matrix, magic
square matrix, random matrix",
note = "*** This report has been withdrawn and is replaced by
Report No. 276. ***"
}
@techreport{Higham:1993:SPT,
author = "Nicholas J. Higham",
title = "Stability of Parallel Triangular System Solvers",
type = "Numerical Analysis Report",
number = "No. 236",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep236.ps.gz",
abstract = "Several parallel algorithms have been proposed for
solution of triangular systems. The stability of four
of them is analysed here: a fan-in algorithm, a block
elimination method, a method based on a factorized
power series expansion of the matrix inverse, and a
method based on a divide and conquer matrix inversion
technique. We derive new forward error and residual
bounds, including an improvement on the bounds of Sameh
and Brent for the fan-in algorithm. We identify a
forward error bound that holds not only for all the
methods described here, but for any triangular equation
solver that does not rely on algebraic cancellation;
among the implications of the bound is that any such
method is extremely accurate for certain special types
of triangular system.",
keywords = "triangular system, matrix inversion, parallel
algorithms, fan-in operation, numerical stability,
rounding error analysis",
}
@techreport{Higham:1993:MPFb,
author = "Nicholas J. Higham and Philip A. Knight",
title = "Matrix Powers in Finite Precision Arithmetic",
type = "Numerical Analysis Report",
number = "No. 235",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = aug,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep235.ps.gz",
abstract = "If $A$ is a square matrix with spectral radius less
than 1 then $A^k \to 0$ as $k \to \infty$, but the
powers computed in finite precision arithmetic may or
may not converge. We derive a sufficient condition for
$fl(A^k) \to 0$ as $k\to\infty$ and a bound on
$\norm{fl(A^k)}$, both expressed in terms of the Jordan
canonical form of $A$. Examples show that the results
can be sharp. We show that the sufficient condition can
be rephrased in terms of a pseudospectrum of $A$ when
$A$ is diagonalizable, under certain assumptions. Our
analysis leads to the rule of thumb that convergence or
divergence of the computed powers of $A$ can be
expected according as the spectral radius computed by
any backward stable algorithm is less than or greater
than 1.",
keywords = "matrix powers, rounding errors, Jordan canonical form,
nonnormal matrices, pseudospectrum",
}
@techreport{MCCM:1993:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report 1992",
type = "Numerical Analysis Report",
number = "No. 233",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep233.pdf",
}
@techreport{Paul:1993:FCP,
author = "Christopher A. H. Paul",
title = "A {FORTRAN} 77 Code for Plotting Stability Regions",
type = "Numerical Analysis Report",
number = "No. 230",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep230.ps.gz",
abstract = "The standard technique for obtaining the stability
regions of numerical methods for ordinary differential
equations (ODEs) and delay differential equations
(DDEs) is the boundary-locus algorithm (BLA). However,
in the case of the DDE $y'(t) = \lambda y(t) + \mu
y(t-\tau)$ for $\lambda$ and $\mu$ real, the BLA often
fails to map out the stability region correctly. In
this paper we give a FORTRAN 77 listing of an
alternative stability boundary algorithm, which can be
used for both implicit and explicit numerical methods
applied to both ODEs and DDEs.",
keywords = "stability regions, boundary-locus algorithm,
Runge-Kutta methods",
}
@techreport{Baker:1993:GCT,
author = "Christopher T. H. Baker and Christopher A. H. Paul",
title = "A Global Convergence Theorem for a Class of Parallel Continuous
Explicit Runge-Kutta Methods and Vanishing Lag Delay Differential
Equations",
institution = "University of Manchester",
address = "England",
type = "Numerical Analysis Report",
number = "No. 229",
month = may,
year = "1993",
keywords = "parallel continuous explicit Runge-Kutta methods, iterated
continuous extensions, delay differential equations, vanishing
lag",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep229.ps.gz",
abstract = "Iterated continuous extensions (ICEs) are continuous explicit
Runge-Kutta methods developed for the numerical solution of
evolutionary problems in ordinary and delay differential
equations (DDEs). ICEs have a particular r\^{o}le in the
explicit solution of DDEs with vanishing lags. They may be
regarded as parallel continuous explicit Runge-Kutta (PCERK)
methods, as they allow advantage to be taken of parallel
architectures. ICEs can also be related to a collocation
method.
The purpose of this paper is to provide a theorem giving the
global order of convergence for variable-step implementations
of ICEs applied to state-dependent DDEs with and without
vanishing lags. Implications of the theoryfor the
implementation of this class of methods are discussed and
demonstrated. The results establish that our approach allows
the construction of PCERK methodswhose order of convergence is
restricted only by the continuity of the solution."
}
@techreport{Higham:1993:PAC,
author = "Nicholas J. Higham and Pythagoras Papadimitriou",
title = "A Parallel Algorithm for Computing the Polar
Decomposition",
type = "Numerical Analysis Report",
number = "No. 226",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep226.ps.gz",
abstract = "The polar decomposition $A=UH$ of a rectangular matrix
$A$, where $U$ is unitary and $H$ is Hermitian positive
semidefinite, is an important tool in various
applications, including aerospace computations, factor
analysis and signal processing. We consider a $p$th
order iteration for computing $U$ that involves $p$
independent matrix inversions per step and which is
hence very amenable to parallel computation. We show
that scaling the iterates speeds convergence of the
iteration but makes the iteration only conditionally
stable, with the backward error typically $\kappa_2(A)$
times bigger than the unit roundoff. In our
implementation of the iteration on the Kendall Square
Research KSR1 virtual shared memory MIMD computer we
take $p$ to be the number of processors ($p \le 16$ in
our experiments). Our code is found to be significantly
faster than two existing techniques for computing the
polar decomposition: one a Newton iteration, the other
based on the singular value decomposition.",
keywords = "polar decomposition, singular value decomposition,
numerical stability, LAPACK, level 3 BLAS, Kendall
Square Research KSR1 computer",
}
@techreport{Higham:1993:MSD,
author = "Nicholas J. Higham",
title = "The Matrix Sign Decomposition and Its Relation to the
Polar Decomposition",
type = "Numerical Analysis Report",
number = "No. 225",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = apr,
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep225.ps.gz",
abstract-1 = "The sign function of a square matrix was introduced by
Roberts in 1971. We show that it is useful to regard
$S=\sign(A)$ as being part of a matrix sign
decomposition $A=SN$, where $N = (A^2)^{1/2}$. This
decomposition leads to the new representation $\sign(A)
= A(A^2)^{-1/2}$. Most results for the matrix sign
decomposition have a counterpart for the polar
decomposition $A=UH$, and vice versa.",
abstract-2 = "To illustrate this, we derive best approximation
properties of the factors $U$, $H$ and~$S$, determine
bounds for $\norm{A-S}$ and $\norm{A-U}$, and describe
integral formulas for $S$ and $U$. We also derive
explicit expressions for the condition numbers of the
factors $S$ and $N$. An important equation expresses
the sign of a block $2\times2$ matrix involving $A$ in
terms of the polar factor $U$ of $A$. We apply this
equation to a family of iterations for computing $S$ by
Pandey, Kenney and Laub, to obtain a new family of
iterations for computing $U$. The iterations have some
attractive properties, including suitability for
parallel computation.",
keywords = "matrix sign function, polar decomposition,
conditioning, best approximation, properties, parallel
iteration",
}
@techreport{Higham:1992:SPI,
author = "Nicholas J. Higham and Alex Pothen",
title = "Stability of the Partitioned Inverse Method for
Parallel Solution of Sparse Triangular Systems",
type = "Numerical Analysis Report",
number = "No. 222",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = oct,
year = "1992",
note = "To appear in {\em SIAM J. Sci. Comput.}.",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep222.ps.gz",
abstract = "Several authors have recently considered a parallel
method for solving sparse triangular systems with many
right-hand sides. The method employs a partition into
sparse factors of the product form of the inverse of
the coefficient matrix. It is shown here that while the
method can be unstable, stability is guaranteed if a
certain scalar that depends on the matrix and the
partition is small, and that this scalar is small when
the matrix is well-conditioned. Moreover, when the
partition is chosen so that the factors have the same
sparsity structure as the coefficient matrix, the
backward error matrix can be taken to be sparse.",
keywords = "sparse matrix, triangular system, substitution
algorithm, parallel algorithm, rounding error analysis,
matrix inverse",
}
@Article{Higham:1993:FPB,
author = "Nicholas J. Higham and Philip A. Knight",
title = "Finite Precision Behavior of Stationary Iteration for
Solving Singular Systems",
journal = "Linear Algebra and Appl.",
volume = "192",
pages = "165--186",
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep215.ps.gz",
abstract-1 = "A stationary iterative method for solving a singular
system $Ax=b$ converges for any starting vector if
$\lim_{i\to\infty}G^i$ exists, where $G$ is the
iteration matrix, and the solution to which it
converges depends on the starting vector. We examine
the behaviour of stationary iteration in finite
precision arithmetic. A perturbation bound for singular
systems is derived and used to define forward stability
of a numerical method. A rounding error analysis
enables us to deduce conditions under which a
stationary iterative method is forward stable or
backward stable.",
abstract-2 = "A stationary iterative method for solving a singular
system The component of the forward error in the null
space of $A$ can grow linearly with the number of
iterations, but it is innocuous as long as the
iteration converges reasonably quickly. As special
cases, we show that when $A$ is symmetric positive
semi-definite the Richardson iteration with optimal
parameter is forward stable and, if $A$ also has unit
diagonal and property A, then the Gauss-Seidel method
is both forward and backward stable. Two numerical
examples are given to illustrate the analysis.",
keywords = "stationary iteration, singular system, Drazin inverse,
Jacobi method, Gauss-Seidel method, successive
over-relaxation, Richardson iteration, error analysis,
numerical stability, Neumann problem",
mynote = "Special issue for Proceedings of Workshop on
Computational Linear Algebra in Algebraic and Related
Problems",
}
@techreport{Paul:1992:FEV,
author = "Christopher A. H. Paul",
title = "A fast, efficient, very low storage, adaptive
quadrature scheme",
type = "Numerical Analysis Report",
number = "No. 213",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = may,
year = "1992",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep213.ps.gz",
abstract = "In this report we review the types of quadrature
scheme that are available for the evaluation of
integrals. We present a new adaptive quadrature scheme
which avoids the storage requirements of normal
adaptive schemes. Finally we provide a comparison of
all the types of quadrature scheme considered for a set
of test integrals.",
keywords = "adaptive quadrature, minimal storage",
}
@techreport{Paul:1992:ERK,
author = "Christopher A. H. Paul and Christopher T. H. Baker",
title = "Explicit {Runge-Kutta} Methods for the Numerical
Solution of Singular Delay Differential Equations",
type = "Numerical Analysis Report",
number = "No. 212",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = apr,
year = "1992",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep212.ps.gz",
abstract = "In this paper we are concerned with the development of
an explicit Runge-Kutta scheme for the numerical
solution of delay differential equations (DDEs) where
one or more delay lies in the current Runge-Kutta
interval. The scheme presented is also applicable to
the numerical solution of {\em Volterra functional
equations} (VFEs), although the theory is not covered
in this paper. We also derive the stability equations
of the scheme for the ODE $y'(t) = \lambda y(t)$, and
the DDE $y'(t) = \lambda y(t) + \mu y(t-\tau)$, where
the delay $\tau$ and the Runge-Kutta stepsize $H$ are
both constant. In the case of the DDE, we consider the
two distinct cases: $(i)$ $\tau \ge H$, and $(ii)$
$\tau < H$. We evaluate the performance of the scheme
by solving several types of {\em singular} DDE and a
VFE.",
keywords = "explicit Runge-Kutta, singular delay differential
equations",
}
@Article{Higham:1993:PTB,
author = "Nicholas J. Higham",
title = "Perturbation Theory and Backward Error for {$AX-XB=C$}",
journal = "BIT",
volume = 33,
pages = "124-136",
year = "1993",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep211.ps.gz",
abstract = "Because of the special structure of the equations $AX-XB=C$ the
usual relation for linear equations ``$\mbox{backward error} =
\mbox{relative residual}$'' does not hold, and application of the
standard perturbation result for $Ax=b$ yields a perturbation
bound involving ${\rm sep}(A,B)^{-1}$ that is not always
attainable. An expression is derived for the backward error of
an approximate solution $Y$; it shows that the backward error can
exceed the relative residual by an arbitrary factor. A sharp
perturbation bound is derived and it is shown that the condition
number it defines can be arbitrarily smaller than the ${\rm
sep}(A,B)^{-1}$-based quantity that is usually used to measure
sensitivity. For practical error estimation using the residual
of a computed solution an ``LAPACK-style'' bound is shown to be
efficiently computable and potentially much smaller than a
sep-based bound. A Fortran~77 code has been written that solves
the Sylvester equation and computes this bound, making use of
LAPACK routines.",
keywords = "Sylvester equation, Lyapunov equation, backward error,
perturbation bound, condition number, error estimate, LAPACK."
}
@techreport{Baker:1992:ESA,
author = "Christopher T. H. Baker and John C. Butcher and
Christopher A. H. Paul",
title = "Experience of {STRIDE} applied to delay differential
equations",
type = "Numerical Analysis Report",
number = "No. 208",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = feb,
year = "1992",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep208.ps.gz",
abstract = "STRIDE is intended as a robust adaptive code for
solving {\em initial value problems} for {\em ordinary
differential equations} (ODEs). The acronym STRIDE
stands for {\bf ST}able {\bf R}unge-Kutta {\bf
I}ntegrator for {\bf D}ifferential {\bf E}quations. Our
purpose here is to report on its adaptation for the
numerical solution of a set of delay and neutral
differential equations.",
keywords = "STRIDE, delay and neutral differential equations",
}
@InProceedings{Higham:1993:MPFa,
author = "Nicholas J. Higham and Philip A. Knight",
editor = "Carl D. Meyer and Robert J. Plemmons",
booktitle = "Linear Algebra, Markov Chains, and Queueing Models",
title = "Componentwise Error Analysis for Stationary Iterative
Methods",
volume = "48",
publisher = pub-SV,
address = pub-SV:adr,
pages = "29--46",
year = "1993",
series = "IMA Volumes in Mathematics and its Applications",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep206.ps.gz",
asbtract = "How small can a stationary iterative method for
solving a linear system $Ax=b$ make the error and the
residual in the presence of rounding errors? We give a
componentwise error analysis that provides an answer to
this question and we examine the implications for
numerical stability. The Jacobi, Gauss-Seidel and
successive over-relaxation methods are all found to be
forward stable in a componentwise sense and backward
stable in a normwise sense, provided certain conditions
are satisfied that involve the matrix, its splitting,
and the computed iterates. We show that the stronger
property of componentwise backward stability can be
achieved using one step of iterative refinement in
fixed precision, under suitable assumptions.",
keywords = "stationary iteration, Jacobi method, Gauss-Seidel
method, successive over-relaxation, error analysis,
numerical stability",
}
@techReport{Paul:1991:SBR,
author = "Christopher A. H. Paul and Christopher T. H. Baker",
title = "Stability boundaries revisited --- {Runge-Kutta}
methods for delay differential equations",
type = "Numerical Analysis Report",
number = "No. 205",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = dec,
year = "1991",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep205.ps.gz",
abstract = "We discuss the practical determination of stability
regions when various Runge-Kutta methods, combined with
continuous extensions, are applied with a fixed
stepsize $h$ to the linear delay differential test
equation $ y'(t) = \lambda y(t) +\mu y(t-\tau) \quad (t
\ge 0)$, with fixed delay $\tau$. The delay $\tau$ is
not limited to an integer multiple of the stepsize
$h$.",
keywords = "delay differential equation, continuous extension,
stability",
}
@techReport{Paul:1991:DDD,
author = "Christopher A. H. Paul",
title = "Developing a Delay Differential Equation Solver",
type = "Numerical Analysis Report",
number = "No. 204",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = dec,
year = "1991",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep204.ps.gz",
abstract = "We discuss briefly various phenomena to be tested when
designing a robust code for delay differential
equations: choice of interpolant; tracking of
discontinuities; vanishing delays; and problems arising
from floating-point arithmetic.",
keywords = "delay differential equations, interpolation,
discontinuities, vanishing delay, real arithmetic",
}
@InProceedings{Higham:1990:HAG,
author = "Nicholas J. Higham",
editor = "D. F. Griffiths and G. A. Watson",
booktitle = "Numerical Analysis 1989, Proceedings of the 13th
Dundee Conference",
title = "How Accurate is {Gaussian} Elimination?",
volume = "228",
publisher = pub-LONGMAN,
address = pub-LONGMAN:adr,
pages = "137--154",
year = "1990",
series = "Pitman Research Notes in Mathematics",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep173.ps.gz",
abstract = "J. H. Wilkinson put Gaussian elimination (GE) on a
sound numerical footing in the 1960s when he showed
that with partial pivoting the method is stable in the
sense of yielding a small backward error. He also
derived bounds proportional to the condition number
$\kappa(A)$ for the forward error $\|x-\widehat x\|$,
where $\widehat x$ is the computed solution to $Ax=b$.
More recent work has furthered our understanding of GE,
largely through the use of componentwise rather than
normwise analysis. We survey what is known about the
accuracy of GE in both the forward and backward error
senses. Particular topics include: classes of matrix
for which it is advantageous not to pivot; how to
estimate or compute the backward error; iterative
refinement in single precision; and how to compute
efficiently a bound on the forward error.",
keywords = "Gaussian elimination, partial pivoting, rounding error
analysis, backward error, forward error, condition
number, iterative refinement in single precision,
growth factor, componentwise bounds, condition
estimator",
}
@InProceedings{Higham:1990:ACD,
author = "Nicholas J. Higham",
editor = "M. G. Cox and S. J. Hammarling",
booktitle = "Reliable Numerical Computation",
title = "Analysis of the {Cholesky} Decomposition of a
Semi-definite Matrix",
publisher = pub-OUP,
address = pub-OUP:adr,
pages = "161--185",
year = "1990",
URL = "http://www.maths.manchester.ac.uk/~higham/narep/narep128.ps.gz",
abstract = "Perturbation theory is developed for the \Chol\ of an
$n \times n$ symmetric \psd\ matrix $A$ of rank~$r$.
The matrix $W=\All^{-1}\A{12}$ is found to play a key
role in the \pert\ bounds, where $\All$ and $\A{12}$
are $r \times r$ and $r \times (n-r)$ submatrices of
$A$ respectively. A backward error analysis is given;
it shows that the computed Cholesky factors are the
exact ones of a matrix whose distance from $A$ is
bounded by
$4r(r+1)\bigl(\norm{W}+1\bigr)^2u\norm{A}+O(u^2)$,
where $u$ is the unit roundoff. For the \cpiv\ strategy
it is shown that $\norm{W}^2 \le {1 \over 3}(n-r)(4^r-
1)$, and empirical evidence that $\norm{W}$ is usually
small is presented. The overall conclusion is that the
\Cholalg\ with \cpiv\ is stable for semi-definite
matrices. Similar \pert\ results are derived for the
\QR\ with \colpiv\ and for the LU decomposition with
\cpiv. The results give new insight into the
reliability of these decompositions in rank
estimation.",
keywords = "Cholesky decomposition, positive semi-definite matrix,
perturbation theory, backward error analysis, QR
decomposition, rank estimation, LINPACK",
}