MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
A Survey of Componentwise Perturbation Theory
Get PDFPerturbation bounds in numerical linear algebra are traditionally derived and
expressed using norms.
Norm bounds cannot reflect the scaling or sparsity of a problem and its
perturbation, and so can be unduly weak.
If the problem data and its perturbation are measured
componentwise, much smaller and more revealing bounds can be obtained.
A survey is given of componentwise perturbation theory in numerical linear
algebra, covering linear systems, the matrix inverse,
matrix factorizations,
the least squares problem, and the eigenvalue and singular value problems.
Most of the results described have been published in the last five years
A parallel algorithm for computing the polar decomposition
No full textThe polar decomposition A = UH of a rectangular matrix A, where U is unitary and H is Hermitian positive semidefinite, is an important tool in various applications, including aerospace computations, factor analysis and signal processing. We consider a pth order iteration for computing U that involves p independent matrix inversions per step and which is hence very amenable to parallel computation. We show that scaling the iterates speeds convergence of the iteration but makes the iteration only conditionally stable, with the backward error typically κappa_2(A) times bigger than the unit roundoff. In our implementation of the iteration on the Kendall Square Research KSR1 virtaul shared memory MIMD computer we take p to be the number of processors (p ≤ 16 in our experiments). Our code is found to be significantly faster than two existing techniques for computing the polar decomposition: one a Newton iteration, the other based on the singular value decomposition
Stability of the partitioned inverse method for parallel solution of sparse triangular systems
Get PDFSeveral authors have recently considered a parallel method for solving sparse triangular systems with many right-hand sides. The method employs a partition into sparse factors of the product form of the inverse of the coefficient matrix. It is shown here that while the method can be unstable, stability is guaranteed if a certain scalar that depends on the matrix and the partition is small and that this scalar is small when the matrix is well conditioned. Moreover, when the partition is chosen so that the factors have the same sparsity structure as the coefficient matrix, the backward error matrix can be taken to be sparse
The path formulation of bifurcation theory
Get PDFWe show how the path formulation of bifurcation theory can be made to work, and that it is (essentially) equivalent to the usual parametrized contact equivalence of Golubitsky
and Schaeffer
The matrix sign decomposition and its relation to the polar decomposition
No full textThe sign function of a square matrix was introduced by Roberts in 1971. We show that it is useful to regard S = sign(A) as being part of a matrix sign decomposition A = SN, where N = (A2)1/2. This decomposition leads to the new representation sign(A) = A(A2)−1/2. Most results for the matrix sign decomposition have a counterpart for the polar decomposition A = UH, and vice versa. To illustrate this, we derive best approximation properties of the factors U, H, and S, determine bounds for ||A − S|| and ||A − U||, and describe integral formulas for S and U. We also derive explicit expressions for the condition numbers of the factors S and N. An important equation expresses the sign of a block 2 × 2 matrix involving A in terms of the polar factor U of A. We apply this equation to a family of iterations for computing S by Pandey, Kenney, and Laub, to obtain a new family of iterations for computing U. The iterations have some attractive properties, including suitability for parallel computation
Delay reconstruction for multiprobe signals
Get PDFA physical system governed by low-dimensional dynamics may be described completely with just a few measurements. Once one has such a description, any further measurements are redundant-one ought to be able to determine the results from what one already knows. Here we apply this idea to multivariate time series; we use the signal in one of the channels to build a model of the underlying system, then use the model to predict all the other channels. We demonstrate the method on a signal from a fluid-mechanical experiment, then discuss the implications for signal compression and for the secrecy of messages masked by chaotic nois
Noncommutative geometry: illustrations from the representation theory of GL(n)
Get PDFThis is a view from noncommutative geometry of the representation theory of GL(n). Topics covered include: Morita equivalence, the Iwahori-Hecke C*-algebra, the spherical C*-algebra, C*-Plancherel Theorem, Brylinski quotient (now called the extended quotient)
Quotient spaces and critical points of invariant functions for C*-actions
Get PDFConsider a linear action of the group C∗ on X = C^{n+1}. We study the fundamental algebraic properties of the sheaves of invariant and basic differential forms for such an action, and use these to define an algebraic notion of multiplicity for critical points of functions which are invariant under the C∗-action. We also prove a theorem relating the cohomology of the Milnor fibre of the critical point on the quotient space with this algebraic multiplicity. We also include an appendix showing how to use Cech complexes to compute local cohomology
Topology from time series
No full textWe describe methods for the study of topological properties of the invariant manifolds of experimental dynamical systems. We explain how to compute such invariants as the Euler characteristic and Betti numbers using time series data, and suggest a number of potential applications
Perturbation Theory and Backward Error for
No full textBecause of the special structure of the equations the
usual relation for linear equations ``\mbox{backward error} =
\mbox{relative residual}'' does not hold, and
application of the standard perturbation result for yields a
perturbation bound involving that is not always
attainable. An expression is derived for the backward error of an
approximate solution ; it shows that the backward error can exceed
the relative residual by an arbitrary factor. A sharp perturbation
bound is derived and it is shown that the condition number it defines
can be arbitrarily smaller than the -based
quantity that is usually used to measure sensitivity. For practical
error estimation using the residual of a computed solution an
``LAPACK-style'' bound is shown to be efficiently computable and
potentially much smaller than a sep-based bound.
A Fortran~77 code has been written that solves the Sylvester equation
and computes this bound, making use of LAPACK routines