MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Blocked Schur Algorithms for Computing the Matrix Square Root
Get PDFThe Schur method for computing a matrix square root reduces the matrix to the Schur triangular form and then computes a square root of the triangular matrix. We show that by using either standard blocking or recursive blocking the computation of the square root of the triangular matrix can be made rich in matrix multiplication. Numerical experiments making appropriate use of level 3 BLAS show significant speedups over the point algorithm, both in the square root phase and in the algorithm as a whole. In parallel implementations, recursive blocking is found to provide better performance than standard blocking when the parallelism comes only from threaded BLAS, but the reverse is true when parallelism is explicitly expressed using OpenMP. The excellent numerical stability of the point algorithm is shown to be preserved by blocking. These results are extended to the real Schur method. Blocking is also shown to be effective for multiplying triangular matrices
Robust Stabilized Stokes Approximation Methods for Highly Stretched Grids
No full textAnisotropic meshes are important for efficiently resolving incompressible flow problems that include boundary layer or corner singularity phenomena. Unfortunately, the stability of standard inf–sup stable mixed approximation methods is prone to degeneracy whenever the mesh aspect ratio becomes large. As an alternative, a stabilized mixed approximation method is considered here. Specifically, a robust a priori error estimate for the local jump stabilized Q1–P0 approximation introduced by Kechkar & Silvester (1992, Analysis of locally stabilized mixed finite element methods for the Stokes problem. Math. Comp., 58, 1-10) is established for anisotropic meshes. Our numerical results demonstrate that the stabilized Q1-P0 method is competitive with the nonconforming, nonparametric, rotated approximation method introduced by Rannacher & Turek (1992, Simple nonconforming quadrilateral Stokes element. Numer. Meth. Partial Differential Equations, 8, 97-111)
Matrix Computations in Basic on a Microcomputer
No full textWe consider the efficient implementation of matrix computations in interpreted Basic on a microcomputer. Linear equations routines SGEFA and SGESL from the LINPACK library of Fortran programs are translated into Basic and run on four microcomputers: the Commodore 64, the Amstrad CPC 464, the BBC Microcomputer, and the BBC with a Z-80 second processor. The computational cost of the routines is found to be dominated by subscripting calculations rather than by floating point arithmetic. For the BBC Microcomputer and the Commodore 64, the BLAS routines which constitute the inner loops of SGEFA and SGESL are coded in assembly language; speed increases of factors 2.8 (BBC) and 5.3 (Commodore 64) accrue, and the improved execution times are comparable to ones which have been quoted for the more powerful and expensive IBM PC running under a Fortran compiler. The computational cost of the routines using coded BLAS is found to be dominated by floating point arithmetic, subscripting calculations and other overheads having been reduced to a negligible level, and it is concluded that these hybrid Basic/assembly language routines extract near optimum performance from their host machines. Our findings are shown to be applicable to any matrix routine whose computational cost can be measured in "flops"
Multilevel communication optimal LU and QR factorizations for hierarchical platforms
No full textThis study focuses on the performance of two classical dense linear algebra algorithms, the LU and the QR factorizations, on multilevel hierarchical platforms. We first introduce a performance model called Hierarchical
Cluster Platform (HCP), encapsulating the characteristics of such platforms. The focus is set on reducing the communication requirements of studied algorithms at each level of the hierarchy. Lower bounds on communication are
therefore extended with respect to the \HCP model. We then introduce multilevel LU and QR algorithms tailored for those platforms, and provide a detailed performance analysis. We also provide a set of performance predictions showing the need for such algorithms on large platforms
Sensitivity matrix and reconstruction algorithm for EIT assuming axial uniformity
No full textReferences Cited By Metrics
In electrical impedance tomography (EIT) two-dimensional models continue to be applied despite their known inability to provide correct reconstruction. In this paper, a reconstruction algorithm that assumes a translationally invariant conductivity distribution is described. A more precise forward solver is obtained by taking off-slice currents into consideration. An appropriate sensitivity matrix is derived. Numerical evidence for the improvement in precision compared to two-dimensional reconstruction is given
Classification of symmetry groups for planar n-body choreographies
No full textSince the foundational work of Chenciner and Montgomery in 2000 there has been a great deal of interest in choreographic solutions of the n-body problem: periodic motions where the n bodies all follow one another at regular intervals along a closed path. The principal approach combines variational methods with symmetry properties. In this paper, we give a systematic treatment of the symmetry aspect. In the first part we classify all possible symmetry groups of planar n-body, collision-free choreographies. These symmetry groups fall in to 2 infinite families and, if n is odd, three exceptional groups. In the second part we develop the equivariant fundamental group and use it to determine the topology of the space of loops with a given symmetry, which we show is related to certain cosets of the pure braid group in the full braid group, and to centralizers of elements of the corresponding coset. In particular, we refine the symmetry classification by classifying the connected components of the set of loops with any given symmetry. This leads to the existence of many new choreographies in n-body systems governed by a strong force potential
MCMC Methods for Functions: Modifying Old Algorithms to Make Them Faster
Get PDFMany problems arising in applications result in the need to probe a probability distribution for functions. Examples include Bayesian nonparametric statistics and conditioned diffusion processes. Standard MCMC algorithms typically become arbitrarily slow under the mesh refinement dictated by nonparametric description of the un- known function. We describe an approach to modifying a whole range of MCMC methods, applicable whenever the target measure has density with respect to a Gaussian process or Gaussian random field reference measure, which ensures that their speed of convergence is robust under mesh refinement.
Gaussian processes or random fields are fields whose marginal distri- butions, when evaluated at any finite set of N points, are RN-valued Gaussians. The algorithmic approach that we describe is applicable not only when the desired probability measure has density with respect to a Gaussian process or Gaussian random field reference measure, but also to some useful non-Gaussian reference measures constructed through random truncation. In the applications of interest the data is often sparse and the prior specification is an essential part of the over- all modelling strategy. These Gaussian-based reference measures are a very flexible modelling tool, finding wide-ranging application. Examples are shown in density estimation, data assimilation in fluid mechanics, subsurface geophysics and image registration.
The key design principle is to formulate the MCMC method so that it is, in principle, applicable for functions; this may be achieved by use of proposals based on carefully chosen time-discretizations of stochas- tic dynamical systems which exactly preserve the Gaussian reference measure. Taking this approach leads to many new algorithms which can be implemented via minor modification of existing algorithms, yet which show enormous speed-up on a wide range of applied problems
Version 6 of the consensus yeast metabolic network refines biochemical coverage and improves model performance
Get PDFUpdates to maintain a state-of-the art reconstruction of the yeast metabolic network are essential to reflect our understanding of yeast metabolism and functional organization, to eliminate any inaccuracies identified in earlier iterations, to improve predictive accuracy and to continue to expand into novel subsystems to extend the comprehensiveness of the model. Here, we present version 6 of the consensus yeast metabolic network (Yeast 6) as an update to the community effort to computationally reconstruct the genome-scale metabolic network of Saccharomyces cerevisiae S288c. Yeast 6 comprises 1458 metabolites participating in 1888 reactions, which are annotated with 900 yeast genes encoding the catalyzing enzymes. Compared with Yeast 5, Yeast 6 demonstrates improved sensitivity, specificity and positive and negative predictive values for predicting gene essentiality in glucose-limited aerobic conditions when analyzed with flux balance analysis. Additionally, Yeast 6 improves the accuracy of predicting the likelihood that a mutation will cause auxotrophy. The network reconstruction is available as a Systems Biology Markup Language (SBML) file enriched with Minimium Information Requested in the Annotation of Biochemical Models (MIRIAM)-compliant annotations. Small- and macromolecules in the network are referenced to authoritative databases such as Uniprot or ChEBI. Molecules and reactions are also annotated with appropriate publications that contain supporting evidence. Yeast 6 is freely available at http://yeast.sf.net/ as three separate SBML files: a model using the SBML level 3 Flux Balance Constraint package, a model compatible with the MATLAB® COBRA Toolbox for backward compatibility and a reconstruction containing only reactions for which there is experimental evidence (without the non-biological reactions necessary for simulating growth)
The equivariant K-theory and cobordism rings of divisive weighted projective spaces
Get PDFWe apply results of Harada, Holm and Henriques to prove that the Atiyah-Segal equivariant
complex K-theory ring of a divisive weighted projective space (which is singular for nontrivial
weights) is isomorphic to the ring of integral piecewise Laurent polynomials on the associated
fan. Analogues of this description hold for other complex-oriented equivariant cohomology theories,
as we conrm in the case of homotopical complex cobordism, which is the universal example.
We also prove that the Borel versions of the equivariant K-theory and complex cobordism rings
of more general singular toric varieties, namely those whose integral cohomology is concentrated
in even dimensions, are isomorphic to rings of appropriate piecewise formal power series. Finally,
we conrm the corresponding descriptions for any smooth, compact, projective toric variety, and
rewrite them in a face ring context. In many cases our results agree with those of Vezzosi and
Vistoli for algebraic K-theory, Anderson and Payne for operational K-theory, Krishna and Uma
for algebraic cobordism, and Gonzalez and Karu for operational cobordism; as we proceed, we
summarize the details of these coincidences
Finite -groups with a Frobenius group of automorphisms whose kernel is a cyclic -group
Get PDFSuppose that a finite -group admits a Frobenius group of automorphisms with kernel that is a cyclic -group and with complement . It is proved that if the fixed-point subgroup of the complement
is nilpotent of class , then has a characteristic subgroup of index bounded in terms of ,
, and whose nilpotency class is bounded in terms of and only. Examples show that the condition of being cyclic is essential.
The proof is based on a Lie ring method and a theorem of the
authors and P.~Shumyatsky about Lie rings with a metacyclic
Frobenius group of automorphisms . It is also proved that has a characteristic subgroup of -bounded index whose order and rank are bounded in terms of and the order and rank of , respectively, and whose exponent is bounded in terms of the exponent of