MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Inexact Sparse Matrix-Vector Products in the Calculation of Passage Time Distributions in Large Semi-Markov Models
Get PDFWe have previously presented an iterative algorithm based on repeated sparse matrix-vector multiplication for the calculation of passage time distributions in large semi-Markov models. We showed that the required number of operations can be reduced without affecting the accuracy of the final result if we do not perform multiplications with vector elements that are small in magnitude. Our earlier evaluation was limited, however, to a small number of test cases and no general error bound was derived. This paper addresses our prior work's limitations. We present an error analysis of inexact matrix-vector products in our iterative algorithm that leads to a bound on the overall error compared with the exactly computed solution. We support this analysis with numerical results from a range of semi-Markov models that demonstrate that the bound is valid in practice and that reducing the number of multiplications leads to a reduction in run-time of over 50% in the best cas
Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
Get PDFWe show that the sequence of moduli of the eigenvalues of a matrix polynomial is log-majorized, up to universal constants, by a sequence of "tropical roots" depending only on the norms of the matrix coefficients. These tropical roots are the non-differentiability points of an auxiliary tropical polynomial, or equivalently, the opposites of the slopes of its Newton polygon. This extends to the case of matrix polynomials some bounds obtained by Hadamard, Ostrowski and Pólya for the roots of scalar polynomials. We also obtain new bounds in the scalar case, which are accurate for "fewnomials" or when the tropical roots are well separated
Computing the Frechet Derivative of the Matrix Logarithm and Estimating the Condition Number
No full textThe most popular method for computing the matrix logarithm is the
inverse scaling and squaring method, which is the basis of the recent
algorithm of [A. H. Al-Mohy and N. J. Higham, \emph{Improved inverse
scaling and squaring algorithms for the matrix logarithm}, SIAM J.
Sci.\ Comput., 34 (2012), pp.~C152--C169].
For real matrices
we develop a version of the latter algorithm
that works entirely in real arithmetic
and is twice as fast as and more accurate than the original algorithm.
We show that by differentiating the algorithms we obtain backward stable
algorithms for computing the Fr\'echet derivative.
We demonstrate experimentally that our two algorithms are more
accurate and efficient than existing algorithms for computing the
Fr\'echet derivative
and we also show how the algorithms can be used to produce reliable
estimates of the condition number of the matrix logarithm
Performance Analysis of Asynchronous Parallel Jacobi
No full textThe directed acyclic graph (DAG) associated with a parallel al- gorithm captures the order in which separate local computations are completed and how their outputs are subsequently used in further com- putations. Unlike in a synchronous parallel algorithm the DAG asso- ciated with an asynchronous parallel algorithm is not predetermined. Instead it is a product of the asynchronous timing dynamics of the machine and, as such, it is best thought of as a pseudorandom vari- able. In this paper we present a new tighter bound on the rate of convergence of asynchronous parallel Jacobi (APJ), which is based on statistical properties of the DAG and is valid for systems which satisfy a standard sufficient condition for convergence.
We also describe an experiment in which we make a precise log of the calculations taking place during an implementation of APJ on a distributed memory multicore machine, which enables us to reconstruct and study the DAG. We demonstrate that our bound provides a good approximation of the true rate of convergence in these examples and show how problems in the algorithm�s implementation can affect the asynchronous timing dynamics and in turn the rate of convergence of the algorithm
Bayesian data assimilation in shape registration
Get PDFIn this paper we apply a Bayesian framework to the problem of geodesic curve matching. Given a template curve, the geodesic equations provide a mapping from initial conditions for the conjugate momentum onto topologically equivalent shapes. Here, we aim to recover the well-defined posterior distribution on the initial momentum which gives rise to observed points on the target curve; this is achieved by explicitly including a reparameterization in the formulation. Appropriate priors are chosen for the functions which together determine this field and the positions of the observation points, the initial momentum p0 and the reparameterization vector field ν, informed by regularity results about the forward model. Having done this, we illustrate how maximum likelihood estimators can be used to find regions of high posterior density, but also how we can apply recently developed Markov chain Monte Carlo methods on function spaces to characterize the whole of the posterior density. These illustrative examples also include scenarios where the posterior distribution is multimodal and irregular, leading us to the conclusion that knowledge of a state of global maximal posterior density does not always give us the whole picture, and full posterior sampling can give better quantification of likely states and the overall uncertainty inherent in the problem
Real-Time imaging with a high speed X-Ray CT system
Get PDFThe Real Time Tomography (RTT) system is a new type of fast cone beam CT scanner, using fixed rings of multiple sources and detectors in an offset geometry. We demonstrate the potential of this system for use in the imaging of high speed dynamic processes, such as moving fluid flows. The effect of the source firing pattern is discussed, with application to increasing the temporal resolution of the system. Through the use of a simple temporal regularisation term, we show that temporal resolution can be further increased, at the expense of a slight loss in spatial resolution
Backward stability of iterations for computing the polar decomposition
Get PDFAmong the many iterations available for computing the polar decomposition the most practically useful are the scaled Newton iteration and the recently proposed dynamically weighted Halley iteration. Effective ways to scale these and other iterations are known, but their numerical stability is much less well understood. In this work we show that a general iteration for computing the unitary polar factor is backward stable under two conditions. The first condition requires that the iteration is implemented in a mixed backward--forward stable manner and the second requires that the mapping
does not significantly decrease the size of any singular value relative to the largest singular value.
Using this result we show that the dynamically weighted Halley iteration is backward stable when it is implemented using Householder QR factorization with column pivoting and either row pivoting or row sorting. We also prove the backward stability of the scaled Newton iteration under
the assumption that matrix inverses are computed in a mixed
backward-forward stable fashion; our proof is much shorter than a previous one of Kielbasinski and Zietak.
We also use our analysis to explain the instability of
the inverse Newton iteration and to show that the Newton-Schulz iteration is only conditionally stable.
This work shows that by carefully blending perturbation analysis with rounding error analysis it is possible to produce a general result that can prove the backward stability or predict or explain the instability (as the case may be) of a wide range of practically interesting iterations for the polar decomposition
On the (Page)Ranking of Professional Tennis Players
Get PDFWe explore the relationship between official rankings of professional tennis players and rankings computed using a variant of the PageRank algorithm as proposed by Radicchi in 2011. We show Radicchi�s equations follow a natural interpretation of the PageRank algorithm and present up-to-date comparisons of official rankings with PageRank-based rankings for both the Association of Tennis Professionals (ATP) and Women�s Tennis Association (WTA) tours. For top-ranked players these two rankings are broadly in line; however, there is wide variation in the tail which leads us to question the degree to which the official ranking mechanism reflects true player ability. For a 390-day sample of recent tennis matches, PageRank-based rankings are found to be better predictors of match outcome than the official rankings
Computing the Frechet Derivative of the Matrix Logarithm and Estimating the Condition Number
Get PDFThe most popular method for computing the matrix logarithm is the
inverse scaling and squaring method, which is the basis of the recent
algorithm of [A. H. Al-Mohy and N. J. Higham, \emph{Improved inverse
scaling and squaring algorithms for the matrix logarithm}, SIAM J.
Sci.\ Comput., 34 (2012), pp.~C152--C169].
We show that by differentiating the latter algorithm a backward stable
algorithm for computing the Fr\'echet derivative
of the matrix logarithm is obtained.
This algorithm requires complex arithmetic, but we also develop a
version that uses only real arithmetic when is real;
as a special case we obtain a new algorithm for computing the logarithm of
a real matrix in real arithmetic.
We show experimentally that our two algorithms are more
accurate and efficient than existing algorithms for computing the
Fr\'echet derivative.
We also show how the algorithms can be used to produce reliable
estimates of the condition number of the matrix logarithm
Finite and Infinite Elementary Divisors of Matrix Polynomials: A Global Approach
Get PDFThere is general agreement on the definition of the finite elementary divisors of a matrix polynomial Q(\l)\in\F[\l]^{m\times n}, where \F an arbitrary field.
Regarding the elementary divisors at infinity, or infinite elementary divisors, such an agreement has not been so unanimous.
We define the infinite elementary divisors of Q(\l) to be the elementary divisors of \l^\ell Q(\l^{-1}) at 0, where is the degree of Q(\l).
We show that this is the most natural definition if one applies the usual geometric technique of using homogeneous coordinates to deal with the point at infinity.
We call our approach global because the homogeneous invariant factors of Q(\l) are defined for all points of the projective line and to distinguish it from
another possible approach that, using local rings, leads to the same conclusions