MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
The Power of Bidiagonal Matrices
Full text linkBidiagonal matrices are widespread in numerical linear algebra, not least because of their use in the standard algorithm for computing the singular value decomposition and their appearance as LU factors of tridiagonal matrices. We show that bidiagonal matrices have a number of interesting properties that make them powerful tools in a variety of problems, especially when they are multiplied together. We show that the inverse of a product of bidiagonal matrices is insensitive to small componentwise relative perturbations in the factors if the factors or their inverses are nonnegative. We derive componentwise rounding error bounds for the solution of a linear system , where or is a product of bidiagonal matrices, showing that strong results are obtained when the are nonnegative or have a checkerboard sign pattern. We show that given the \fact\ of an totally nonnegative matrix into the product of bidiagonal matrices, \normo{A^{-1}} can be computed in flops and that in floating-point arithmetic the computed result has small relative error, no matter how large \normo{A^{-1}} is. We also show how factorizations involving bidiagonal matrices of some special matrices, such as the Frank matrix and the Kac--Murdock--Szeg\"o matrix, yield simple proofs of the total nonnegativity and other properties of these matrices
Mixed-Precision Paterson--Stockmeyer Method for Evaluating Polynomials of Matrices
Full text linkThe Paterson--Stockmeyer method is an evaluation scheme for matrix polynomials with scalar coefficients that arise in many state-of-the-art algorithms based on polynomial or rational approximation, for example, those for computing transcendental matrix functions. We derive a mixed-precision version of the Paterson--Stockmeyer method that
is particularly useful for evaluating matrix polynomials with scalar coefficients of decaying magnitude.
The key idea is to perform computations on data of small magnitude in low precision, and rounding error analysis is provided for the use of lower-than-working precisions.
We focus on the evaluation of the Taylor approximants of the matrix exponential and show the applicability of our method to the existing scaling and squaring algorithms, particularly when the norm of the input matrix (which in practical algorithms is often scaled towards to origin) is sufficiently small. We also demonstrate through experiments the general applicability of our method to the computation of the polynomials from the Pad\'e approximant of the matrix exponential and the Taylor approximant of the matrix cosine.
Numerical experiments show our mixed-precision Paterson--Stockmeyer algorithms can be more efficient
than its fixed-precision counterpart while delivering the same level of accuracy
On the Cross-Shaped Matrices
Full text linkA cross-shaped matrix X\in\C^{n\times n} has nonzero elements located on the main diagonal and the anti-diagonal, so that the sparsity pattern has the shape of a cross. It is shown that can be factorized into products of identity-plus-rank-two matrices and can be symmetrically permuted to block diagonal form with diagonal blocks and, if is odd, a diagonal block. Exploiting these properties we derive explicit formulae for its determinant, inverse, and characteristic polynomial
On the Cross-Shaped Matrices
Full text linkA cross-shaped matrix X\in\C^{n\times n} has nonzero elements located on the main diagonal and the anti-diagonal, so that the sparsity pattern has the shape of a cross. It is shown that can be factorized into products of identity-plus-rank-two matrices and can be symmetrically permuted to block diagonal form with diagonal blocks and, if is odd, a diagonal block. Exploiting these properties we derive explicit formulae for its determinant, inverse, and characteristic polynomial
Modelling and classifying joint trajectories of self-reported mood and pain in a large cohort study
No full textIt is well-known that mood and pain interact with each other, however individual-level variability in this relationship has been less well quantified than overall associations between low mood and pain. Here, we leverage the possibilities presented by mobile health data, in particular the “Cloudy with a Chance of Pain” study, which collected longitudinal data from the residents of the UK with chronic pain conditions. Participants used an App to record self-reported measures of factors including mood, pain and sleep quality. The richness of these data allows us to perform model-based clustering of the data as a mixture of Markov processes. Through this analysis we discover four endotypes with distinct patterns of co-evolution of mood and pain over time. The differences between endotypes are sufficiently large to play a role in clinical hypothesis generation for personalised treatments of comorbid pain and low mood
Randomized Low Rank Matrix Approximation: Rounding Error Analysis and a Mixed Precision Algorithm
Full text linkThe available error bounds for randomized algorithms for computing a low rank approximation to a matrix assume exact arithmetic. Rounding errors potentially dominate the approximation error, though, especially when the algorithms are run in low precision arithmetic. We give a rounding error analysis of the method that computes a randomized rangefinder and then computes an approximate singular value decomposition approximation. Our analysis covers the basic method and the power iteration for the fixed-rank problem, as well as the power iteration for the fixed-precision problem. We give both worst-case and probabilistic rounding error bounds as functions of the problem dimensions and the rank. The worst-case bounds are pessimistic, but the probabilistic bounds are reasonably tight and still reliably bound the error in practice. We also propose a mixed precision version of the algorithm that offers potential speedups by gradually decreasing the precision during the execution of the algorithm
A Parametrization of Structure-Preserving Transformations for Matrix Polynomials
No full textGiven a matrix polynomial of degree and the associated vector space of pencils \DLP(A) described in
Mackey, Mackey, Mehl, and Mehrmann [SIAM J. Matrix Anal. Appl., 28 (2006), pp. 971-1004], we construct a parametrization for the set of left and right transformations that preserve the block structure of such pencils, and hence produce a new matrix polynomial \At(\lambda) that is still of degree and is unimodularly equivalent to . We refer to such left and right transformations as structure-preserving
transformations (SPTs). Unlike previous work on SPTs, we do not require the leading matrix coefficient of to be nonsingular. We show that additional constraints on the parametrization lead to SPTs that also preserve extra structures in such as symmetric, alternating,
and -palindromic structures. Our parametrization allows easy construction of SPTs that are low-rank modifications of the identity matrix. The latter transform into an equivalent matrix polynomial \At(\lambda) whose th matrix coefficient \At_j is a low-rank modification of . We expect such SPTs to be one of the key tools for developing algorithms that reduce a matrix polynomial to Hessenberg form or tridiagonal form in a finite number of steps and without the use of a linearization
An approach to protein structure using information geometry
Full text linkIn the light of recent structural developments in DNA structural diversity crystallographic studies and the Protein Data Bank*, this note is intended to draw attention to an interesting feature of the ordering of amino acids along protein chains. They all exhibited clustering compared to a random
distribution, so there is a stable long range ordering that is unexpected. To date
we have no clear explanation of why this should be the case.
* https://doi.org/10.1016/j.jbc.2021.100553
Probabilistic Rounding Error Analysis of Householder QR Factorization
Full text linkWhen an matrix is premultiplied by a product of
Householder matrices the worst-case normwise rounding error bound
is proportional to , where is the unit roundoff. We
prove that this bound can be replaced by one proportional to
that holds with high probability if the rounding
errors are mean independent and of mean zero, under the
assumption that a certain bound holds with probability . The
proof makes use of a matrix concentration inequality. In
particular, this result applies to Householder QR factorization.
The same square rooting of the error constant applies to
two-sided transformations by Householder matrices and hence to
standard QR-type algorithms for computing eigenvalues and
singular values. It also applies to Givens QR factorization.
These results complement recent probabilistic rounding error
analysis results for inner-product based algorithms and show that
the square rooting effect is widespread in numerical linear
algebra. Our numerical experiments, which make use of a new
backward error formula for QR factorization, show that the
probabilistic bounds give a much better indicator of the actual
backward errors and their rate of growth than the worst-case
bounds
Hamilton's Discovery of the Quaternions and Creativity in Mathematics
Full text linkCreativity can be defined as the process of forming new patterns from pre-existing component parts. As an illustration, we explain how Hamilton's discovery of the quaternions, and Cayley and Graves's subsequent discoveries of the octonions, could have resulted from considering the properties of complex numbers and asking for each one, ``how might this be different?''. We give some general suggestions on differences to look for and explain why creativity can be much richer when people work in small groups rather than individually