A group majorization ordering for Euclidean distance matrices

This paper investigates some properties of Euclidean distance matrices (EDMs) with focus on their ordering structure. The ordering treated here is the group majorization ordering induced by the group of permutation matrices. By using this notion, we establish two monotonicity results for EDMs: (i) The radius of a spherical Euclidean distance matrix (spherical EDM) is increasing with respect to the group majorization ordering. (ii) The larger an EDM is in terms of the group majorization ordering, the more spread out its eigenvalues are. Minimal elements with respect to this ordering are also described.     

Multispherical Euclidean distance matrices

In this paper we introduce new necessary and sufficient conditions for an Euclidean distance matrix to be multispherical. The class of multispherical distance matrices studied in this paper contains not only most of the matrices studied by Hayden et al. (1996) 2, but also many other multispherical structures that do not satisfy the conditions in Hayden et al. (1996) 2.We also study the information provided by the origin of coordinates when it is placed at the center of the spheres and the origin representation property is satisfied. These vectors associated with the origin of coordinates generate a number of supporting hyperplanes for a family of multispherical matrices and also describe part of the null space of the corresponding distance matrices.     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.     

On the block-structured distance to non-surjectivity of sublinear mappings

We show that the block-structured distance to non-surjectivity of a set-valued sublinear mapping equals the reciprocal of a suitable block-structured norm of its inverse. This gives a natural generalization of the classical Eckart and Young identity for square invertible matrices.Mathematics Subject Classification (1991): 15A12, 65F35, 65F50, 90C25Supported by NSF grant CCF-0092655     

Eigenstructure of distance matrices with an equal distance subset

We characterize the distance matrices with an equal distance subset in terms of eigenstructure and determine EDMs in this class by examination of a lower dimensional matrix.     

On Kendall-Ressel and related distributions

We delineate a connection of Kendall-Ressel and related laws with the lower real branch of Lambert W function. A characterization of the canonical member of Kendall-Ressel class is found. The Letac-Mora interpretation of the reciprocity of two specific NEFs is extended by considering two related reproductive EDMs. A local limit theorem on gamma convergence for the reproductive back-shifted Kendall-Ressel EDM is derived. Each member of this EDM is self-decomposable and unimodal, but not strongly unimodal. The coefficient of variation, skewness and kurtosis of each representative of this EDM are higher than the corresponding measures for the members of gamma and inverse Gaussian EDMs. An integral representation for the lower real branch of Lambert W function is given.     

Modeling host-parasitoid interactions with correlated events

In this paper, we present a host-parasitoid model with correlated events. We apply a block-structured state-dependent (BSDE) approach that provides a methodological tool to model state-dependent Markovian transitions operating in the presence of phases. A particularly appealing feature of the resulting BSDE host-parasitoid model is that it allows us to deal with non-exponential distributional assumptions on a host birth, a parasitoid death, and parasitism, but keeping the dimensionality of the underlying block-structured Markov chain tractable. Numerical examples are presented to illustrate the effects of the correlation structure on the expected extinction times and the extinction probabilities.     

Regularized decomposition of large scale block-structured robust optimization problems

Computational Management Science - We consider a general robust block-structured optimization problem, coming from applications in network and energy optimization. We propose and study an iterative...     

A parallel adaptive grid algorithm for computational shock hydrodynamics

Adaptive Mesh Refinement (AMR) algorithms that dynamically match the local resolution of the computational grid to the numerical solution being sought have emerged as powerful tools for solving problems that contain disparate physical scales. In particular several workers have demonstrated the effectiveness of employing an adaptive, hierarchical block-structured grid system for time-accurate simulations of complex shock wave phenomena. Here we present an overview of one such block-structured AMR algorithm. Our formulation has progressed far beyond the development stage to become a reliable numerical tool for performing detailed investigations of complex flows. While our refinement machinery is not tied to a specific application and is intended for general use, in this paper we adopt detonation phenomena as a theme so as to provide a sense of purpose.     

超音速探测器-刚性盘-缝-带型降落伞系统的大涡模拟研究

研究了Mach数为2时,流场不同块结构自适应网格加密精度对探测器-刚性盘-缝-带型降落伞系统的气动减速性能以及流场结构特性的影响.对于非定常可压缩流体流动,采用了兼顾激波与湍流的WENO(weighted essen-tially non-oscillatory)和TCD(tuned center difference...     

High-multiplicity N-fold IP via configuration LP

Mathematical Programming - N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully...     

Generation of three-dimensional block-structured grids based on rotation of two-dimensional multiply connected cross sections

An algorithm for generating curvilinear block-structured grids in axisymmetric three-dimensional domains of any connectivity is developed. The organization of the connection between the blocks is automated. The grids constructed are used to compute ideal gas steady flows past axisymmetric bodies at a nonzero angle of attack.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

RANS-simulation of premixed turbulent combustion using the level set approach

A model for premixed turbulent combustion is investigated using a RANS-approach. The evolution of the flame front is described with the help of the level set approach [1] which is used for tracking of propagating interfaces in free-surface flows, geodesics, grid generation and combustion. The fluid properties are conditioned on the flame front position using a burntunburnt probability function across the flame front. Computations are performed using the code FASTEST-3D which is a flow solver for a non-orthogonal, block-structured grid. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Geometric decay in level-expanding QBD models

Level-expanding quasi-birth-and-death (QBD) processes have been shown to be an efficient modeling tool for studying multi-dimensional systems, especially two-dimensional ones. Computationally, it changes the more challenging problem of dealing with algorithms for two-dimensional systems to a less challenging one for block-structured transition matrices of QBD type with varying finite block sizes. In this paper, we focus on tail asymptotics in the stationary distribution of a level-expanding QBD process. Specifically, we provide sufficient conditions for geometric tail asymptotics for the level-expanding QBD process, and then apply the result to an interesting two-dimensional system, an inventory queue model.     

An implementation of a parallel primal-dual interior point method for block-structured linear programs

An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.     

Two theorems on Euclidean distance matrices and Gale transform

We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones

where is the elliptope (set of correlation matrices) and is the (closed convex) cone of EDMs.

The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ₁,λ₂,…,λ_n such that

∑_j=1ⁿλ_jp^j=0, ∑_j=1ⁿλ_j=0,

we have

∑_j=1ⁿλ_jpⁱ−p^j2= forall i=1,…,n,

for some scalar independent of i.     

Parallel interior-point solver for structured quadratic programs: Application to financial planning problems

Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other areas such as telecommunication network modelling. We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra. The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems. Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01     

Block-Structured Fluid Queues Driven by QBD Processes

Abstract

In this paper, a unified approach for studying block-structured fluid models is proposed by means of the RG-factorization. When the stochastic environment (or background) is assumed to be a quasi-birth-and death (QBD) process, with either infinitely many levels or finitely many levels, the Laplace transform for the stationary probability distribution of the buffer content is expressed in terms of the R-measure. At the same time, the Laplace-Stieltjes transforms for both the conditional distribution and the conditional mean of a first passage time in such a fluid queue are derived by the same approach.