URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep128.dvi.Z
Document-type: InProceedings
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: "Oxford University Press"
address: "Walton Street, Oxford OX2 6DP, UK"
pages: "161--185"
year: "1990"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep173.dvi.Z
Document-type: InProceedings
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: "Longman Scientific and Technical"
address: "Essex, UK"
pages: "137--154"
year: "1990"
series: "Pitman Research Notes in Mathematics"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep204.ps.Z
Document-type: TechReport
author: "Christopher A. H. Paul"
title: "Developing a Delay Differential Equation Solver"
type: "Numerical Analysis Report"
number: "204"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: dec,
year: "1991"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep205.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: dec,
year: "1991"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep206.ps.Z
Document-type: InProceedings
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: "Spring\-er-Ver\-lag"
address: "Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ etc."
pages: "29--46"
year: "1993"
series: "IMA Volumes in Mathematics and its Applications"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep208.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: feb,
year: "1992"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep211.dvi.Z
Document-type: Article
author: "Nicholas J. Higham"
title = "Perturbation Theory and Backward Error for $AX-XB=C$",
journal: "BIT"
volume: 33,
pages: "124-136"
year: 1993,
abstract = "Because of the special structure of the equations $AX-XB=C$ the
usual relation for linear equations ``$\mboxbackward error =
\mboxrelative 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."
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep212.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: apr,
year: "1992"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep213.ps.Z
Document-type: TechReport
author: "Christopher A. H. Paul"
title: "A fast, efficient, very low storage, adaptive
quadrature scheme",
type: "Numerical Analysis Report"
number: "213"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: may,
year: "1992"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep215.ps.Z
Document-type: Article
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"
abstract-1: "A stationary iterative method for solving a singular
system $Ax=b$ converges for any starting vector if
$\lim_i\to\inftyG^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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep222.dvi.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: oct,
year: "1992"
note: "To appear in \em SIAM J. Sci. Comput.."
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep225.dvi.Z
Document-type: TechReport
author: "Nicholas J. Higham"
title: "The Matrix Sign Decomposition and Its Relation to the
Polar Decomposition",
type: "Numerical Analysis Report"
number: "225"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: apr,
year: "1993"
note: "To appear in \em Linear Algebra and Appl.."
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 $\normA-S$ and $\normA-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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep226.dvi.Z
Document-type: TechReport
author: "Nicholas J. Higham and Pythagoras Papadimitriou"
title: "A Parallel Algorithm for Computing the Polar
Decomposition",
type: "Numerical Analysis Report"
number: "226"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jun,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep229.ps.Z
Document-type: techreport
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",
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."
}
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep230.ps.Z
Document-type: TechReport
author: "Christopher A. H. Paul"
title: "A FORTRAN 77 Code for Plotting Stability Regions"
type: "Numerical Analysis Report"
number: "230"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: may,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep233.dvi.Z
Document-type: TechReport
author: "Manchester Centre for Computational Mathematics"
title: "Annual Report 1992"
type: "Numerical Analysis Report"
number: "233"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jun,
year: "1993"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep235.ps.Z
Document-type: TechReport
author: "Nicholas J. Higham and Philip A. Knight"
title: "Matrix Powers in Finite Precision Arithmetic"
type: "Numerical Analysis Report"
number: "235"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: aug,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep236.dvi.Z
Document-type: TechReport
author: "Nicholas J. Higham"
title: "Stability of Parallel Triangular System Solvers"
type: "Numerical Analysis Report"
number: "236"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jul,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep237.ps.Z
Document-type: TechReport
author: "Nicholas J. Higham"
title: "The Test Matrix Toolbox for MATLAB"
type: "Numerical Analysis Report"
number: "237"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: dec,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep238.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: mar,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep239.dvi.Z
Document-type: TechReport
author: "Nicholas J. Higham and Pythagoras Papadimitriou"
title: "Parallel Singular Value Decomposition via the Polar
Decomposition",
type: "Numerical Analysis Report"
number: "239"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: oct,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep241.dvi.Z
Document-type: TechReport
author: "Nicholas J. Higham"
title: "A Survey of Componentwise Perturbation Theory in
Numerical Linear Algebra",
type: "Numerical Analysis Report"
number: "241"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
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.",
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep242.ps.Z
Document-type: TechReport
author: "Pythagoras Papadimitriou"
title: "The KSR1---A Numerical Analyst's Perspective"
type: "Numerical Analysis Report"
number: "242"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: dec,
year: "1993"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep243.ps.Z
Document-type: TechReport
author: "Christopher A. H. Paul"
title: "A Test Set of Functional Differential Equations"
type: "Numerical Analysis Report"
number: "243"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: feb,
year: "1994"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep245.ps.Z
Document-type: TechReport
author: "George Hall"
title: "A New Stepsize Strategy for Runge-Kutta codes"
type: "Numerical Analysis Report"
number: "245"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: mar,
year: "1994"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep246.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: mar,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep247.ps.Z
Document-type: TechReport
author: "David R. Wille"
title: "New Stepsize Estimators for Linear Multistep Methods"
type: "Numerical Analysis Report"
number: "247"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: mar,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep248.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: apr,
year: "1994"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep249.ps.Z
Document-type: TechReport
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\"odinger Equation",
type: "Numerical Analysis Report"
number: "249"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jul,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep251.ps.Z
Document-type: TechReport
author: "Manchester Centre for Computational Mathematics"
title: "Annual Report 1993"
type: "Numerical Analysis Report"
number: "251"
institution: "University of Manchester"
address: "Manchester M13 9PL, England"
month: may,
year: "1994"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep252.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jul,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep254.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jul,
year: "1994"
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"
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib
URL: ftp://vtx.ma.man.ac.uk/pub/narep/narep255.ps.Z
Document-type: TechReport
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: "University of Manchester"
address: "Manchester M13 9PL, England"
month: jul,
year: "1994"
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",
bibsource: ftp://vtx.ma.man.ac.uk/pub/narep/u-manchester-mccm.bib