MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures
Get PDFWe present a new parallel implementation of a divide and conquer algorithm for computing the spectral decomposition of a symmetric tridiagonal matrix on distributed memory architectures. The implementation we develop differs from other implementations in that we use a two-dimensional block cyclic distribution of the data, we use the Löwner theorem approach to compute orthogonal eigenvectors, and we introduce permutations before the back transformation of each rank-one update in order to make good use of deflation. This algorithm yields the first scalable, portable, and numerically stable parallel divide and conquer eigensolver. Numerical results confirm the effectiveness of our algorithm. We compare performance of the algorithm with that of the QR algorithm and of bisection followed by inverse iteration on an IBM SP2 and a cluster of Pentium PIIs
Uniqueness, Shape, and Dimension in EIT
Get PDFWe briefly review the known mathematical results on uniqueness of solution in electrical impedance tomography (EIT). Generally, a real or complex conductivity is determined uniquely by complete boundary data. Uniqueness results are also known for planar resistor networks. However, it is common to make gross errors in the forward modeling of the electrical fields and this may result in no consistent solution. In particular, a two-dimensional model is often used when data are collected from a three-dimensional domain. The boundary shape is often inaccurately known, and commonly modeled by a circle. No model conductivity consistent with measured data exists when the dimension or the boundary shape is wrong
Modifying the interia of matrices arising in optimization
No full textApplications in constrained optimization (and other areas) produce symmetric matrices with a natural block 2 × 2 structure. An optimality condition leads to the problem of perturbing the (1,1) block of the matrix to achieve a specific inertia. We derive a perturbation of minimal norm, for any unitarily invariant norm, that increases the number of nonnegative eigenvalues by a given amount, and we show how it can be computed efficiently given a factorization of the original matrix. We also consider an alternative way to satisfy the optimality condition based on a projection approach. Theoretical tools developed here include an extension of Ostrowski's theorem on congruences and some lemmas on inertias of block 2 × 2 symmetric matrices
Factorizing complex symmetric matrices with positive definite real and imaginary parts
No full textComplex symmetric matrices whose real and imaginary parts are positive definite are shown to have a growth factor bounded by 2 for LU factorization. This result adds to the classes of matrix for which it is known to be safe not to pivot in LU factorization. Block factorization with the pivoting strategy of Bunch and Kaufman is also considered, and it is shown that for such matrices only pivots are used and the same growth factor bound of 2 holds, but that interchanges that destroy band structure may be made. The latter results hold whether the pivoting strategy uses the usual absolute value or the modification employed in LINPACK and LAPACK
Nonuniqueness in diffusion-based optical tomography
Get PDFA condition on nonuniqueness in optical tomography is stated. The main result applies to steady-state (dc) diffusion-based optical tomography, wherein we demonstrate that simultaneous unique recovery of diffusion and absorption coefficients cannot be achieved. A specific example of two images that give identical dc data is presented. If the refractive index is considered an unknown, then nonuniqueness also occurs in frequency-domain and time-domain optical tomography, if the underlying model of the diffusion approximation is employed
Delay embedding in the presence of dynamical noise
No full textWe present a new embedding theorem for time series, in the spirit of
Takens's theorem, but requiring multivariate signals. Our result is part
of a growing body of work that extends the
domain of geometric time series analysis to some genuinely
stochastic systems---including such natural examples as
x_{j+1} = \phi(x_j) + \eta_j
where \phi is some fixed map and the \eta_j
are i.i.d. random displacements
A modified Cholesky algorithm based on a symmetric indefinite factorization
Get PDFGiven a symmetric and not necessarily positive definite matrix A, a modified Cholesky algorithm computes a Cholesky factorization P(A+E)PT = RT R, where P is a permutation matrix and E is a perturbation chosen to make A+E positive definite. The aims include producing a small-normed E and making A+E reasonably well conditioned. Modified Cholesky factorizations are widely used in optimization. We propose a new modified Cholesky algorithm based on a symmetric indefinite factorization computed using a new pivoting strategy of Ashcraft, Grimes, and Lewis. We analyze the effectiveness of the algorithm, both in theory and practice, showing that the algorithm is competitive with the existing algorithms of Gill, Murray, and Wright and Schnabel and Eskow. Attractive features of the new algorithm include easy-to-interpret inequalities that explain the extent to which it satisfies its design goals, and the fact that it can be implemented in terms of existing software
The evolution of finite-amplitude wavetrains in plane channel flow
No full textWe consider a viscous incompressible fluid flow driven between two parallel plates
by a constant pressure gradient. The flow is at a finite Reynolds number, with an
O(1) disturbance in the form of a travelling wave. A phase equation approach is
used to discuss the evolution of slowly varying fully nonlinear two-dimensional wave-
trains. We consider uniform wavetrains in detail, showing that the development of
a wavenumber perturbation is governed by the Burgers equation in most cases. The
wavenumber perturbation theory, constructed by using the phase equation approach
for a uniform wavetrain, is shown to be distinct from an amplitude perturbation
expansion about the periodic flow. In fact, we show that the amplitude equation
contains only linear terms and is simply the heat equation. We review, briefly, the
well-known dynamics of the Burgers equation, which imply that both shock struc-
tures and finite-time singularities of the wavenumber perturbation can occur with
respect to the slow scales. Numerical computations have been performed to iden-
tify areas of the {wavenumber, Reynolds number, energy} neutral surface for which
each of these possibilities can occur. We note that the evolution equations will break
down under certain circumstances, in particular for a weakly nonlinear secondary
flow. Finally, we extend the theory to three dimensions and discuss the limit of a
weak spanwise dependence for uniform wavetrains, showing that two functions are
required to describe the evolution. These unknowns are a phase and a pressure func-
tion which satisfy a pair of linearly coupled partial differential equations. The results
obtained from applying the same analysis to the fully three-dimensional problem are
included as an appendix
Boundary Shape and Electrical Impedance Tomography
Get PDFIn electrical impedance tomography the boundary shape is often inaccurately known. If the boundary shape is wrong (in a three-dimensional problem) there will not generally be an isotropic conductivity which fits the current and voltage data. Both the conductivity and boundary shape can be determined by electrical data together with three spatial measurements. In two dimensions errors in boundary shape could be accounted for by a change in conductivity, but not if the length scale on the boundary is also known
Structured backward error and condition of generalized eigenvalue problems
Get PDFBackward errors and condition numbers are defined and evaluated for eigenvalues and eigenvectors of generalized eigenvalue problems. Both normwise and componentwise measures are used. Unstructured problems are considered first, and then the basic definitions are extended so that linear structure in the coefficient matrices (for example, Hermitian, Toeplitz, Hamiltonian, or band structure) is preserved by the perturbations