MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
A class of noncommutative projective surfaces
Get PDFLet A=k+A_1+A_2.... be a connected graded, noetherian k-algebra that is generated in degree one over an algebraically closed field k. Suppose that the graded quotient ring Q(A) has the form Q(A)=k(Y)[t,t^{-1},sigma], where sigma is an automorphism of the integral projective surface Y. Then we prove that A can be written as a naive blowup algebra of a projective surface X birational to Y. This enables one to obtain a deep understanding of the structure of these algebras; for example, generically they are not strongly noetherian and their point modules are not parametrized by a projective scheme. This is despite the fact that the simple objects in the quotient category qgr A will always be in (1-1) correspondence with the closed points of the scheme X
Towards Dense Linear Algebra for Hybrid GPU Accelerated Manycore Systems
Get PDFIf multicore is a disruptive technology, try to imagine hybrid multicore systems
enhanced with accelerators! This is happening today as accelerators, in particular Graphics
Processing Units (GPUs), are steadily making their way into the high performance computing
(HPC) world. We highlight the trends leading to the idea of hybrid manycore/GPU systems,
and we present a set of techniques that can be used to eciently program them. The presentation
is in the context of Dense Linear Algebra (DLA), a major building block for many
scientic computing applications.We motivate the need for new algorithms that would split the
computation in a way that would fully exploit the power that each of the hybrid components
oers. As the area of hybrid multicore/GPU computing is still in its infancy, we also argue
for its importance in view of what future architectures may look like. We therefore envision
the need for a DLA library similar to LAPACK but for hybrid manycore/GPU systems. We
illustrate the main ideas with an LU-factorization algorithm where particular techniques are
used to reduce the amount of pivoting, resulting in an algorithm achieving up to 388 GFlop/s
for single and up to 99:4 GFlop/s for double precision factorization on a hybrid Intel Xeon
(2x4 cores @ 2.33 GHz) { NVIDIA GeForce GTX 280 5 (240 cores @ 1.30 GHz) system
Detecting and Solving Hyperbolic Quadratic Eigenvalue Problems
Get PDFHyperbolic quadratic matrix polynomials are an important class of
Hermitian matrix polynomials
with real eigenvalues, among which the overdamped quadratics are those
with nonpositive eigenvalues.
Neither the definition of overdamped nor any of the standard
characterizations provides an efficient way to test if a given
has this property.
We show that a quadratically convergent matrix iteration based on
cyclic reduction, previously studied by Guo and Lancaster,
provides necessary and sufficient conditions for to be overdamped.
For weakly overdamped the iteration is shown to be generically linearly
convergent with constant at worst 1/2,
which implies that
the convergence of the iteration is reasonably fast in almost all
cases of practical interest.
We show that the matrix iteration can be implemented in such a way
that when overdamping is detected a scalar is
provided that lies in the gap between the largest and
smallest eigenvalues of the
quadratic eigenvalue problem (QEP) .
Once such a is known, the QEP can be solved by linearizing to a
definite pencil that can be reduced using already available
Cholesky factorizations to a standard Hermitian eigenproblem.
By incorporating an initial preprocessing stage that shifts a
hyperbolic so that it is overdamped,
we obtain an efficient algorithm that identifies and solves a hyperbolic or
overdamped QEP maintaining symmetry throughout and guaranteeing real
computed eigenvalues
Flux balance analysis: A geometric perspective
Get PDFAdvances in the field of bioinformatics have led to reconstruction of genome-scale networks for a number of key organisms. The application of physicochemical constraints to these stoichiometric networks allows researchers, through methods such as flux balance analysis, to highlight key sets of reactions necessary to achieve particular objectives. The key benefits of constraint-based analysis lie in the minimal knowledge required to infer systemic properties. However, network degeneracy leads to a large number of flux distributions that satisfy any objective; moreover, these distributions may be dominated by biologically irrelevant internal cycles. By examining the geometry underlying the problem, we define two methods for finding a unique solution within the space of all possible flux distributions; such a solution contains no internal cycles, and is representative of the space as a whole. The first method draws on typical geometric knowledge, but cannot be applied to large networks because of the high computational complexity of the problem. Thus a second method, an iteration of linear programs which scales easily to the genome scale, is defined. The algorithm is run on four recent genome-scale models, and unique flux solutions are found. The algorithm set out here will allow researchers in flux balance analysis to exchange typical solutions to their models in a reproducible format. Moreover, having found a single solution, statistical analyses such as correlations may be performed
On Spherical Classes in H*QSn
Get PDFWe consider the problem of determining spherical classes in HQS1. We take a
geometrical approach and show how existence of specific classes as a spherical class
in HQS1 will determine the type of homology operations that can detect the related
homotopy class. Most of our results here are quite general, and can be applied to
HQX, with X an arbitrary path connected space . We see this as an approach to
attack the conjecture of Ed Curtis about spherical classes in HQ0S0
Capturing the essence of a metabolic network: A flux balance analysis approach
Get PDFAs genome-scale metabolic reconstructions emerge, tools to manage their size and complexity will be increasingly important. Flux Balance Analysis (FBA) is a constraint-based approach widely used to study the metabolic capabilities of cellular or subcellular systems. FBA problems are highly underdetermined and many different phenotypes can satisfy any set of constraints through which the metabolic system is represented.
Two of the main concerns in FBA are exploring the space of solutions for a given metabolic network and finding a specific phenotype which is representative for a given task such as maximal growth rate. Here we introduce a recursive algorithm suitable for overcoming both of these concerns. The method proposed is able to find the alternate optimal patterns of active reactions of a FBA problem and identify the minimal subnetwork able to perform a specific task as optimally as the whole.
Our method represents an alternative to and an extension of other approaches conceived for exploring the space of solutions of an FBA problem. It may also be particularly helpful in defining a scaffold of reactions upon which to build up a dynamic model, when the important pathways of the system have not yet been well-defined
Jordan Structures of Alternating Matrix Polynomials
Get PDFAlternating matrix polynomials, that is, polynomials whose coecients alternate
between symmetric and skew-symmetric matrices, generalize the notions of even and odd
scalar polynomials. We investigate the Smith forms of alternating matrix polynomials,
showing that each invariant factor is an even or odd scalar polynomial. Necessary and
sucient conditions are derived for a given Smith form to be that of an alternating
matrix polynomial. These conditions allow a characterization of the possible Jordan
structures of alternating matrix polynomials, and also lead to necessary and sucient
conditions for the existence of structure-preserving strong linearizations. Most of the
results are applicable to singular as well as regular matrix polynomials
A simple yet effective a posteriori estimator for classical mixed approximation of Stokes equations
Get PDFThe implementation of quadratic velocity, linear pressure finite element approximation methods for the steady-state incompressible (Navier-)
Stokes equations is addressed in this work. Three types of a posteriori error indicator are introduced and are shown to give global error estimates that are equivalent to the true discretisation error. Computational results suggest that the solution of local Poisson problems provides a cost-effective error estimation strategy, both from the perspective of accurate estimation of the global error and for the purpose of selecting elements for refinement within a contemporary self-adaptive refinement algorithm
Linearizations of Singular Matrix Polynomials and the Recovery of Minimal Indices
Get PDFA standard way of dealing with a regular matrix polynomial P(¸) is to convert it into
an equivalent matrix pencil { a process known as linearization. Two vector spaces of pencils L1(P)
and L2(P) that generalize the ¯rst and second companion forms have recently been introduced by
Mackey, Mackey, Mehl and Mehrmann. Almost all of these pencils are linearizations for P(¸) when
P is regular. The goal of this work is to show that most of the pencils in L1(P) and L2(P) are still
linearizations when P(¸) is a singular square matrix polynomial, and that these linearizations can
be used to obtain the complete eigenstructure of P(¸), comprised not only of the ¯nite and in¯nite
eigenvalues, but also for singular polynomials of the left and right minimal indices and minimal bases.
We show explicitly how to recover the minimal indices and bases of the polynomial P(¸) from the
minimal indices and bases of linearizations in L1(P) and L2(P). As a consequence of the recovery
formulae for minimal indices, we prove that the vector space DL(P) = L1(P) \ L2(P) will never
contain any linearization for a square singular polynomial P(¸). Finally, the results are extended to
other linearizations of singular polynomials de¯ned in terms of more general polynomial base
Preconditioning stochastic Galerkin saddle point systems
Get PDFMixed finite element discretizations of deterministic second-order elliptic partial differential equations (PDEs) lead to saddle point systems for which the study of iterative solvers and preconditioners is mature. Galerkin approximation of solutions of stochastic second-order elliptic PDEs, which couple standard mixed finite element discretizations in physical space with global polynomial
approximation on a probability space, also give rise to linear systems with familiar saddle point structure. For stochastically nonlinear problems, the solution of such systems presents a serious computational challenge. The blocks are sums of Kronecker products of pairs of matrices associated with two distinct discretizations and the systems are large, reflecting the curse of dimensionality
inherent in most stochastic approximation schemes. Moreover, for the problems considered herein, the leading blocks of the saddle point matrices are block-dense and the cost of a matrix vector product is non-trivial.
We implement a stochastic Galerkin discretization for the
steady-state diffusion problem written as a mixed first-order system. The diffusion coefficient is assumed to be a lognormal random field, approximated via a nonlinear function of a finite number of unbounded random parameters. We study the resulting saddle point systems and investigate the efficiency of block-diagonal preconditioners of Schur complement and augmented type, for use with MINRES. By introducing so-called Kronecker product preconditioners we improve the robustness of cheap, mean-based preconditioners with respect to the statistical properties of the stochastically nonlinear diffusion coefficients