%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nicholas J. Higham",
%%% version = "1.00",
%%% date = "December 7, 1999",
%%% 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 = "higham at ma.man.ac.uk (Internet)",
%%% 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 = "narep.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.
%%%
%%% The numeric Internet address of ftp.ma.man.ac.uk is 130.88.16.53.
%%%
%%% For details of how to access the reports, see the README file.
%%%
%%% Files not associated with technical reports:
%%%
%%% mscflyer.ps.gz One page flyer advertising the M.Sc. in Numerical Analysis
%%% and Computing in the Departments of Mathematics at the
%%% University of Manchester and UMIST.
%%%
%%% msc-NA.ps.gz Document fully describing the M.Sc. in Numerical Analysis
%%% and Computing in the Departments of Mathematics at the
%%% University of Manchester and UMIST.
%%% Updated each year.
%%%
%%% nagroup.dvi.gz Document describing the Numerical Analysis Group
%%% in the Department of Mathematics at the University
%%% of Manchester. Regularly updated.
@String{inst-MCCM = "Manchester Centre for
Computational Mathematics"}
@String{inst-MCCM:adr = "Manchester, England"}
%%% Numerical Analysis Reports: ISSN 1360-1725
@String{inst-U-MANCHESTER = "University of Manchester"}
@String{inst-U-MANCHESTER:adr = "Manchester M13 9PL, England"}
% @String{inst-U-MANCHESTER-UMIST = "University of Manchester\slash UMIST"}
% @String{inst-U-MANCHESTER-UMIST: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 = "Walton Street, Oxford OX2 6DP, UK"}
@String{pub-SV = "Spring{\-}er-Ver{\-}lag"}
@String{pub-SV:adr = "Berlin, Germany~/ Heidelberg,
Germany~/ London, UK~/ etc."}
@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 = "narep128.dvi.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",
}
@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 = "narep173.dvi.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",
}
@TechReport{Paul:1991:DDD,
author = "Christopher A. H. Paul",
title = "Developing a Delay Differential Equation Solver",
type = "Numerical Analysis Report",
number = "204",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = dec,
year = "1991",
URL = "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",
}
@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 = "205",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = dec,
year = "1991",
URL = "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",
}
@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 = "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{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 = "208",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = feb,
year = "1992",
URL = "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",
}
@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 = "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{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 = "212",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = apr,
year = "1992",
URL = "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",
}
@TechReport{Paul:1992:FEV,
author = "Christopher A. H. Paul",
title = "A fast, efficient, very low storage, adaptive
quadrature scheme",
type = "Numerical Analysis Report",
number = "213",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = may,
year = "1992",
URL = "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",
}
@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 = "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{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 = "222",
institution = inst-U-MANCHESTER,
address = inst-U-MANCHESTER:adr,
month = oct,
year = "1992",
note = "To appear in {\em SIAM J. Sci. Comput.}.",
URL = "narep222.dvi.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",
}
@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 = "225",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = apr,
year = "1993",
note = "To appear in {\em Linear Algebra and Appl.}.",
URL = "narep225.dvi.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:1993:PAC,
author = "Nicholas J. Higham and Pythagoras Papadimitriou",
title = "A Parallel Algorithm for Computing the Polar
Decomposition",
type = "Numerical Analysis Report",
number = "226",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1993",
URL = "narep226.dvi.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{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 = "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{Paul:1993:FCP,
author = "Christopher A. H. Paul",
title = "A {FORTRAN} 77 Code for Plotting Stability Regions",
type = "Numerical Analysis Report",
number = "230",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1993",
URL = "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{MCCM:1993:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report 1992",
type = "Numerical Analysis Report",
number = "233",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1993",
URL = "narep233.dvi.gz",
}
@TechReport{Higham:1993:MPFb,
author = "Nicholas J. Higham and Philip A. Knight",
title = "Matrix Powers in Finite Precision Arithmetic",
type = "Numerical Analysis Report",
number = "235",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = aug,
year = "1993",
URL = "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{Higham:1993:SPT,
author = "Nicholas J. Higham",
title = "Stability of Parallel Triangular System Solvers",
type = "Numerical Analysis Report",
number = "236",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1993",
URL = "narep236.dvi.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:TMT,
author = "Nicholas J. Higham",
title = "The {Test Matrix Toolbox} for {MATLAB}",
type = "Numerical Analysis Report",
number = "237",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = dec,
year = "1993",
URL = "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{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 = "238",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "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:PSV,
author = "Nicholas J. Higham and Pythagoras Papadimitriou",
title = "Parallel Singular Value Decomposition via the Polar
Decomposition",
type = "Numerical Analysis Report",
number = "239",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1993",
URL = "narep239.dvi.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{Higham:1994:SCP,
author = "Nicholas J. Higham",
title = "A Survey of Componentwise Perturbation Theory in
Numerical Linear Algebra",
type = "Numerical Analysis Report",
number = "241",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = feb,
year = "1994",
note = "To appear in {\em Mathematics of Computation
1943--1993}, W. Gautschi, ed. Proceedings of Symposia
in Applied Mathematics, American Mathematical
Society.",
URL = "narep241.dvi.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{Papadimitriou:1993:KNA,
author = "Pythagoras Papadimitriou",
title = "The {KSR1}---{A} Numerical Analyst's Perspective",
type = "Numerical Analysis Report",
number = "242",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = dec,
year = "1993",
URL = "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{Paul:1994:TSF,
author = "Christopher A. H. Paul",
title = "A Test Set of Functional Differential Equations",
type = "Numerical Analysis Report",
number = "243",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = feb,
year = "1994",
URL = "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{Hall:1994:NSS,
author = "George Hall",
title = "A New Stepsize Strategy for {Runge-Kutta} codes",
type = "Numerical Analysis Report",
number = "245",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "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{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 = "246",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "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{Wille:1994:NSE,
author = "David R. Wille",
title = "New Stepsize Estimators for Linear Multistep Methods",
type = "Numerical Analysis Report",
number = "247",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = mar,
year = "1994",
URL = "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{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 = "248",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = apr,
year = "1994",
URL = "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{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 = "249",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "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{MCCM:1994:AR,
author = "Manchester Centre for Computational Mathematics",
title = "Annual Report 1993",
type = "Numerical Analysis Report",
number = "251",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1994",
URL = "narep251.ps.gz",
}
@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 = "252",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "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{Wille:1994:ESC,
author = "David Richard Will\'e",
title = "Experiments in Stepsize Control for {Adams} Linear
Multistep Methods",
type = "Numerical Analysis Report",
number = "253",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1994",
URL = "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{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 = "254",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "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{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 = "255",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jul,
year = "1994",
URL = "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{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 = "257",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = sep,
year = "1994",
note = "Submitted to SIAM J. Numer. Anal.",
URL = "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{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 = "260",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = oct,
year = "1994",
URL = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "267",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = may,
year = "1995",
URL = "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{Hall:1995:ESM,
author = "George Hall",
title = "Equilibrium States for Multistep Methods",
type = "Numerical Analysis Report",
number = "268",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1995",
URL = "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: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 = "269",
institution = inst-MCCM,
address = inst-MCCM:adr,
month = jun,
year = "1995",
URL = "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{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 = "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{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 = "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{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 = "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{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 = "narep275.ps.gz",
}
@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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "narep286.ps.gz",
}
@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 = "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{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 = "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{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 = "narep289.ps.gz",
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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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: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 = "narep297.ps.gz",
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{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 = "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{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 = "narep299.ps.gz"
}
@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 = "narep300.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 = "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{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 = "narep302.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 = "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{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 = "narep304.ps.gz",
}
@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 = "narep305.ps.gz",
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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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: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 = "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: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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "narep320.ps.gz",
}
@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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "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{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 = "narep333.ps.gz",
note = "To appear in proceedings of EPSRC Numerical Analysis Summer School,
Leicester University, July 1998."
}
@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 = "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: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 = "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{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 = "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{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 = "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{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 = "narep339.ps.gz",
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{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 = "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: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 = "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{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 = "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{Rihan:99:SAP,
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 = "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{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 = "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{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 = "narep347.ps.gz",
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{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 = "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{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 = "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{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 = "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{Ford:1999:Charroots,
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 = "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{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 = "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{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 = "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{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 = "narep354.ps.gz",
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{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 = "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"
}