MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Conjugate p-elements of Full Support that Generate the Wreath Product Cp wr Cp
Get PDFFor a symmetric group G:=Sym(n) and a conjugacy class X of involutions in G, it is known that if the class of involutions does not have a unique fixed point, then - with a few small exceptions - given two elements a,x in X, either is isomorphic to the dihedral group D8, or there is a further element y in X such that and are both isomorphic to D8 (P. Rowley and D. Ward, On pi-Product Involution Graphs in Symmetric Groups. MIMS ePrint, 2014).
One natural generalisation of this to p-elements is to consider when two conjugate p-elements generate a wreath product of two cyclic groups of order p. In this paper we give a necessary and sufficient condition for this in the case that our p-elements have full support
Technical report on backward stability of polynomial root-finding using Fiedler companion matrices
Get PDF{Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyze the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial , the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, are the set of roots of a nearby polynomial or not. We show that, if the coefficients of are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favorable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial is large, companion Fiedler matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change, to first order, of the characteristic polynomial coefficients of Fielder matrices under small perturbations. We show that, for all Fiedler matrices except the Frobenius ones, this change involves quadratic terms in the coefficients of the characteristic polynomial of the original matrix, while for the Frobenius matrices it only involves linear terms. We present extensive numerical experiments that support these theoretical results. The effect of balancing these matrices is also investigated
Numerical Linear Algebra Problems in Structural Analysis
Get PDFA range of numerical linear algebra problems that arise in finite element-based structural analysis are considered.
These problems were encountered when implementing the finite element method in the software package Oasys GSA.
We present novel solutions to these problems in the form of a new method for error detection, algorithms with superior numerical efficiency and algorithms with scalable performance on parallel computers.
The solutions and their corresponding software implementations have been integrated into GSA's program code and we present results that demonstrate the use of these implementations by engineers to solve real-world structural analysis problems.
We start by introducing a new method for detecting the sources of ill conditioning in finite element stiffness matrices.
The stiffness matrix can become ill-conditioned due to a variety of errors including user errors, i.e., errors in the definition of the finite element model when using a software package.
We identify two classes of errors and develop a new method called model stability analysis for detecting where in the structural model these errors arise.
Our method for debugging models uses the properties of the eigenvectors associated with the smallest and largest eigenvalues of the stiffness matrix to identify parts of the structural model that are badly defined.
Through examples, we demonstrate the use of model stability analysis on real-life models and show that upon fixing the errors identified by the method, the condition number of the matrices typically drops from to .
In the second part we introduce the symmetric definite generalized eigenproblem and the symmetric eigenproblem that are encountered in structural analysis.
The symmetric definite generalized eigenvalue problem is to solve for the smallest eigenvalues and associated eigenvectors of for a symmetric positive-definite, sparse stiffness matrix and a symmetric semidefinite mass matrix .
%We seek the eigenvalues and associated eigenvectors closest to 0 for this problem.
We analyse the existing solution algorithm, which uses the subspace iteration method.
We improve the numerical efficiency of the algorithm by accelerating convergence via novel shift strategies and by reducing floating point operations using selective re-orthogonalization and locking of converged eigenvectors.
The software implementation also benefits from improvements such as the use of faster and more robust libraries for linear algebra operations encountered during the iteration.
We then develop an implementation of the subspace iteration method for solving the symmetric eigenvalue problem for the smallest and largest eigenvalues and their eigenvectors; this problem arises in model stability analysis.
In the next part we tackle the main bottleneck of sparse matrix computations in our eigensolvers: the sparse matrix-multiple vector multiplication kernel.
We seek to obtain an algorithm that has high computational throughput for the operation for a square sparse and a conforming skinny, dense which, in turn, depends on the underlying storage format of .
Current sparse matrix formats and algorithms have high bandwidth requirements and poor reuse of cache and register loaded entries, which restricts their performance.
We propose the mapped blocked row format: a bitmapped sparse matrix format that stores entries as blocks without a fill overhead, thereby offering blocking without additional storage and bandwidth overheads.
An efficient algorithm decodes bitmaps using de Bruijn sequences and minimizes the number of conditionals evaluated.
Performance is compared with that of popular formats, including vendor implementations of sparse BLAS.
Our sparse matrix multiple-vector multiplication algorithm achieves high throughput on all platforms and is implemented using platform-neutral optimizations.
The last part of the thesis deals with the -orthogonalization problem, i.e., for a sparse symmetric positive definite B \in \R^{\nbyn} and a tall skinny matrix X \in \R^{\nbyl}, we wish to rotate the columns of such that .
This problem arises when the engineer wishes to orthonormalize the eigenvectors of the generalized eigenproblem such that they are orthogonal with respect to the stiffness matrix.
Conventionally in the literature Gram-Schmidt like methods are employed for \bo ization but they have poor cache efficiency.
We recall a method that uses the Cholesky factorization of the inner product matrix and derive a stable algorithm that increases the parallel scalability through cache-reuse and is also numerically stable.
Our experiments demonstrate orders of magnitude improvement in performance compared with Gram-Schmidt family of methods
Estimating the Condition Number of the Frechet Derivative of a Matrix Function
Get PDFThe Fr\'{e}chet derivative of a matrix function is used in a variety of applications and several algorithms are available for computing it. We define a condition number for the Fr\'{e}chet derivative and derive upper and lower bounds for it that differ by at most a factor . For a wide class of functions we derive an algorithm for estimating the 1-norm condition number that requires flops given flops algorithms for evaluating and ; in practice it produces estimates correct to within a factor . Numerical experiments show the new algorithm to be much more reliable than a previous heuristic estimate of conditioning
Algorithms and theory for polynomial eigenproblems
Get PDFIn this thesis we develop new theoretical and numerical results for matrix polynomials and polynomial eigenproblems. This includes the cases of standard and generalized eigenproblems.
Two chapters concern quadratic eigenproblems , where , and enjoy special properties that are commonly encountered in modal analysis. We discuss this application in some detail, in particular the mathematics behind discrete dampers. We show how the physical intuition of a damper that gets stronger and stronger can be mathematically proved using matrix analysis. We then develop an algorithm for quadratic eigenvalue problems with low rank damping, which outperforms existing algorithm both in terms of speed and accuracy. The first part of our algorithm requires the solution of a generalized eigenproblem with semidefinite coefficient matrices. To solve this problem we develop a new algorithm based on an algorithm proposed by Wang and Zhao [SIAM J. Matrix Anal. Appl. 12-4 (1991), pp.
654--660]. The new algorithm computes all eigenvalues in a backward stable and symmetry preserving manner.
The next two chapters are about equivalences of matrix polynomials. We show, for an algebraically closed field , that any matrix polynomial , , can be
reduced to triangular form,
while preserving the degree and the finite and infinite elementary divisors.
We then show that the same result holds for real matrix polynomials if we replace ``triangular'' with ``quasi-triangular,'' that is, block-triangular with diagonal blocks of size and . The proofs are constructive in the sense that we build up triangular and quasi-triangular matrix polynomials starting the Smith form. In this sense we are solving structured inverse problems. In particular, our results imply that the necessary constraints that make list of elementary divisors admissible for a real square matrix polynomial of degree are also sufficient conditions. For the case of matrix polynomials with invertible leading coefficients, we show how triangular/quasi-triangular forms, as well as diagonal and Hessenberg forms, can be computed numerically.
Finally, we present a backward error analysis of the shift-and-invert Arnoldi algorithm for matrices. This algorithm is also of interest to polynomial eigenproblems with easily constructible monic linearizations. The analysis shows how errors from the linear system solves and orthonormalization process affect the Arnoldi recurrence. Residual bounds for linear systems and columnwise backward error bounds for QR factorizations come to play, so we discuss these in some detail. The main result is a set of backward error bounds that can be estimated cheaply. We also use our error analysis to define a sensible condition for ``breakdown,'' that is, a condition for when the Arnoldi iteration should be stopped
Invariant measures for the n-dimensional border collision normal form
Get PDFThe border collision normal form is a continuous piecewise affine map of \BR^n with applications in piecewise smooth bifurcation theory. We show that these maps have absolutely continuous invariant measures for an open set of parameter space and hence that the attractors have Hausdorff (fractal) dimension . If the attractors have topological dimension two, i.e. they contain open sets, and if then they have topological dimension generically
The Matrix Unwinding Function, with an Application to Computing the Matrix Exponential
No full textA new matrix function corresponding to the scalar unwinding number of
Corless, Hare, and Jeffrey is introduced.
This matrix unwinding function, , is shown to
be a valuable tool for deriving
identities involving the matrix logarithm and
fractional matrix powers,
revealing, for example, the
precise relation between and .
The unwinding function is also shown to be closely connected with the matrix
sign function.
An algorithm for computing the unwinding function based on the
Schur--Parlett method with a special reordering is proposed.
It is shown that matrix argument reduction using the function
,
which has eigenvalues with imaginary parts in the interval
and for which \e^A = \e^{\mathrm{mod}(A)},
can give significant computational savings in the evaluation
of the exponential by scaling and squaring algorithms
A preconditioned MINRES method for nonsymmetric Toeplitz matrices
Get PDFCirculant preconditioning for symmetric Toeplitz linear systems is well-established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in Gil Strang's `Proposal for Toeplitz Matrix Calculations' (Studies in Applied Mathematics, 74, pp. 171-176, 1986.). For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available.
In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established
Orbits on k-subsets of 2-transitive Simple Lie-type Groups
No full textFor a finite rank one simple Lie-type group acting 2-transitively on a set we derive formulae for the number of G-orbits on the set of all k-subsets
Restoring Definiteness via Shrinking, with an Application to Correlation Matrices with a Fixed Block
Get PDFIndefinite estimates of positive semidefinite matrices arise in many data analysis applications involving covariance matrices and correlation matrices. We develop a method for restoring positive semidefiniteness of an indefinite estimate based on the process of shrinking, which finds a convex linear combination of the original matrix and a target positive semidefinite matrix . We describe three \alg s for computing the optimal shrinking parameter \alpha_* = \min \{\alpha \in [0,1] : \mbox{S(\alpha) is positive semidefinite}\}. One algorithm is based on the bisection method, with the use of Cholesky factorization to test definiteness, a second employs Newton's method, and a third finds the smallest eigenvalue of a symmetric definite generalized eigenvalue problem. We show that weights that reflect confidence in the individual entries of can be used to construct a natural choice of the target matrix . We treat in detail a problem variant in which a positive semidefinite leading principal submatrix of remains fixed, showing how the fixed block can be exploited to reduce the cost of the bisection and generalized eigenvalue methods. Numerical experiments show that when applied to estimates of correlation matrices shrinking can be at least an order of magnitude faster than computing the nearest correlation matrix