MIMS EPrints

Not a member yet

2151 research outputs found

Sort by

Algorithms for the Matrix Exponential and its Fr\'echet Derivative

Author: Al-Mohy Awad H.
Publication venue
Publication date: 06/07/2010
Field of study

New algorithms for the matrix exponential and its Fr\'echet derivative are presented. First, we derive a new scaling and squaring algorithm (denoted

\mathrm{expm_{new}}

) for computing

e^A

, where

A

is any square matrix, that mitigates the overscaling problem. The algorithm is built on the algorithm of Higham [{\em SIAM J. Matrix Anal. Appl.}, 26\penalty0(4):\penalty0 1179--1193, 2005] but improves on it by two key features. The first, specific to triangular matrices, is to compute the diagonal elements in the squaring phase as exponentials instead of powering them. The second is to base the backward error analysis that underlies the algorithm on members of the sequence

\{\|A^k\|^{1/k}\}

instead of

\|A\|

. The terms

\|A^k\|^{1/k}

are estimated without computing powers of

A

by using a matrix 1-norm estimator. Second, a new algorithm is developed for computing the action of the matrix exponential on a matrix,

e^{tA}B

, where

A

is an

n\times n

matrix and

B

n\times n_0

with

n_0 \ll n

. The algorithm works for any

A

, its computational cost is dominated by the formation of products of

A

with

n\times n_0

matrices, and the only input parameter is a backward error tolerance. The algorithm can return a single matrix

e^{tA}B

or a sequence

e^{t_kA}B

on an equally spaced grid of points

t_k

. It uses the scaling part of the scaling and squaring method together with a truncated Taylor series approximation to the exponential. It determines the amount of scaling and the Taylor degree using the strategy of

\mathrm{expm_{new}}

. Preprocessing steps are used to reduce the cost of the algorithm. An important application of the algorithm is to exponential integrators for ordinary differential equations. It is shown that the sums of the form

\sum_{k=0}^p\varphi_k(A)u_k

that arise in exponential integrators, where the

\varphi_k

are related to the exponential function, can be expressed in terms of a single exponential of a matrix of dimension

n+p

built by augmenting

A

with additional rows and columns. Third, a general framework for simultaneously computing a matrix function,

f(A)

, and its Fr\'echet derivative in the direction

E

L_f(A,E)

, is established for a wide range of matrix functions. In particular, we extend the algorithm of Higham and

\mathrm{expm_{new}}

to two algorithms that intertwine the evaluation of both

e^A

and

L(A,E)

at a cost about three times that for computing

e^A

alone. These two extended algorithms are then adapted to algorithms that simultaneously calculate

e^A

together with an estimate of its condition number. Finally, we show that

L_f(A,E)

, where

f

is a real-valued matrix function and

A

and

E

are real matrices, can be approximated by

\Im f(A+ihE)/h

for some suitably small

h

. This approximation generalizes the complex step approximation known in the scalar case, and is proved to be of second order in

h

for analytic functions

f

and also for the matrix sign function. It is shown that it does not suffer the inherent cancellation that limits the accuracy of finite difference approximations in floating point arithmetic. However, cancellation does nevertheless vitiate the approximation when the underlying method for evaluating

f

employs complex arithmetic. The complex step approximation is attractive when specialized methods for evaluating the Fr\'echet derivative are not available

The Complex Step Approximation to the Fréchet Derivative of a Matrix Function

Author: Al-Mohy Awad H.
Higham Nicholas J.
Publication venue
Publication date: 2010
Field of study

We show that the Fr\'echet derivative of a matrix function

f

A

in the direction

E

, where

A

and

E

are real matrices, can be approximated by

\Im f(A+ihE)/h

for some suitably small

h

. This approximation, requiring a single function evaluation at a complex argument, generalizes the complex step approximation known in the scalar case. The approximation is proved to be of second order in

h

for analytic functions

f

f

employs complex arithmetic. The ease of implementation of the approximation, and its superiority over finite differences, make it attractive when specialized methods for evaluating the Fr\'echet derivative are not available, and in particular for condition number estimation when used in conjunction with a block 1-norm estimation algorithm

Small-scale instabilities in dynamical systems with sliding

Author: Sieber J
Kowalczyk P
Publication venue
Publication date: 2010
Field of study

We demonstrate with a minimal example that in Filippov systems (dynamical systems governed by discontinuous but piecewise smooth vector fields) stable periodic motion with sliding is not robust with respect to stable singular perturbations. We consider a simple dynamical system that we assume to be a quasi-static approximation of a higher-dimensional system containing a fast stable subsystem. We tune a system parameter such that a stable periodic orbit of the simple system touches the discontinuity surface: this is the so-called grazing-sliding bifurcation. The periodic orbit remains stable, and its local return map becomes piecewise linear. However, when we take into account the fast dynamics the local return map of the periodic orbit changes qualitatively, giving rise to, for example, period-adding cascades or small-scale chaos

Computing Matrix Functions

Author: Higham Nicholas J.
Al-Mohy Awad H.
Publication venue
Publication date: 01/01/2010
Field of study

The need to evaluate a function

f(A)\in\mathbb{C}^{n \times n}

of a matrix

A\in\mathbb{C}^{n \times n}

