MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Backward error and condition of structured linear systems
Get PDFExisting definitions of backward error and condition number for linear systems do not cater to structure in the coefficient matrix, except possibly for sparsity. The definitions are extended so that when the coefficient matrix has structure the perturbed matrix has this structure too. It is shown that when the structure comprises linear dependence on a set of parameters, the structured componentwise backward error is given by the solution of minimal -norm to an underdetermined linear system; an explicit expression for the condition number in this linear case is also obtained. Applications to symmetric matrices, Toeplitz matrices and the least squares problem are discussed and illustrated through numerical examples
The problem of Anisotropy in Electrical Impedance Tomography
No full textThe 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
Componentwise perturbation theory for linear systems with multiple right-hand sides
No full textExisting definitions of componentwise backward error and componentwise condition number for linear systems are extended to systems with multiple right-hand sides and to a general class of componentwise measure of perturbations involving Hölder p-norms. It is shown that for a system of order n with r right-hand sides, the componentwise backward error can be computed by finding the minimum p-norm solutions to n underdetermined linear systems, and an explicit expression is obtained in the case r = 1. A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant. Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse ODE problem
Stability of a method for multiplying complex matrices with three real matrix multiplications
Get PDFBy use of a simple identity, the product of two complex matrices can be formed with three real matrix multiplications and five real matrix additions, instead of the four real matrix multiplications and two real matrix additions required by the conventional approach. This alternative method reduces the number of arithmetic operations, even for small dimensions, achieving a saving of up to 25 percent. The numerical stability of the method is investigated. The method is found to be less stable than conventional multiplication but stable enough to warrant practical use. Issues involved in the choice of method for complex matrix multiplication are discussed, including the relative efficiency of real and complex arithmetic and the backward stability of block algorithms
Dynamics of laminar triple-flamelet structures in non-premixed turbulent combustion
No full textIn the spirit of laminar-flamelet modelling of non-premixed turbulent combustion, a diffusion flamelet is studied. However, the flamelet is also taken to end at a finite position. Such an end of a diffusion flame exhibits fuel-rich and fuel-lean elements as well as the diffusion flame sheet—a structure that is known as a \emph{triple-flame} and which has the property of being able to propagate. A counterflow geometry with shear becomes the most relevant situation in which to picture ends of diffusion flames in a turbulent flow. In an equidiffusive system, the speed of propagation of the end-point is demonstrated to be positive only for relatively limited values of strain or scalar dissipation rate and becomes large and negative towards the higher finite value at which a diffusion flame would extinguish uniformly. The implications of these findings for the behaviour of turbulent diffusion flames are discussed
Algorithm 694: A Collection of Test Matrices in MATLAB
No full textWe present a collection of 45 parametrized test matrices. The matrices are mostly square, dense,
nonrandom, and of arbitrary dimension. The collection includes matrices with known inverses or
known eigenvalues, ill-conditioned or rank deficient matrices, and symmetric, positive definite,
orthogonal, defective, involuntary, and totally positive matrices. For each matrix we give a
MATLAB M-file that generates it
Iterative refinement enhances the stability of QR factorization methods for solving linear equations
No full textIterative refinement is a well-known technique for improving the quality of an approximate solution to a linear system. In the traditional usage residuals are computed in extended precision, but more recent work has shown that fixed precision is sufficient to yield benefits for stability. We extend existing results to show that fixed precision iterative refinement renders anarbitrary linear equations solver backward stable in a strong, componentwise sense, under suitable assumptions. Two particular applications involving theQR factorization are discussed in detail: solution of square linear systems and solution of least squares problems. In the former case we show that one step of iterative refinement suffices to produce a small componentwise relative backward error. Our results are weaker for the least squares problem, but again we find that iterative refinement improves a componentwise measure of backward stability. In particular, iterative refinement mitigates the effect of poor row scaling of the coefficient matrix, and so provides an alternative to the use of row interchanges in the HouseholderQR factorization. A further application of the results is described to fast methods for solving Vandermonde-like systems
Exploiting fast matrix multiplication within the level 3 BLAS
No full textThe Level 3 BLAS (BLAS3) are a set of specifications of FORTRAN 77 subprograms for carrying out matrix multiplications and the solution of triangular systems with multiple right-hand sides. They are intended to provide efficient and portable building blocks for linear algebra algorithms on high-performance computers. We describe algorithms for the BLAS3 operations that are asymptotically faster than the conventional ones. These algorithms are based on Strassen's method for fast matrix multiplication, which is now recognized to be a practically useful technique once matrix dimensions exceed about 100. We pay particular attention to the numerical stability of these “fast BLAS3.” Error bounds are given and their significance is explained and illustrated with the aid of numerical experiments. Our conclusion is that the fast BLAS3, although not as strongly stable as conventional implementations, are stable enough to merit careful consideration in many applications
Stability analysis of algorithms for solving confluent Vandermonde-like systems
Get PDFA confluent Vandermonde-like matrix is a generalisation of the confluent Vandermonde matrix in which the monomials are replaced by arbitrary polynomials. For the case where the polynomials satisfy a three-term recurrence relation algorithms for solving the systems and in operations are derived. Forward and backward error analyses that provide bounds for the relative error and the residual of the computed solution are given. The bounds reveal a rich variety of problem-dependent phenomena, including both good and bad stability properties and the possibility of Xextremely accurate solutions. To combat potential instability, a method is derived for computing a “stable” ordering of the points ; it mimics the interchanges performed by Gaussian elimination with partial pivoting, using only operations. The results of extensive numerical tests are summarised, and recommendations are given for how to use the fast algorithms to solve Vandermonde-like systems in a stable manner
Bounding the error in Gaussian elimination for tridiagonal systems
Get PDFIf is the computed solution to a tridiagonal system obtained by Gaussian elimination, what is the “best” bound available for the error and how can it be computed efficiently? This question is answered using backward error analysis, perturbation theory, and properties of the factorization of . For three practically important classes of tridiagonal matrix, those that are symmetric positive definite, totally nonnegative, or -matrices, it is shown that where the backward error matrix is small componentwise relative to . For these classes of matrices the appropriate forward error bound involves Skeel’s condition number cond , which, it is shown, can be computed exactly in operations. For diagonally dominant tridiagonal the same type of backward error result holds, and the author obtains a useful upper bound for cond that can be computed in operations. Error bounds and their computation for general tridiagonal matrices are discussed also