MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Newton's method for the matrix square root
No full textOne approach to computing a square root of a matrix A is to apply Newton's method to the quadratic matrix equation F(X) ≡X2 - A = 0. Two widely-quoted matrix square root iterations obtained by rewriting this Newton iteration are shown to have excellent mathematical convergence properties. However, by means of a perturbation analysis and supportive numerical examples, it is shown that these simplified iterations are numerically unstable. A further variant of Newton's method for the matrix square root, recently proposed in the literature, is shown to be, for practical purposes, numerically stable
The Singular Value Decomposition in Multivariate Statistics
Get PDFMany multivariate techniques in statistics are described in terms of an appropriate sums of squares and cross products matrix, such as a covariance matrix, or a correlation matrix, rather than in terms of the original data matrix. While this is frequently the best way of understanding and analysing a technique, it is not necessarily the most satisfactory approach for implementing the technique computationally. From a numerical point of view, it is usually better to work with the data matrix.
This is a review article aimed at the statistician and mathematician who, while not being expert numerical analysts, would like to gain some understanding of why it is better to work with the data matrix, and of the techniques that allow us to avoid the explicit computation of sums and squares and cross products matrices. To give a focus and to keep the article of moderate length, we concentrate in particular on the use of the singular value decomposition and its application to multiple regression problems. In the final two sections we give a brief discussion of principal components, canonical correlations and the generalized singular value decomposition
Analysis of the early stage of thermal runaway
No full textIt is shown that a variable grouping containing a logarithmic time-dependent factor is required for the development of a coordinate-perturbation expansion which realistically describes the spatially varying thermal-runaway process. The resulting solution is in good agreement with careful numerical computations. It describes a self-focussing temperature growth, the form and behaviour of which are remarkably independent of both the conditions leading to thermal runaway and the topology of the thermal-runaway region. The detailed solution also reveals an underlying structure in the temperature development, in which a strongly supercritical thermal runaway (where the relative effects of conduction are initially small) is found to be very much like a less strongly supercritical, but more highly-developed, thermal runaway. In this development the local rate rate of self-heating accelerates dramatically while, in comparison, the conductive impediment to the temperature growth diminishes towards zero. Attempts to develop a solution using a variable grouping without the logarithmic factor are shown to produce results which are unsuitable for describing inhomogeneous thermal runaway.
Some numerically computed results are presented, detailing the Ignition Kernel formed as a result of supercritical thermal runaway in a fixed-temperature symmetric container
Nearness Problems in Numerical Linear Algebra
Get PDFWe consider the theoretical and the computational aspects of some nearness problems in numerical linear algebra. Given a matrix , a matrix norm and a matrix property P, we wish to find the distance from to the class of matrices having property P, and to compute a nearest matrix from this class.
It is well-known that nearness to singularity is measured by the reciprocal of the matrix condition number. We survey and compare a wide variety of techniques for estimating the condition number and make recommendations concerning the use of the estimates in applications.
We express the solution to the nearness to unitary and nearness to Hermitian positive (semi-) definiteness problems in terms of the polar decomposition. A quadratically convergent Newton iteration for computing the unitary polar factor is presented and analysed, and the iteration is developed into a practical algorithm for computing the polar decomposition. Applications of the algorithm to factor analysis, aerospace computations and optimisation are described; and the algorithm is used to derive a new method for computing the square root of a symmetric positive definite matrix. This leads us, in the remainder of the thesis, to consider the theory and computation of matrix square roots.
We analyse the convergence properties and the numerical stability of several well-known Newton methods for computing the matrix square root. By means of a perturbation analysis and supportive numerical examples it is shown that two of these Newton iterations are numerically unstable. The polar decomposition algorithm, and a further Newton square root iteration are shown not to suffer from this numerical instability.
For a nonsingular real matrix we derive conditions for the existence of a real square root, and for the existence of a real square root which is a polynomial in ; the number of square roots of the latter type is determined. We show how a Schur method recently proposed by Bj\"orck and Hammarling can be extended so as to compute a real square root of a real matrix in real arithmetic. Finally, we investigate the conditioning of matrix square roots and derive an algorithm for the computation of a well-conditioned square root
Matrix Condition Numbers
Get PDFSeveral properties of matrix norms and condition numbers are
described. The sharpness of the norm bounds in the standard perturbation
results for is investigated. For perturbations in the bounds
are sharp and quite likely to be realistic. For perturbations in the
usual bound is not sharp and can be unduly pessimistic; a more suitable
measure of the conditioning than cond(A) is suggested.
Some important concepts relating to the problem of condition
estimation are discussed, careful consideration being given to the
reliability and computational cost of condition estimators. The LINPACK
condition estimation algorithm is described, its weaknesses, including
two counter-examples, pointed out, and some observations given.
Let be an tridiagonal matrix. We show that it is possible to
compute ,
and hence , in operations. Several
algorithms which perform this task are given. All but one of the
algorithms apply to irreducible tridiagonal matrices: those having no
zero elements on the subdiagonal and superdiagonal. It is shown how
these algorithms may be employed in the computation of
when is reducible.
If is, in addition, positive definite then it is possible to compute
as the norm of the solution to a
linear system involving 's comparison matrix, , which is also
positive definite and tridiagonal. Utilising a relation between the
factors of and we show how the LINPACK routine
SPTSL, which solves for positive definite tridiagonal matrices ,
can be modified so that it also computes , the increase in
computational cost being 00 approximately 60 percen
A Survey of Numerical Aspects of Plane Rotations
Get PDFIn recent years the use of plane rotations in orthogonal factorizations has been increasing in popularity. This is in part due to modifications which enable computations with plane rotations to be carried out more quickly and in part due to the use of plane rotations in updating matrix factorizations and in other sparse applications.
A review of Jacobi, Givens and modified plane rotations and of products of plane rotations is given. The review includes discussion of the computational details required
to avoid underflow and overflow when computing plane rotations, storage of plane rotations and the stability of plane rotations. Mention is also made of the possibility of
using plane rotations for pivoting
Latent Roots and Latent Vectors
Get PDFThis book is concerned with the latent roots and latent vectors of matrices whose elements are real. Its main purpose is to discuss some of the methods available for finding latent roots and vectors. The methods presented include not only those that are the most useful in practice, but some chosen because of the interesting ideas they present and the help they give to a general understanding of the latent root and vector problem. I have attempted throughout to introduce the material in as uncomplicated a manner as possible
Bistatic two dimensional synthetic aperture radar as a tensor tomography problem
No full textBistatic radar uses a separate location for the transmitter and receiver, for example on two aircraft or UAVs. The transmitter sends out a pulse and the receiver records its magnitude, for each travel time (we consider the incoherent case, most systems in practice record also the phase).
For each transmitter and receiver position a measurement at a given travel time is the sum of reflections on a prolate spheroid (ellipse in two dimensional case) with the transmitter and receiver as its foci. If the transmitter and receiver are distant from reflectors supported in a small ball the spheroids can be approximated by planes.
Although reflectors are commonly assumed to be isotropic, in practice the relative amplitude of reflection depends on the incoming and outgoing direction, described by the (bistatic) radar scattering cross-section.
In this poster we relate this problem to a tensor Radon transform, which in two dimensions has an explicit singular value decomposition
Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
No full textWe consider the LU factorization of an matrix represented as a block low-rank (BLR) matrix: most of its off-diagonal blocks are approximated by matrices of small rank , which reduces the asymptoticcomplexity of computing the LU factorization of down to \O(n^2r). In this article, our aim is to further reduce this complexity by exploiting fast matrix arithmetic, that is, the ability to multiply two full-rank matrices together for \O(n^\w) flops, where \w<3. This is not straightforward: simply accelerating the intermediate operations performed in the standard BLR factorization algorithm does not suffice to reduce the quadratic complexity in , because these operations are performed on matrices whose size is too small. To overcome this obstacle, we devise a new BLR factorization algorithm that, by recasting the operations so as to work on intermediate matrices of larger size, can exploit more efficiently fast matrix arithmetic. This new algorithm achieves an asymptotic complexity of \O(n^{(\w+1)/2}r^{(\w-1)/2}), which represents an asymptotic improvement compared to the standard BLR factorization as soon as \w<3. In particular, for Strassen's algorithm, \w\approx2.81 yields a complexity of \O(n^{1.904}r^{0.904}). Our numerical experiments are in good agreement with this theoretical result