arises in a wide and growing number of applications, ranging from the numerical solution of differential equations to measures of the complexity of networks. We give a survey of numerical methods for evaluating matrix functions, along with a brief treatment of the underlying theory and a description of two recent applications. The survey is organized by classes of methods, which are broadly those based on similarity transformations, those employing approximation by polynomial or rational functions, and matrix iterations. Computation of the Fr\'echet derivative, which is important for condition number estimation, is also treated, along with the problem of computing

f(A)b

without computing

f(A)

. A summary of available software completes the survey

Locally Finitely Presented Categories of Sheaves of Modules

Author: Prest Mike
Ralph Alexandra
Publication venue
Publication date: 15/02/2010
Field of study

We determine conditions under which the category of sheaves of modules over a ringed space is locally finitely presented, respectively locally finitely generated

Structured Linearizations for Palindromic Matrix Polynomials of Odd Degree

Author: De Teran Fernando
Dopico Froilan M.
Mackey D. Steven
Publication venue
Publication date: 19/04/2010
Field of study

The standard way to solve polynomial eigenvalue problems P(\la)x=0 is to convert the matrix polynomial P(\la) into a matrix pencil that preserves its spectral information-- a process known as linearization. When P(\la) is palindromic, the eigenvalues, elementary divisors, and minimal indices of P(\la) have certain symmetries that can be lost when using the classical first and second companion linearizations for numerical computations, since these linearizations do not preserve the palindromic structure. Recently new families of linearizations have been introduced with the goal of finding linearizations that retain whatever structure that the original P(\la) might possess, with particular attention paid to the preservation of palindromic structure. However, no general construction of palindromic linearizations valid for all palindromic polynomials has as yet been achieved. In this paper we present a family of linearizations for odd degree polynomials P(\la) which are palindromic whenever P(\la) is, and which are valid for all palindromic polynomials of odd degree. We illustrate our construction with several examples. In addition, we establish a simple way to recover the minimal indices of the polynomial from those of the linearizations in the new family

Modular representations and finite W-algebras

Author: Premet Alexander
Publication venue
Publication date: 24/05/2010
Field of study

This preprint is a set of notes on nilpotent orbits, finite W-algebras, modular representations and primitive ideals from the lectures I gave at the summer school "Structures in Lie Representation Theory" held at Jacobs University Bremen in August 2009. The notes were taken by K. Rian, O. Styrt and G. Tomasini and then edited by myself

Geometric structure in the principal series of the p-adic group G_2

Author: Aubert Anne-Marie
Baum Paul
Plymen Roger
Publication venue
Publication date: 30/07/2010
Field of study

In the representation theory of reductive

p

-adic groups

G

, 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

G_2

. A feature of this article is the role played by cocharacters

h_c

attached to two-sided cells

c

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

A(G)

of all these extended quotient varieties. We conjecture that, after a simple algebraic correction, the space

A(G)

is a model of the smooth dual

Irr(G)

. In this respect, our programme is a conjectural refinement of the Bernstein programme. The algebraic correction is controlled by the cocharacters

h_c

. The cocharacters themselves appear to be closely related to Langlands parameters

A Schur--Pad\'e Algorithm for Fractional Powers of a Matrix

Author: Higham Nicholas J.
Lin Lijing
Publication venue
Publication date: 19/10/2010
Field of study

A new algorithm is developed for computing arbitrary real powers

A^p

of a matrix

A\in\mathbb{C}^{n\times n}

. The algorithm starts with a Schur decomposition, takes

k

square roots of the triangular factor

T

, evaluates an

[m/m]

Pad\'e approximant of

(1-x)^p

I - T^{1/2^k}

, and squares the result

k

times. The parameters

k

and

m

are chosen to minimize the cost subject to achieving double precision accuracy in the evaluation of the Pad\'e approximant, making use of a result that bounds the error in the matrix Pad\'e approximant by the error in the scalar Pad\'e approximant with argument the norm of the matrix. The Pad\'e approximant is evaluated from the continued fraction representation in bottom-up fashion, which is shown to be numerically stable. In the squaring phase the diagonal and first superdiagonal are computed from explicit formulae for

T^{p/2^j}

, yielding increased accuracy. Since the basic algorithm is designed for

p\in(-1,1)

, a criterion for reducing an arbitrary real

p

to this range is developed, making use of bounds for the condition number of the

A^p

problem. How best to compute

A^k

for a negative integer

k

is also investigated. In numerical experiments the new algorithm is found to be superior in accuracy and stability to several alternatives, including the use of an eigendecomposition and approaches based on the formula

A^p = \exp(p\log(A))

Two dimensional attractors in the border collision normal form

Author: Glendinning Paul
Wong Chi Hong
Publication venue
Publication date: 17/11/2010
Field of study

New techniques are developed to show that the two-dimensional normal form for codimension one border collision bifurcations of fixed points of discrete time piecewise smooth dynamical systems has attractors which are themselves two dimensional. This makes it possible to prove the existence of these attractors for a countable set of parameter values which cannot be treated using the essentially one-dimensional methods in the literature

1,445

full texts

2,151

metadata records

Updated in last 30 days.

MIMS EPrints

Access Repository Dashboard

Do you manage Open Research Online? Become a CORE Member to access insider analytics, issue reports and manage access to outputs from your repository in the CORE Repository Dashboard! 👇