MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Experience with a Matrix Norm Estimator
Get PDFFortran 77 codes for estimating the 1-norm of a real or complex matrix were presented by Higham in [ACM Trans. Math. Software, 14 (1988), pp. 381–396]. The codes have found use in various applications and have been adopted by two program libraries. Further observations about the norm estimation algorithm and experience in using it are reported here. In particular, an example is given where the algorithm requires nearly the maximum possible number of iterations
Image reconstruction in electrical impedance tomography
Get PDFThis thesis is concerned with Electrical Impedance Tomogaphy (EIT), a medical imaging technique in which pictures of the electrical conductivity distribution of the body are formed from current and voltage data taken on the body surface. The focus of the thesis is on the mathematical aspects of reconstructing the conductivity image from the measured data (the reconstruction problem). The reconstruction problem is particularly difficult and in this thesis it is investigated analytically and numerically. The aim of this investigation is to understand why the problem is difficult and to find
numerical solution methods which respect the difficulties encountered. The analytical investigation of this non-linear inverse problem for an elliptic partial differential equation shows that while the forward mapping is analytic the inverse mapping is discontinuous. A rigorous treatment of the linearisation of the problem is given, including proofs of forms of linearisation assumed by previous authors. It is shown that the derivative of the forward problem is compact. Numerical
calculations of the singular value decomposition (SVD) are given including plots of singular values and images of the singular functions. The SVD is used to settle a controversy concerning current drive patterns.
Reconstruction algorithms are investigated and use of Regularised Newton methods is suggested. A formula for the second derivative of the forward mapping is derived which proves too computationally expensive to calculate. Use of Tychonov regularisation as well as filtered SVD and
iterative methods are discussed. The similarities, and differences, between EIT and X-Ray Computed Tomography (X-Ray CT) are illuminated. This leads to an explanation of methods used by other authors for EIT reconstuction based on X-Ray CT. Details of the author's own implementation of a regularised Newton method are given. Finally the idea of adaptive current patterns is investigated. An algorithm is given for the experimental determination of optimal
current patterns and the integration of this technique with
regularised Newton methods is explored. Promising numerical results from this technique are given.
The thesis concludes with a discussion of some outstanding problems in EIT and points to possible routes for their solution. An appendix gives brief details of the design and development of the Oxford Polytechnic Adaptive Current Tomograph
Analysis of the Cholesky Decomposition of a Semi-definite Matrix
Get PDFPerturbation theory is developed for the Cholesky decomposition of an symmetric positive semidefinite matrix of rank~. The matrix
W=\All^{-1}\A{12} is found to play a key role in the perturbation bounds,
where \All and \A{12} are and submatrices of
respectively.
A backward error analysis is given; it shows that the computed Cholesky
factors are the exact ones of a matrix whose distance from is bounded by
4r(r+1)\bigl(\norm{W}+1\bigr)^2u\norm{A}+O(u^2), where is the unit
roundoff. For
the complete pivoting strategy it is shown that \norm{W}^2 \le {1 \over
3}(n-r)(4^r- 1), and empirical evidence that \norm{W} is usually small is
presented. The overall conclusion is that the Cholesky algorithm with complete
pivoting is stable for semi-definite matrices.
Similar perturbation results are derived for the QR decomposition with column
pivoting and for the LU decomposition with complete pivoting. The results give
new insight into the reliability of these decompositions in rank estimation
Fast polar decomposition of an arbitrary matrix
Get PDFThe polar decomposition of an matrix of full rank, where , can be computed using a quadratically convergent algorithm of Higham [SIAM J. Sci. Statist. Comput., 7(1986), pp. 1160–1174]. The algorithm is based on a Newton iteration involving a matrix inverse. It is shown how, with the use of a preliminary complete orthogonal decomposition, the algorithm can be extended to arbitrary . The use of the algorithm to compute the positive semidefinite square root of a Hermitian positive semidefinite matrix is also described. A hybrid algorithm that adaptively switches from the matrix inversion based iteration to a matrix multiplication based iteration due to Kovarik, and to Björck and Bowie, is formulated. The decision when to switch is made using a condition estimator. This “matrix multiplication rich” algorithm is shown to be more efficient on machines for which matrix multiplication can be executed 1.5 times faster than matrix inversion
Analysis of the Cholesky Decomposition of a Semi-definite Matrix
Get PDFPerturbation theory is developed for the Cholesky decomposition of an symmetric positive semidefinite matrix of rank~. The matrix
W=\All^{-1}\A{12} is found to play a key role in the perturbation bounds,
where \All and \A{12} are and submatrices of
respectively.
A backward error analysis is given; it shows that the computed Cholesky
factors are the exact ones of a matrix whose distance from is bounded by
4r(r+1)\bigl(\norm{W}+1\bigr)^2u\norm{A}+O(u^2), where is the unit
roundoff. For
the complete pivoting strategy it is shown that \norm{W}^2 \le {1 \over
3}(n-r)(4^r- 1), and empirical evidence that \norm{W} is usually small is
presented. The overall conclusion is that the Cholesky algorithm with complete
pivoting is stable for semi-definite matrices.
Similar perturbation results are derived for the QR decomposition with column
pivoting and for the LU decomposition with complete pivoting. The results give
new insight into the reliability of these decompositions in rank estimation
Large growth factors in Gaussian elimination with pivoting
Get PDFThe growth factor plays an important role in the error analysis of Gaussian elimination. It is well known that when partial pivoting or complete pivoting is used the growth factor is usually small, but it can be large. The examples of large growth usually quoted involve contrived matrices that are unlikely to occur in practice. We present real and complex matrices arising from practical applications that, for any pivoting strategy, yield growth factors bounded below by and , respectively. These matrices enable us to improve the known lower bounds on the largest possible growth factor in the case of complete pivoting. For partial pivoting, we classify the set of real matrices for which the growth factor is . Finally, we show that large element growth does not necessarily lead to a large backward error in the solution of a particular linear system, and we comment on the practical implications of this result
Analysis of thermal runaway in the ignition process
No full textThe evolution of a thermal runaway event is studied from the time a self-sustained temperature growth first sets in to the time deflagration flames begin to emerge. Proper modeling of the effect of conduction on the distribution of temperature growth reveals that it enhances the overall rate of release of chemical energy. It is shown that this contributes to the likelihood of substantial pressure increases being produced at some stage, and a criterion is identified for this to happen. In the absence of such pressure effects, the results are valid over a wide range of degrees of supercriticality, from marginal cases to cases in which conductive heat losses start off being very small indeed
Flame propagation in a nonuniform mixture: analysis of a slowly varying triple flame
No full textFor flames propagating through a nonuniform medium a three-flame structure is described. This consists of a feul-rich premixed flame, a feul-lean premixed flame, and, starting where these flames meet, a diffusion flame. Such formations have been observed experimentally and probably occur as laminar flamelets in turbulent diffusion flames. A low-heat-release model for such flame structures is developed and solutions are obtained in the limit of slowly varying premixed flames. Under these conditions, it is shown that the Triple-Flame propagation speed depends on the transverse mixture fraction gradient and is bounded from above by the maximum adiabatic laminar flame speed of the system
Ghosts of Order on the Frontier of Chaos
Get PDFWhat kinds of motion can occur in classical mechanics? We address this question by looking at the structures traced out by trajectories in phase space; the most orderely, completely integrable systems are characterized by phase trajectories confined to low-dimensional, invariant tori. The KAM theory examines what happens to the tori when an integrable system is subjected to a small perturbation and finds that, for small enough perturbations, most of them survive.
The KAM theory is mute about the disrupted tori, but, for two dimensional systems, Aubry and Mather discovered an astonishing picture: the broken tori are replaced by "cantori", tattered, Cantor-set remnants of the original invariant curves. We seek to extend Aubry and Mather's picture to higher dimensional systems and report two kinds of studies; both concern perturbations of a completely integrable, four-dimensional symplectic map. In the first study we compute some numerical approximations to Birkhoff periodic orbits; sequences of such orbits should approximate any higher dimensional analogs of the cantori. In the second study we prove converse KAM theorems; that is, we use a combination of analytic arguments and rigorous, machine-assisted computations to find perturbations so large that no KAM tori survive. We are able to show that the last few of our Birkhoff orbits exist in a regime where there are no tori
