MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Uniformity principle for -definability
Get PDFThe main goal of this research is to develop logical tools and techniques for effective reasoning about continuous data based on -definability. In this article we invent the Uniformity Principleand prove it for -definability over the real numbers extended by open predicates. Using the Uniformity Principle, we investigate different approaches to enrich the language of {Sigma}-formulas in such a way that simplifies reasoning about computable continuous data without enlarging the class of -definable sets. In order to do reasoning about computability of certain continuous data we have to pick up an appropriate language of a structure representing these continuous data. We formulate several major conditions how to do that in a right direction. We also employ the Uniformity Principleto argue that our logical approach is a good way for formalization of computable continuous data in logical terms
Tube geometry can force switchlike transitions in the behavior of propagating bubbles
Get PDFMicroscale process engineering requires precise control of bubbles and droplets. We investigate
geometry-induced control and find that a centered constriction in the cross section of rectangular
tubes can lead to new families of steadily propagating bubbles, which localize in the
least-constricted regions of the cross section. Tuning the constriction geometry can cause a
switchlike transition from centered to localized bubbles at a critical value of the flow rate: a
mechanism for flow-rate-driven bubble control. The accompanying large change in bubble volume
could be significant for liquid recovery applications
Linearizations of Singular Matrix Polynomials and the Recovery of Minimal Indices
Get PDFA standard way of dealing with a regular matrix polynomial P(¸) is to convert it into
an equivalent matrix pencil { a process known as linearization. Two vector spaces of pencils L1(P)
and L2(P) that generalize the ¯rst and second companion forms have recently been introduced by
Mackey, Mackey, Mehl and Mehrmann. Almost all of these pencils are linearizations for P(¸) when
P is regular. The goal of this work is to show that most of the pencils in L1(P) and L2(P) are still
linearizations when P(¸) is a singular square matrix polynomial, and that these linearizations can
be used to obtain the complete eigenstructure of P(¸), comprised not only of the ¯nite and in¯nite
eigenvalues, but also for singular polynomials of the left and right minimal indices and minimal bases.
We show explicitly how to recover the minimal indices and bases of the polynomial P(¸) from the
minimal indices and bases of linearizations in L1(P) and L2(P). As a consequence of the recovery
formulae for minimal indices, we prove that the vector space DL(P) = L1(P) \ L2(P) will never
contain any linearization for a square singular polynomial P(¸). Finally, the results are extended to
other linearizations of singular polynomials de¯ned in terms of more general polynomial base
Perturbation, Computation and Refinement of Invariant Subspaces for Matrix Polynomials
Get PDFGeneralizing the notion of an eigenvector, invariant subspaces are frequently used in the context of linear eigenvalue problems, leading to conceptually elegant and
numerically stable formulations in applications that require the computation of several eigenvalues and/or eigenvectors. Similar benefits can be expected for polynomial eigenvalue problems, for which the concept of invariant subspaces needs to be replaced by the concept of invariant pair. Little is known so far about
numerical aspects of such invariant pairs. The
aim of this paper is to fill this gap. The behavior of invariant pairs under perturbations of the matrix polynomial is studied and a first-order perturbation expansion is given. From a computational point of view, we investigate how to best extract invariant pairs from a linearization of the matrix polynomial. Moreover, we describe efficient refinement procedures directly based on the polynomial formulation. Numerical experiments
with matrix polynomials from a number of applications demonstrate the effectiveness of our extraction and refinement procedures
The Scaling and Squaring Method for the Matrix Exponential Revisited
Get PDFThe scaling and squaring method is the most widely used method for computing the
matrix exponential, not least because it is the method implemented in the MATLAB
function expm. The method scales the matrix by a power of 2 to reduce the norm to
order 1, computes a Pad´e approximant to the matrix exponential, and then repeatedly
squares to undo the effect of the scaling. We give a new backward error analysis of the
method (in exact arithmetic) that employs sharp bounds for the truncation errors and
leads to an implementation of essentially optimal efficiency. We also give a new rounding
error analysis that shows the computed Pad´e approximant of the scaled matrix to be
highly accurate. For IEEE double precision arithmetic the best choice of degree of Pad´e
approximant turns out to be 13, rather than the 6 or 8 used by previous authors. Our
implementation of the scaling and squaring method always requires at least two fewer
matrix multiplications than the expm function in MATLAB 7.0 when the matrix norm
exceeds 1, which can amount to a 37% saving in the number of multiplications, and it
is typically more accurate, owing to the fewer required squarings. We also investigate
a different scaling and squaring algorithm proposed by Najfeld and Havel that employs
a P ad´e approximation to the function x coth(x). This method is foun
Numerical Relativity and Asymptotic Flatness
Get PDFIt is highly plausible that the region of spacetime far from an isolated gravitating body is, in some sense, asymptotically Minkowskian. However theoretical studies of the full nonlinear theory, initiated by Bondi et al (1962 Proc. R. Soc. A 269 21�51), Sachs (1962 Proc. R. Soc. A 270 103�26) and Newman and Unti (1962 J. Math. Phys. 3 891�901), rely on careful, clever, a priori choices of a chart (and tetrad) and so are not readily accessible to the numerical relativist, who chooses her/his chart on the basis of quite different grounds. This paper seeks to close this gap. Starting from data available in a typical numerical evolution, we construct a chart and tetrad which are, asymptotically, sufficiently close to the theoretical ones, so that the key concepts of the Bondi news function, Bondi mass and its rate of decrease can be estimated. In particular, these estimates can be expressed in the numerical relativist's chart as numerical relativity recipes
Exit problems associated with affine reflection groups
No full textWe obtain a formula for the distribution of the first exit time of
Brownian motion from the alcove of an affine Weyl group. In most
cases the formula is expressed compactly, in terms of Pfaffians. Expected
exit times are derived in the type � case. The results extend to
other Markov processes. We also give formulas for the real eigenfunctions
of the Dirichlet and Neumann Laplacians on alcoves, and observe
that the �Hot Spots� conjecture of J. Rauch is true for alcoves
Non-axisymmetric self-similar flow between two rotating disks
Get PDFThis paper considers the flow of an incompressible, viscous fluid forced by the independent rotation of two (bounding) infinite, parallel planes. The flow field is assumed to have a radial self-similarity of Von Kármán form and the relevant governing equations are derived with no assumptions of rotational symmetry. An exact class of solutions to the Navier�Stokes equations is shown to exist, corresponding to nonlinear, non-axisymmetric states. These steady, non-axisymmetric solutions appear through symmetry breaking of the classical axisymmetric steady states. The locus of bifurcation points is determined numerically and a number of limiting cases are described asymptotically. The initial-value problem is considered in the context of the self-similar equations. It is shown that unsteady calculations can break down at a finite time with the development of a singularity in the (exact) system of equations. An asymptotic description is given in the neighbourhood of the breakdown event. The structure of the singularity consists of an inviscid core flow to which an infinity of solutions are possible within the framework of the same asymptotic description. Whether a singularity is approached, or a steady/periodic axisymmetric state is achieved (and even the qualitative details of the singularity) is dependent on the initial conditions for some parameter regimes
Some Issues in Dense Linear Algebra for Multicore and Special Purpose Architectures
Get PDFWe address some key issues in designing dense linear algebra
(DLA) algorithms that are common for both multi/many-cores and
special purpose architectures (in particular GPUs). We present them in
the context of an LU factorization algorithm, where randomization techniques
are used as an alternative to pivoting. This approach yields an
algorithm based entirely on a collection of small Level 3 BLAS type computational
tasks, which has emerged as a common goal in designing DLA
algorithms for new architectures. Other common trends, also considered
here, are block asynchronous task execution and “Block” layouts for the
data associated with the separate tasks. We present numerical results
and other specific experiments with DLA algorithms on NVIDIA GPUs
using CUDA. The GPU results are also of interest themselves as we show
a performance of up to 160 Glop/s on a single Quadro FX 5600 card
Stability of learning dynamics in two-agent, imperfect-information games
Get PDFOne issue in multi-agent co-adaptive learning concerns convergence. When two (or more) agents play a game with different information and different payoffs, the general behaviour tends to be oscillation around a Nash equilibrium. Several algorithms have been proposed to force convergence to mixed-strategy Nash equilibria in imperfect-information games when the agents are aware of their opponent's strategy. We consider the effect on one such algorithm, the lagging anchor algorithm, when each agent must also infer the gradient information from observations, in the infinitesimal time-step limit. Use of an estimated gradient, either by opponent modelling or stochastic gradient ascent, destabilises the algorithm in a region of parameter space. There are two phases of behaviour. If the rate of estimation is low, the Nash equilibrium becomes unstable in the mean. If the rate is high, the Nash equilibrium is an attractive fixed point in the mean, but the uncertainty acts as narrow-band coloured noise, which causes dampened oscillations