MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Improved error bounds for underdetermined system solvers
Get PDFThe minimal 2-norm solution to an underdetermined system of full rank can be computed using a QR factorization of in two different ways. One method requires storage and reuse of the orthogonal matrix , while the method of seminormal equations does not. Existing error analyses show that both methods produce computed solutions whose normwise relative error is bounded to first order by , where is a constant depending on the dimensions of , is the 2-norm condition number, and is the unit roundoff. It is shown that these error bounds can be strengthened by replacing by the potentially much smaller quantity , which is invariant under row scaling of . It is also shown that reflects the sensitivity of the minimum norm solution to row-wise relative perturbations in the data and . For square linear systems row equilibration is shown to endow solution methods based on LU or QR factorization of with relative error bounds proportional to , just as when a QR factorization of is used. The advantages of using fixed precision iterative refinement in this context instead of row equilibration are explained
Optimization by direct search in matrix computations
Get PDFA direct search method attempts to maximize a function using function values only. Many questions about the stability and accuracy of algorithms in matrix computations can be expressed in terms of the maximum value of some easily computable function . For a variety of algorithms it is shown that direct search is capable of revealing instability or poor performance, even when such failure is difficult to discover using theoretical analysis or numerical tests with random or nonrandom data. Informative numerical examples generated by direct search provide the impetus for further analysis and improvement of an algorithm. The direct search methods used are the method of alternating directions and the multi-directional search method of Dennis and Torczon. The problems examined include the reliability of matrix condition number estimators and the stability of Strassen’s fast matrix inversion method
Finite precision behavior of stationary iteration for solving singular systems
No full textA stationary iterative method for solving a singular system Ax=b converges for any starting vector if limi→∞Gi exists, where G is the iteration matrix, and the solution to which it converges depends on the starting vector. We examine the behavior of stationary iteration in finite precision arithmetic. A pertubation bound for singular systems is derived and used to define forward stability of a numerical method. A rounding error analysis enables us to deduce conditions under which a stationary iterative method is forward stable or backward stable. The component of the forward error in the null space of A can grow linearly with the number of iterations, but it is innocuous as long as the iteration converges reasonably quickly. As special cases, we show that when A is symmetric positive semidefinite the Richardson iteration with optimal parameter is forward stable, and if A also has unit diagonal and property A, then the Gauss-Seidel method is both forward and backward stable. Two numerical examples are given to illustrate the analysis
Diffusing through spectres: ridge curves, ghost circles and a partition of phase space
No full textThe study of transport in Hamiltonian and related systems is greatly illuminated if one can construct a framework of "almost invariant" surfaces to organized the dynamics. This can be done in the case of area-preserving twist maps, using pieces of table and unstable manifold of periodic orbits or cantori, as shown by MacKay, Meiss and Percival. The resulting surfaces, however, are not necessarily the most appropriate ones, as they need not be graphs, nor is it clear that they can always be chosen mutually disjoint. Hall proposed a choice based on "ridge curves" for the gradient flow of the associated variational problem, which Golé christened "ghost cicles". They have the advantage that they are always graphs. In this Letter, we present numerical experiments suggesting that ghost circles are mutually disjoint. Our work has subsequently led to a proof of this by Angenent and Golé. We propose that ghost circles from a convenient, natural skeleton around which to organize studies of transport
Multiplicities of Critical Points of Invariant Functions
Get PDFThe purpose of this expository article is to describe in an elementary and homogeneous manner, the relationship between the geometric and algebraic multiplicities of isolated critical points of holomorphic functions. In particular, I am interested in the setting where the function is invariant under some group action. The emphasis is on functions invariant under actions of finite groups as very little is known if the group is not finite. Most of the results described here are already explicitly in the
literature; the only small extension is to functions that are not invariant, but equivariant under the action of a group G: a function f satisfying f(gx) = J(g).f(x) for
some homomorphism J : G \to C∗. The results (in Section 7) on the multiplicity of critical points of homogeneous functions invariant under C∗ are also new
The problem of Anisotropy in Electrical Impedance Tomography
Get PDFThe reconstruction algorithms used for Electrical Impedance Tomography assume that the conductivity is isotropic. If the conductivity is anisotropic then the solution to the reconstruction problem is not unique. As many body tissues are anisotropic this presents a problem. Recent mathematical results suggest that anisotropic conductivities which are indistinguishable using EIT differ by a distortion of the domain. In addition, those anisotropic distributions consistent with some anisotropic distribution are unlikely to occur in practice. What is need for the success of EIT in the anisotropic case is sufficient additional knowledge of the structure of the anisotropy to make the solution of the reconstruction problem unique
Linear Filters and Non-linear Systems
No full textIt has been asserted in the literature that the low pass filtering of time series data may lead to erroneous results when calculating attractor dimensions. Here we prove that finite order, non-recursive filters do not have this effect. In fact, a generic, finite order, non-recursive filter leaves invariant all the quantities that can be estimated by using embedding techniques such as the method of delays
Stability of Block Algorithms with Fast Level-3 BLAS
No full textBlock algorithms are becoming increasingly popular in matrix computations.
Since their basic unit of data is a submatrix rather than a scalar they have a
higher level of granularity than point algorithms, and this makes them
well-suited to high-performance computers.
The numerical stability of the block algorithms in the new linear algebra
program library LAPACK is investigated here. It is shown that these
algorithms have backward error analyses in which the backward error bounds are
commensurate with the error bounds for the underlying level 3 BLAS (BLAS3).
One implication is that the block algorithms are as stable as the corresponding
point algorithms when conventional BLAS3 are used. A second implication is
that the use of BLAS3 based on fast matrix multiplication techniques affects
the stability only insofar as it increases the constant terms in the normwise
backward error bounds.
For linear equation solvers employing factorization it is
shown that fixed precision iterative refinement helps to mitigate the effect of
the larger error constants.
Despite the positive results presented here, not all plausible block \alg s are
stable; we illustrate this with the example of \LUf\ with block triangular
factors, and we describe how to check a block \alg\ for stability without doing
a full error analysis
Solving the Generalized Symmetric Eigenvalue Problem
Get PDFThe generalized symmetric eigenvalue problem (GSEVP) , symmetric, symmetric positive definite, occurs in many practical problems, but there is as yet no numerically stable algorithm which takes full advantage of its structure. The \textit{standard method}
(factor , solve the ordinary symmetric eigenvalue problem QZQZQZB\kappa(B)A_c y = \lambda D^{2}_{c} yA_cD_cD^{-1}_{c} A_c D^{-1}_c$, while maintaining the symmetric and diagonal forms. The results of numerical tests indicate the benefits of this approach. A variant of the approach is amenable to parallel computation
Estimating the matrix p-norm
No full textThe H\"older -norm of an matrix has no explicit representation
unless ,~ or . It is shown here that the -norm can be
estimated reliably in operations. A generalization of the power
method is used, with a starting vector determined by a technique with a
condition estimation flavour. The algorithm nearly always computes a
-norm estimate correct to the specified accuracy, and the estimate is always
within a factor of . As a by-product, a new way is
obtained to estimate the 2-norm of a rectangular matrix; this method is more
general and produces better estimates in practice than a similar technique of
Cline, Conn and Van Loan