MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
A New Scaling and Squaring Algorithm for the Matrix Exponential
Get PDFThe scaling and squaring method for the matrix exponential is based on the approximation , where is the Pad\'e approximant to and the integers and are to be chosen. Several authors have identified a weakness of existing scaling and squaring algorithms termed overscaling, in which a value of much larger than necessary is chosen, causing a loss of accuracy in floating point arithmetic. Building on the scaling and squaring algorithm of Higham [{\em SIAM J. Matrix Anal. Appl.}, 26\penalty0 (4):\penalty0 1179--1193, 2005], which is used by MATLAB's \texttt{expm}, we derive a new algorithm that alleviates the overscaling problem. Two key ideas are employed. The first, specific to triangular matrices, is to compute the diagonal elements in the squaring phase as exponentials instead of from powers of . The second idea is to base the backward error analysis that underlies the algorithm on members of the sequence instead of , since for non-normal matrices it is possible that is much smaller than , and indeed this is likely when overscaling occurs in existing algorithms. The terms are estimated without computing powers of by using a matrix 1-norm estimator in conjunction with a bound of the form that holds for certain fixed and less than . The improvements to the truncation error bounds have to be balanced by the potential for a large to cause inaccurate evaluation of in floating point arithmetic. We employ rigorous error bounds along with some heuristics to ensure that rounding errors are kept under control. Our numerical experiments show that the new algorithm generally provides accuracy at least as good as the existing algorithm of Higham at no higher cost, while for matrices that are triangular or cause overscaling it usually yields significant improvements in accuracy, cost, or both
A Framework for Analyzing Nonlinear Eigenproblems and Parametrized Linear Systems
Get PDFAssociated with an matrix polynomial of degree , , are the eigenvalue problem and the linear system problem , where in the latter case is to be computed for many values of the parameter . Both problems can be solved by conversion to an equivalent problem or that is linear in the parameter or . This linearization process has received much attention in recent years for the eigenvalue problem, but it is less well understood for the linear system problem. We develop a framework in which more general versions of both problems can be analyzed, based on one-sided factorizations connecting a general nonlinear matrix function to a simpler function , typically a polynomial of degree 1 or 2. Our analysis relates the solutions of the original and linearized problems and in the linear system case indicates how to choose and recover from . For the eigenvalue problem this framework includes many special cases studied in the literature, including the vector spaces of pencils and recently introduced by Mackey, Mackey, Mehl, and Mehrmann and a class of rational problems. We use the framework to investigate the conditioning and stability of the parametrized linear system and thereby study the effect of scaling, both of the original polynomial and of the pencil . Our results identify situations in which scaling can potentially greatly improve the conditioning and stability and our numerical results show that dramatic improvements can be achieved in practice
The Canonical Generalized Polar Decomposition
Get PDFThe polar decomposition of a square matrix has been generalized by several authors to scalar products on or given by a bilinear or sesquilinear form. Previous work has focused mainly on the case of square matrices, sometimes with the assumption of a Hermitian scalar product. We introduce the canonical generalized polar decomposition , defined for general matrices , where is a partial -isometry and is -selfadjoint with nonzero eigenvalues lying in the open right half-plane, and the nonsingular matrices and define scalar products on and , respectively. We derive conditions under which a unique decomposition exists and show how to compute the decomposition by matrix iterations. Our treatment derives and exploits key properties of -partial isometries and orthosymmetric pairs of scalar products, and also employs an appropriate generalized Moore--Penrose pseudoinverse. We relate commutativity of the factors in the canonical generalized polar decomposition to an appropriate definition of normality. We also consider a related generalized polar decomposition , defined only for square matrices and in which is an automorphism; we analyze its existence and the uniqueness of the selfadjoint factor when is singular
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
Get PDFA 25-year old and somewhat neglected algorithm of Crawford and Moon
attempts to determine
whether a given Hermitian matrix pair is definite by exploring the
range of the function
,
which is a subset of the unit circle.
We revisit the algorithm and show that
with suitable modifications and careful attention to implementation
details it provides a reliable and efficient means of testing definiteness.
A clearer derivation of the basic algorithm is given
that emphasizes an arc expansion viewpoint
and makes no assumptions about the definiteness of the pair.
Convergence of the algorithm is proved for all ), definite or not.
It is shown that proper handling of three details of the algorithm is
crucial to the efficiency and reliability:
how the midpoint of an arc is computed,
whether shrinkage of an arc is permitted,
and how directions of negative curvature are computed.
For the latter, several variants of
Cholesky factorization with complete pivoting are explored and the benefits of
pivoting demonstrated.
The overall cost of our improved algorithm is typically just a few Cholesky
factorizations.
Applications of the algorithm are described to testing the hyperbolicity of a
Hermitian quadratic matrix polynomial,
constructing conjugate gradient methods for sparse linear systems in saddle point form,
and computing the Crawford number of the pair via a quasiconvex univariate
minimization problem
A Schanuel Property for Exponetially Transcendental Powers
Get PDFWe prove the analogue of Schanuel’s conjecture for raising to the
power of an exponentially transcendental real number. All but countably many
real numbers are exponentially transcendental. We also give a more general
result for several powers in a context which encompasses the complex case
Multiplicative structure of 2x2 tropical matrices
Get PDFWe study the algebraic structure of the semigroup of all 2x2 tropical matrices under multiplication. Using ideas from tropical geometry, we give a complete description of Green's relations and the idempotents and maximal subgroups of this semigroup
Geometric structure in the principal series of the p-adic group G_2
Get PDFIn the representation theory of reductive -adic groups
, the issue of reducibility of induced representations is an issue of great intricacy. It is our contention, expressed as a conjecture in [3], that there exists a simple geometric structure underlying this intricate theory.
We will illustrate here the conjecture with some detailed
computations in the principal series of the exceptional group .
A feature of this article is the role played by cocharacters
attached to two-sided cells in certain extended
affine Weyl groups.
The quotient varieties which occur in the Bernstein programme are replaced by extended quotients. We form the disjoint union of all these extended quotient varieties. We conjecture that, after a simple algebraic deformation, the space is a model of the smooth dual . In this respect, our programme is a conjectural refinement of the Bernstein programme.
The algebraic deformation is controlled by the cocharacters
. The cocharacters themselves appear to be closely
related to Langlands parameters
Computing a Nearest Correlation Matrix with Factor Structure
Get PDFAn correlation matrix has factor structure if its off-diagonal agrees with that of a rank matrix. Such correlation matrices arise, for example, in factor models of collateralized debt obligations (CDOs) and multivariate time series. We analyze the properties of these matrices and, in particular, obtain an explicit formula for the rank in the one factor case. Our main focus is on the nearness problem of finding the nearest factor correlation matrix C(X) = \diag(I-XX^T) + XX^T to a given symmetric matrix, subject to natural nonlinear constraints on the elements of the matrix , where distance is measured in the Frobenius norm. For a special one parameter case we obtain an explicit solution. For the general factor case we obtain the gradient and Hessian of the objective function and derive an instructive result on the positive definiteness of the Hessian when . We investigate several numerical methods for solving the nearness problem: the alternating directions method; a principal factors method used by Anderson, Sidenius, and Basu in the CDO application, which we show is equivalent to the alternating projections method and lacks convergence results; the spectral projected gradient method of Birgin, Mart{\'\i}nez, and Raydan; and Newton and sequential quadratic programming methods. The methods differ in whether or not they can take account of the nonlinear constraints and in their convergence properties. Our numerical experiments show that the performance of the methods depends strongly on the problem, but that the spectral projected gradient method is the clear winner
Episodic, transient systemic acidosis delays evolution of the malignant phenotype: Possible mechanism for cancer prevention by increased physical activity
No full textBackground:
The transition from premalignant to invasive tumour growth is a prolonged multistep process governed by phenotypic adaptation to changing microenvironmental selection pressures. Cancer prevention strategies are required to interrupt or delay somatic evolution of the malignant invasive phenotype. Empirical studies have consistently demonstrated that increased physical activity is highly effective in reducing the risk of breast cancer but the mechanism is unknown.
Results:
Here we propose the hypothesis that exercise-induced transient systemic acidosis will alter the in situ tumour microenvironment and delay tumour adaptation to regional hypoxia and acidosis in the later stages of carcinogenesis. We test this hypothesis using a hybrid cellular automaton approach. This model has been previously applied to somatic evolution on epithelial surfaces and demonstrated three phases of somatic evolution, with cancer cells escaping in turn from the constraints of limited space, nutrient supply and waste removal. In this paper we extend the model to test our hypothesis that transient systemic acidosis is sufficient to arrest, or at least delay, transition from in situ to invasive cancer.
Conclusions:
Model simulations demonstrate that repeated episodes of transient systemic acidosis will interrupt critical evolutionary steps in the later stages of carcinogenesis resulting in substantial delay in the evolution to the invasive phenotype. Our results suggest transient systemic acidosis may mediate the observed reduction in cancer risk associated with increased physical activity
Morse Theory for Invariant Functions and its Application to the n-Body Problem
Get PDFWe study various topological properties of G-manifolds and G-complexes where G is a finite group. We achieve this by first observing the work of others, T.F. Banchoff,
Milnor and R. Bott, and then extending these ideas and concepts to the situation of G-manifolds and complexes.
We start with embedded polyhedra and a critical point theorem, linking numbers of critical points to the Euler characteristic, which we adapt to encompass G-complexes and G-invariant functions to form a critical orbit theorem. We then move on to the Lefschetz fixed point theorem. We describe the concepts G-trace and G-Euler characteristics which have a direct link to their non-G counterparts. We use
these to prove what we call the G-Lefschetz fixed orbit theorem; an extension of the Lefschetz fixed point theorem.
We develop G-Morse and G-Morse-Bott theory from their usual respective theories.
We define the notion of orientation representation and G-Morse and G-Poincare polynomials. The main result of this work is MG_t(f) - PG_t (M) = (1 + t)QG_t (f);
where f is a non-degenerate (in the sense of Morse-Bott theory) function on the manifold M, MG_t(f) is the G-Morse polynomial of f, PG_t(M) is the G-Poincare polynomial of M and QG_t(f) is a polynomial with non-negative coefficients. These polynomials have coefficients in the representation ring.
Finally we apply G-Morse theory to the n-body problem and fully describe the relative equilibria solutions up to and including five particles