MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Adaptive Precision in Block-Jacobi Preconditioning for Iterative Sparse Linear System Solvers
Get PDFWe propose an adaptive scheme to reduce communication overhead caused by data movement by selectively storing the diagonal blocks of a block Jacobi preconditioner in different precision formats (half, single, or double). This specialized preconditioner can then be combined with any Krylov subspace method for the solution of sparse linear systems to perform all arithmetic in double precision. We assess the effects of the adaptive-precision preconditioner on the iteration count and data transfer cost of a preconditioned conjugate gradient solver. A preconditioned conjugate gradient method is, in general, a memory-bound algorithm, and therefore its execution time and energy consumption are largely dominated by the costs of accessing the problem's data in memory. Given this observation, we propose a model that quantifies the time and energy savings of our approach based on the assumption that these two costs depend linearly on the bit length of a floating point number. Furthermore, we use a number of test problems from the SuiteSparse matrix collection to estimate the potential benefits of the adaptive block-Jacobi preconditioning scheme
Multiprecision Algorithms for Computing the Matrix Logarithm
Get PDFTwo algorithms are developed for computing the matrix logarithm in floating point arithmetic of any specified precision. The backward error-based approach used in the state of the art inverse scaling and squaring algorithms does not conveniently extend to a multiprecision environment, so instead we choose algorithmic parameters based on a forward error bound. We derive a new forward error bound for Pad\'{e} approximants that for highly nonnormal matrices can be much smaller than the classical bound of Kenney and Laub. One of our algorithms exploits a Schur decomposition while the other is transformation-free and uses only the computational kernels of matrix multiplication and the solution of multiple right-hand side linear systems. For double precision computations the algorithms are competitive with the state of the art algorithm of Al-Mohy, Higham, and Relton implemented in \texttt{logm} in MATLAB\@. They are intended for computing environments providing multiprecision floating point arithmetic, such as Julia, MATLAB via the Symbolic Math Toolbox or the Multiprecision Computing Toolbox, or Python with the mpmath or SymPy packages. We show experimentally that the algorithms behave in a forward stable manner over a wide range of precisions, unlike existing alternatives
The Nonlinear Eigenvalue Problem
Get PDFNonlinear eigenvalue problems arise in a variety of science and engineering applications and in the past ten years there have been numerous breakthroughs in the development of numerical methods. This article surveys nonlinear eigenvalue problems associated with matrix-valued functions which depend nonlinearly on a single scalar parameter, with a particular emphasis on their mathematical properties and available numerical solution techniques. Solvers based on Newton's method, contour integration, and sampling via rational interpolation are reviewed. Problems of selecting the appropriate parameters for each of the solver classes are discussed and illustrated with numerical examples. This survey also contains numerous MATLAB code snippets that can be used for interactive exploration of the discussed methods
A note on *-conditioning
Get PDFThe purpose of this note is to prove a technical result concerning a variation on Bayesian conditioning which needs be referenced in some other papers
The Design and Performance of Batched BLAS on Modern High-Performance Computing Systems
Get PDFA current trend in high-performance computing is to decompose a large linear algebra prob-
lem into batches containing thousands of smaller problems, that can be solved independently,
before collating the results. To standardize the interface to these routines, the community is
developing an extension to the BLAS standard (the batched BLAS), enabling users to perform
thousands of small BLAS operations in parallel whilst making efficient use of their hardware.
We discuss the benefits and drawbacks of the current batched BLAS proposals and perform
a number of experiments, focusing on GEMM, to explore their affect on the performance. In
particular we analyze the effect of novel data layouts which, for example, interleave the ma-
trices in memory to aid vectorization and prefetching of data. Utilizing these modifications
our code outperforms both MKL and CuBLAS by up to 6 times on the self-hosted Intel KNL
(codenamed Knights Landing) and Kepler GPU architectures, for large numbers of DGEMM
operations using matrices of size 2 � 2 to 20 � 20
Persistent homology for low-complexity models
Get PDFWe show that recent results on randomized dimension reduction schemes that exploit structural properties of data can be applied in the context of persistent homology. In the spirit of compressed sensing, the dimension reduction is determined by the Gaussian width of a structure associated to the data set, rather than its size. The Gaussian width also turns out to be useful for studying the complexity of other methods for approximating persistent homology
Conversions between barycentric, RKFUN, and Newton representations of rational interpolants
Get PDFWe derive explicit formulas for converting between rational interpolants in barycentric, rational Krylov (RKFUN), and Newton form. We show applications of these conversions when working with rational approximants produced by the AAA algorithm [Y. Nakatsukasa, O. Sète, L. N. Trefethen, arXiv preprint 1612.00337, 2016] within the Rational Krylov Toolbox and for the solution of nonlinear eigenvalue problems
Inverse Problems and Control for Lung Dynamics
Get PDFMechanical ventilation is vital for the treatment of patients in respiratory intensive care and can be life saving. However, the risks of regional pressure gradients and over-distension must be balanced with the need to maintain function. For these reasons mechanical ventilation can benefit from the regional information provided by bedside imaging such as electrical impedance tomography (EIT).
In this thesis we develop and test methods to retrieve clinically meaningful measures of lung function from EIT and examine the feasibility of closing the feedback loop to enable EIT-guided control of mechanical ventilation. Working towards this goal we develop a reconstruction algorithm capable of providing fast absolute values of conductivity from EIT measurements. We couple the resulting conductivity time series to a compartmental ordinary differential equation (ODE) model of lung function in order to recover regional parameters of elastance and airway resistance. We then demonstrate how these parameters may be used to generate optimised pressure controls for mechanical ventilation that expose the lungs to minimal gradients of pressure and are stable with respect to EIT measurement errors.
The EIT reconstruction algorithm we develop is capable of producing low dimensional absolute values of conductivity in real time after a limited additional setup time. We show that this algorithm retains the ability to give fast feedback on regional lung changes. We also describe methods of improving computational efficiency for general Gauss-Newton type EIT algorithms.
In order to couple reconstructed conductivity time series to our ODE model we describe and test the recovery of regional ventilation distributions through a process of regularised differentiation. We prove that the parameters of our ODE model are recoverable from these ventilation distributions apart from the degenerate case where all compartments have the same parameters. We then test this recovery process under varying levels of simulated EIT measurement and modelling errors.
Finally we examine the ODE lung model using control theory. We prove that the ODE model is controllable for a wide range of parameter values and link controllability to observable ventilation patterns in the lungs. We demonstrate the generation and optimisation of pressure controls with minimal time gradients and provide a bound on the resulting magnitudes of these pressures. We then test the control generation process using ODE parameter values recovered through EIT simulations at varying levels of measurement noise.
Through this work we have demonstrated that EIT reconstructions can be of benefit to the control of mechanical ventilation
Adaptive Precision in Block-Jacobi Preconditioning for Iterative Sparse Linear System Solvers
Get PDFWe propose an adaptive scheme to reduce communication overhead caused by data movement by selectively storing the diagonal blocks of a block Jacobi preconditioner in different precision formats (half, single, or double). This specialized preconditioner can then be combined with any Krylov subspace method for the solution of sparse linear systems to perform all arithmetic in double precision. We assess the effects of the adaptive-precision preconditioner on the iteration count and data transfer cost of a preconditioned conjugate gradient solver. A preconditioned conjugate gradient method is, in general, a memory-bound algorithm, and therefore its execution time and energy consumption are largely dominated by the costs of accessing the problem's data in memory. Given this observation, we propose a model that quantifies the time and energy savings of our approach based on the assumption that these two costs depend linearly on the bit length of a floating point number. Furthermore, we use a number of test problems from the SuiteSparse matrix collection to estimate the potential benefits of the adaptive block-Jacobi preconditioning scheme
Almost Engel finite and profinite groups
Get PDFLet be an element of a group . For a positive integer , let be the subgroup generated by all commutators over , where is repeated times. We prove that if is a profinite group such that for every there is such that is finite, then has a finite
normal subgroup such that is locally nilpotent. The proof uses the Wilson--Zelmanov theorem saying that Engel profinite groups are locally nilpotent. In the case of a finite group , we prove that if, for some , for all , then the order of the nilpotent residual is bounded in terms of