MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions
Get PDFWe propose a general algorithm for solving a nonsingular linear system based on iterative refinement with three precisions. The working precision is combined with possibly different precisions for solving for the correction term and for computing the residuals. Via rounding error analysis of the algorithm we derive sufficient conditions for convergence and bounds for the attainable normwise forward error and normwise and componentwise backward errors. Our results generalize and unify many existing rounding error analyses for iterative refinement. With single precision as the working precision, we show that by using LU factorization in IEEE half precision as the solver and calculating the residuals in double precision it is possible to solve to full single precision accuracy for condition numbers , with the part of the computations carried out entirely in half precision. We show further that by solving the correction equations by GMRES preconditioned by the LU factors the restriction on the condition number can be weakened to , although in general there is no guarantee that GMRES will converge quickly. Taking for comparison a standard solver that uses LU factorization in single precision, these results suggest that on architectures for which half precision is efficiently implemented it will be possible to solve certain linear systems up to twice as fast \emph{and} to greater accuracy. Analogous results are given with double precision as the working precision
On the exponential generating function for non-backtracking walks
Get PDFWe derive an explicit formula for the exponential generating function associated with non-backtracking walks around a graph. We study both undirected and directed graphs. Our results allow us to derive computable expressions for non-backtracking versions of network centrality measures based on the matrix exponential. We find that eliminating backtracking walks in this context does not significantly increase the computational expense. We show how the new measures may be interpreted in terms of standard exponential centrality computation on a certain multilayer network. Insights from this block matrix interpretation also allow us to characterize centrality measures arising from general matrix functions. Rigorous analysis on the star graph illustrates the effect of non-backtracking and shows that unwanted localization effects can be eliminated when we restrict to non-backtracking walks. We also investigate the localization issue on synthetic networks
Practical Approaches to Reconstruction and Analysis for 3D and Dynamic 3D Computed Tomography
Get PDFThe problem of reconstructing an image from a set of tomographic data is not new, nor is it lacking attention. However there is still a distinct gap between the mathematicians and the experimental scientists working in the computed tomography (CT) imaging community. One of the aims in this thesis is to bridge this gap with mathematical reconstruction algorithms and analysis approaches applied to practical CT problems.
The thesis begins with an extensive analysis for assessing the suitability of recon- struction algorithms for a given problem. The paper presented examines the idea of extracting physical information from a reconstructed sample and comparing against the known sample characteristics to determine the accuracy of a reconstructed vol- ume. Various test cases are studied, which are relevant to both mathematicians and experimental scientists. These include the variance in quality of reconstructed volume as the dose is reduced or the implementation of the level set evolution method, used as part of a simultaneous reconstruction and segmentation technique. The work shows that the assessment of physical attributes results in more accurate conclusions. Fur- thermore, this approach allows for further analysis into interesting questions in CT. This theme is continued throughout the thesis.
Recent results in compressive sensing (CS) gained attention in the CT community as they indicate the possibility of obtaining an accurate reconstruction of a sparse im- age from severely limited or reduced amount of measured data. Literature produced so far has not shown that CS directly guarantees a successful recovery in X-ray CT, and it is still unclear under which conditions a successful sparsity regularized reconstruction can be achieved. The work presented in the thesis aims to answer this question in a practical setting, and seeks to establish a direct connection between the success of sparsity regularization methods and the sparsity level of the image, which is similar to CS. Using this connection, one can determine the sufficient amount of measurements to collect from just the sparsity of an image. A link was found in a previous study using simulated data, and the work is repeated here with experimental data, where the sparsity level of the scanned object varies. The preliminary work presented here ver- ifies the results from simulated data, showing an “almost-linear”relationship between the sparsity of the image and the sufficient amount of data for a successful sparsity regularized reconstruction.
Several unexplained artefacts are noted in the literature as the ‘partial volume’, the ‘exponential edge gradient’ or the ‘penumbra’ effect, with no clear explanation for their cause, or established techniques to remove them. The work presented in this paper shows that these artefacts are due to a non-linearity in the measured data, which comes from either the set up of the system, the scattering of rays or the dependency of linear attenuation on wavelength in the polychromatic case. However, even in monochromatic CT systems, the non-linearity effect can be detected. The paper shows that in some cases, the non-linearity effect is too large to ignore, and the reconstruction problem should be adapted to solve a non-linear problem. We derive this non-linear problem and solve it using a numerical optimization technique for both simulated and real, γ-ray data. When compared to reconstructions obtained using the standard linear model, the non-linear reconstructed images show clear improvements in that the non-linear effect is largely eliminated.
The thesis is finished with a highlight article in the special issue of Solid Earth, named “Pore-scale tomography & imaging - applications, techniques and recommended practice”. The paper presents a major technical advancement in a dynamic 3D CT data acquisition, where the latest hardware and optimal data acquisition plan are applied and as a result, ultra fast 3D volume acquisition was made possible. The experiment comprised of fast, free-falling water-saline drops traveling through a pack of rock grains with varying porosities. The imaging work was enhanced by the use of iterative methods and physical quantification analysis performed. The data acquisition and imaging work is the first in the field to capture a free falling drop and the imaging work clearly shows the fluid interaction with speed, gravity and more importantly, the inter- and intra-grain fluid transfers
Robust chaos revisited
Get PDFRobust chaos is an important idea in the study of piecewise smooth maps. The different techniques used to prove the existence of robust chaos are reviewed a new genericity condition for the classic example is established. The theoretical conditions for the existence of robust chaos are verified numerically providing additional evidence for robust chaos in some examples.
\end{abstract
Effect of tropical scaling on linearizations of matrix polynomials: backward error and conditioning
No full textThe \textit{tropical scaling} algorithm
has experimentally shown to generate
accurate results in computing the eigenpairs of a
matrix polynomial P(\l)=\sum_{k=1}^\d \l^k A_k.
This algorithm scales P(\l) by using certain quantities
known as \textit{tropical roots}, then, for each tropical roots,
it constructs a linearization
of the tropically scaled polynomial,
computes its eigenpairs and extracts eigenpairs of P(\l)
from those of the linearizations.
In this work we analyse this algorithm in
terms of backward error and conditioning.
We show that when the tropical roots are well separated,
for an eigenpair,
the backward error of the scale matrix polynomial
is bounded by the backward error of its linearization
times the condition number of certain coefficients of P(\l).
These coefficients determine the abscissae of the nodes of the
{\it Newton polygon} associated with the matrix polynomial.
Similar results show
that for an eigenvalue,
the condition number of the linearization of a scaled matrix polynomial
is bounded by the condition number of the
scaled matrix polynomial times
the condition number of these coefficients.
Our results show that when these coefficients
are well conditioned the eigenpairs can be computed without any numerical difficulty.
These analysis is supported by the experiments which are provided at the end of
the paper
Spectral element method for parabolic interface problems: Regularity estimates, stability theorem and error estimate
Get PDFIn this paper, an spectral element method with least-square formulation for parabolic interface problem will be presented. The regularity result of the parabolic interface problem is proven for non-homogeneous interface data.
The differentiability estimates and the main stability estimate theorem, using non-conforming spectral element functions, are proven. Error estimates are derived for and versions of the proposed method
On some information geometric approaches to cyber security
No full textVarious contexts of relevance to cyber security involve the analysis of data
that has a statistical character and in some cases the extraction of particular
features from datasets of fitted distributions or empirical frequency distributions.
Such statistics, for example,
may be collected in the automated monitoring of IP-related data
during accessing or attempted accessing of web-based resources, or may be
triggered through an alert for suspected cyber attacks.
Information geometry provides a Riemannian geometric framework in which to
study smoothly parametrized families of probability density functions, thereby
allowing the use of geometric tools to study statistical features of processes
and possibly the representation of features that are associated with attacks.
In particular, we can obtain mutual distances among members of the family
from a collection of datasets, allowing for example measures of departures
from Poisson random or uniformity, and discrimination between nearby distributions.
Moreover, this allows the representation of large numbers of datasets
in a way that respects any topological features in the frequency data
and reveals subgroupings in the datasets using dimensionality reduction.
Here some results are reported on statistical and information geometric studies
concerning pseudorandom sequences, encryption-decryption timing analyses,
comparisons of nearby signal distributions and departure from uniformity for
evaluating obscuring techniques
Combining Analogical Support in Pure Inductive Logic
Get PDFWe investigate the relative probabilistic support afforded by the combination of two analogies based on possibly different, structural similarity (as opposed to e.g. shared predicates) within the context of Pure Inductive Logic and under the assumption of Language Invariance. We show that whilst repeated analogies grounded on the same structural similarity only strengthen the probabilistic support this need not be the case when combining analogies based on different structural similarities. That is, two analogies may provide less support than each would individually
A New Analysis of Iterative Refinement and its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems
Get PDFIterative refinement is a long-standing technique for improving the accuracy
of a computed solution to a nonsingular linear system
obtained via LU factorization.
It makes use of residuals computed in extra precision,
typically at twice the working precision,
and existing results guarantee convergence if the matrix
has condition number safely less than the reciprocal of the unit roundoff, .
We identify a mechanism that allows iterative refinement to produce
solutions with normwise relative error of order
to systems with condition numbers of order or
larger, provided that the update equation is solved with a relative
error sufficiently less than .
A new rounding error analysis is given and its implications are analyzed.
Building on the analysis,
we develop a GMRES-based iterative refinement method (GMRES-IR)
that makes use of the computed LU factors as preconditioners.
GMRES-IR exploits the fact that even if
is extremely ill conditioned the LU factors contain enough information
that preconditioning can greatly reduce the condition
number of .
Our rounding error analysis and numerical experiments show that GMRES-IR
can succeed where standard refinement fails, and that it can
provide accurate solutions to systems with condition numbers of order
and greater.
Indeed in our experiments with such matrices---both random and from the
University of Florida Sparse Matrix Collection---GMRES-IR
yields a normwise relative error of order in at most steps
in every case
Second Workshop on Batched, Reproducible, and Reduced Precision BLAS
Get PDFA summary of the second workshop on Batched, Reproducible, and Reduced Precision BLAS