MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
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
Incomplete LU preconditioner based on max-plus approximation of LU factorization
No full textWe present a new method for the a priori approximation of the orders of magnitude of the entries in the LU factors of a complex or real matrix . This approximation can be used to quickly determine the positions of the largest entries in the LU factors of and these positions can then be used as the sparsity pattern for an incomplete LU factorization preconditioner. Our method uses max-plus algebra and is based solely on the moduli of the entries of . We also present techniques for predicting which permutation matrices will be chosen by Gaussian elimination with partial pivoting. We exploit the strong connection between the field of Puiseux series and the max-plus semiring to prove properties of the max-plus LU factors.
Experiments with a set of test matrices from the University of Florida sparse matrix collection show that our max-plus LU preconditioners outperform traditional level of fill methods and have similar performance to those preconditioners computed with more expensive threshold-based methods
A new restriction for initially stressed elastic solids
Get PDFWe introduce a fundamental restriction on the strain energy function and stress tensor for initially stressed elastic solids. The restriction applies to strain energy functions W that are explicit functions of the elastic deformation gradient F and initial stress tau, that is W := W (F, tau). The restriction is a consequence of energy conservation and ensures that the predicted stress and strain energy do not
depend upon an arbitrary choice of reference configuration. We call this restriction initial stress reference independence (ISRI). It transpires that most strain energy functions found in the literature do not satisfy ISRI, and may therefore lead to unphysical behaviour, which we illustrate through a simple example. To remedy this shortcoming, we derive three strain energy functions that do
satisfy the restriction. We also show that using initial strain (often from a virtual configuration) to model initial stress leads to strain energy functions that automatically satisfy ISRI. Finally, we reach the following important result: ISRI reduces the number of unknowns in the linear stress tensor for initially stressed solids. This new way of reducing the linear stress may open new
pathways for the non-destructive determination of initial stresses through ultrasonic experiments, among others
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
Explicit symmetry breaking and Hamiltonian systems
Get PDFThe central topic of this thesis is the study of persistence of stationary motion under explicit symmetry breaking perturbations in Hamiltonian systems. Explicit
symmetry breaking occurs when a dynamical system having a certain symmetry group is perturbed in a way that the perturbation preserves only some symmetries of the original system. We give a geometric approach to study this phenomenon in the setting of equivariant Hamiltonian systems. A lower bound for the number of orbits of equilibria and orbits of relative equilibria which persist after a small perturbation is given. This bound is given in terms of the equivariant Lyusternik-Schnirelmann category of the group orbit. We also find a localization formula for
this category in terms of the closed orbit-type strata. We show that this formula holds for topological spaces admitting a particular cover, made of tubular neighbourhoods
of their minimal orbit-type strata. Finally we propose a construction of symplectic slices for subgroup actions
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
Reduction of matrix polynomials to simpler forms
Get PDFA square matrix can be reduced to simpler form via similarity transformations. Here ``simpler form'' may refer to diagonal (when possible), triangular (Schur), or Hessenberg form. Similar reductions exist for matrix pencils if we consider general equivalence transformations instead of similarity transformations. For both matrices and matrix pencils, well-established algorithms are available for each reduction, which are useful in various applications. For matrix polynomials, unimodular transformations can be used to achieve the reduced forms but we do not have a practical way to compute them. In this work we introduce a practical means to reduce a matrix polynomial with nonsingular leading coefficient to a simpler (diagonal, triangular, Hessenberg)
form while preserving the degree and the eigenstructure.
The key to our approach is to work with structure preserving
similarity transformations applied to a linearization of the matrix polynomial instead of unimodular transformations applied directly to the matrix polynomial. As an applications, we illustrate how to use these reduced forms to solve parameterized linear systems
A Nonlinear ParaExp Algorithm
Get PDFWe propose and analyse a variant of the ParaExp algorithm for nonlinear initial value problems. We show that this algorithm is mathematically equivalent to a parareal iteration where the coarse integrator solves linear subproblems on overlapping time intervals. A numerical example with a nonlinear wave equation illustrates the convergence behaviour
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
A Block Krylov Method to Compute the Action of the Frechet Derivative of a Matrix Function on a Vector with Applications to Condition Number Estimation
Get PDFWe design a block Krylov method to compute the action of the Fr�©chet derivative of a matrix function on a vector using only matrix-vector products, i.e., the derivative of when is subject to a perturbation in the direction . The algorithm we derive is especially effective when the direction matrix in the derivative is of low rank, while there are no such restrictions on . Our results and experiments are focused mainly on Fr�©chet derivatives with rank 1 direction matrices. Our analysis applies to all functions with a power series expansion convergent on a subdomain of the complex plane which, in particular, includes the matrix exponential. We perform an a priori error analysis of our algorithm to obtain rigorous stopping criteria. Furthermore, we show how our algorithm can be used to estimate the 2-norm condition number of efficiently. Our numerical experiments show that our new algorithm for computing the action of a Fr�©chet derivative typically requires a small number of iterations to converge and (particularly for single and half precision accuracy) is significantly faster than alternative algorithms. When applied to condition number estimation, our experiments show that the resulting algorithm can detect ill-conditioned problems that are undetected by competing algorithms