MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD
Get PDFSpectral divide and conquer algorithms solve the eigenvalue problem for all the
eigenvalues and eigenvectors by recursively computing an invariant subspace for a subset of the
spectrum and using it to decouple the problem into two smaller subproblems. A number of such
algorithms have been developed over the last forty years, often motivated by parallel computing
and, most recently, with the aim of achieving minimal communication costs. However, none of the
existing algorithms has been proved to be backward stable, and they all have a signicantly higher
arithmetic cost than the standard algorithms currently used. We present new spectral divide and
conquer algorithms for the symmetric eigenvalue problem and the singular value decomposition that
are backward stable, achieve lower bounds on communication costs recently derived by Ballard,
Demmel, Holtz, and Schwartz, and have operation counts within a small constant factor of those for
the standard algorithms. The new algorithms are built on the polar decomposition and exploit the
recently developed QR-based dynamically weighted Halley algorithm of Nakatsukasa, Bai, and Gygi,
which computes the polar decomposition using a cubically convergent iteration based on the building
blocks of QR factorization and matrix multiplication. The algorithms have great potential for
ecient, numerically stable computations in situations where the cost of communication dominates
the cost of arithmetic
Duality of matrix pencils and linearizations
Get PDFIn this paper we introduce a duality relation on matrix pencils and show that it is a useful tool in the theory of linearizations of matrix polynomials. We first completely characterize the Kronecker form of dual pencils. Exploiting this result, we then study the behaviour under duality of the spectral structures, including eigenvalues, eigenvectors, Wong chains, and minimal bases. We also present several applications of the new concept, including: constraints on the minimal indices of singular Hamiltonian and symplectic pencils, new sufficient conditions under which pencils in L1, L2 linearization spaces are strong linearizations, a new perspective on Fiedler pencils, a link between the Möller-Stetter theorem and some linearizations of matrix polynomials
Classification of symmetry groups for planar n-body choreographies
Get PDFSince the foundational work of Chenciner and Montgomery in 2000 there has been a great deal of interest in choreographic solutions of the n-body problem: periodic motions where the n bodies all follow one another at regular intervals along a closed path. The principal approach combines variational methods with symmetry properties. In this paper, we give a systematic treatment of the symmetry aspect. In the first part we classify all possible symmetry groups of planar n-body, collision-free choreographies. These symmetry groups fall in to 2 infinite families and, if n is odd, three exceptional groups. In the second part we develop the equivariant fundamental group and use it to determine the topology of the space of loops with a given symmetry, which we show is related to certain cosets of the pure braid group in the full braid group, and to centralizers of elements of the corresponding coset
Continuous-Time Revenue Managment in Carparks - Part two: Refining the PDE
No full textIn this paper, we study optimal revenue management applied to carparks, with the primary objective
to maximize revenues under a continuous-time framework. This work is an extension to Papayiannis et al (2012) where the authors developed a Partial Differential Equation (PDE) model that could solve for the rate at which cash is generated through an infinitesimal time. However, in practice, carpark managers charge customers per day or per hour which is a finite period of time. Unfortunately, this situation was currently not captured by this previous work. Therefore, our current work attempts to reformulate the existing PDE in a way that it does capture the revenue that is generated within any finite time interval of length . The new model is compared against the Monte Carlo (MC) approach for several choices of ; the results are remarkable as the improvement in computation speed and efficiency are significant. Since, the algorithm in the PDE still does not solve the `exact' problem, a method is proposed to marry the benefits of the PDE with those of the MC approach. Our results are prominent as the optimal values generated in this case have shown to be extremely close to the MC ones while the computation times are kept to a minimum
Detecting the Causes of Ill-Conditioning in Structural Finite Element Models
No full textIn 2011, version 8.6 of the finite element-based structural analysis package Oasys GSA was released. A new feature in this release was the estimation of the -norm condition number of the stiffness matrix of structural models by using a -norm estimation algorithm of Higham and Tisseur to estimate . The condition estimate is reported as part of the information provided to engineers when they carry out linear/static analysis of models and a warning is raised if the condition number is found to be large. The inclusion of this feature prompted queries from users asking how the condition number impacted the analysis and, in cases where the software displayed an ill conditioning warning, how the ill conditioning could be ``fixed''. We describe a method that we have developed and implemented in the software that enables engineers to detect sources of ill conditioning in their models and rectify them. We give the theoretical background and illustrate our discussion with real-life examples of structural models to which this tool has been applied and found useful. Typically, condition numbers of stiffness matrices reduce from for erroneous models to or less for the corrected model
Point vortices on the hyperboloid
Get PDFIn Hamiltonian systems with symmetry, many previous studies have centred their attention on compact symmetry groups, but relatively little is known about the effects of noncompact groups. This thesis investigates the properties of the system N point vortices on the hyperbolic plane H2, which has noncompact symmetry SL(2;R).
The Poisson Hamiltonian structure of this dynamical system is presented and relative equilibria conditions are found. We also describe the trajectories of equilibria with momentum value not equal to zero. Finally, stability criteria are found for a number of cases, focusing on N = 2 and 3. These results are placed in with the study of point vortices on the sphere, which has compact symmetry
Geometric structure in smooth dual and local Langlands conjecture
No full textThis expository article is based on the Takagi lectures given by the second author in November, 2012.
Topics in the lectures:
#1. Review of the LL (Local Langlands) conjecture.
#2. Statement of the ABPS(Aubert-Baum-Plymen-Solleveld) conjecture. #3. Brief indication of the proof that for any connected split reductive p-adic group G both ABPS and LL are valid throughout the principal series of G
LU FACTORIZATION WITH PANEL RANK REVEALING PIVOTING AND ITS COMMUNICATION AVOIDING VERSION
No full textWe present block LU factorization with panel rank revealing pivoting (block LU_PRRP), a decomposition algorithm based on strong rank revealing QR panel factorization. Block LU_PRRP is more stable than Gaussian elimination with partial pivoting (GEPP), with a theoretical upper bound of the growth factor of , where is the size of the panel used during the block factorization, is a parameter of the strong rank revealing QR factorization, is the number of columns of the matrix, and for simplicity we assume that n is a multiple of b. We also assume throughout the paper that . For example, if the size of the panel is , and , then , where is the upper bound of the growth factor of GEPP. Our extensive numerical experiments show that the new factorization scheme is as numerically stable as GEPP in practice, but it is more resistant to pathological cases. The block LU_PRRP factorization does only additional floating point operations compared to GEPP. We also present block CALU_PRRP, a version of block LU_PRRP that minimizes communication and is based on tournament pivoting, with the selection of the pivots at each step of the tournament being performed via strong rank revealing QR factorization. Block CALU_PRRP is more stable than CALU, the communication avoiding version of GEPP, with a theoretical upper bound of the growth factor of , where is the height of the reduction tree used during tournament pivoting. The upper bound of the growth factor of CALU is . Block CALU_PRRP is also more stable in practice and is resistant to pathological cases on which GEPP and CALU fail
Triangularizing Quadratic Matrix Polynomials
No full textWe show that any regular quadratic matrix polynomial can be reduced to an upper
triangular quadratic matrix polynomial over the complex numbers
preserving the finite and infinite elementary divisors.
We characterize the real quadratic matrix polynomials that are
triangularizable over the real numbers and show that those that are
not triangularizable are quasi-triangularizable
with diagonal blocks of sizes and .
We also derive complex and real Schur-like theorems for linearizations of
quadratic matrix polynomials with nonsingular leading coefficients.
In particular, we show that for any monic linearization \l I+A of an
quadratic matrix polynomial there exists a nonsingular matrix defined in terms of
orthonormal vectors that transforms to a companion
linearization of a (quasi)-triangular quadratic matrix polynomial.
This provides the foundation for designing numerical algorithms for the
reduction of quadratic matrix polynomials to upper (quasi)-triangular form
Duality of matrix pencils and linearizations
No full textIn this paper we consider a duality relation on matrix pencils and show that it is a useful tool in the theory of linearizations of matrix polynomials.
Exploiting a result that completely characterizes the Kronecker form of dual pencils, we study the behaviour under duality of the spectral structures,
including eigenvalues, eigenvectors, Wong chains, and minimal bases. We also present several new applications of this concept, including: constraints on the minimal indices of singular Hamiltonian and symplectic pencils, new sufficient conditions under which pencils in L1, L2 linearization spaces are strong linearizations, a new perspective on Fiedler pencils, a link between the Möller-Stetter theorem and some linearizations of matrix polynomials