A decomposition for a stochastic matrix with an application to MANOVA

The aim of this paper is to propose a simple method in order to evaluate the (approximate) distribution of matrix quadratic forms when Wishartness conditions do not hold. The method is based upon a factorization of a general Gaussian stochastic matrix as a special linear combination of nonstochastic matrices with the standard Gaussian matrix. An application of previous result is proposed for matrix quadratic forms arising in MANOVA for a multivariate split-plot design with circular dependence structure.     

Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

An algorithm for finding extremal polytope norms of matrix families

In this paper the problem of the computation of the joint spectral radius of a finite set of matrices is considered. We present an algorithm which, under some suitable assumptions, is able to check if a certain product in the multiplicative semigroup is spectrum maximizing. The algorithm proceeds by attempting to construct a suitable extremal norm for the family, namely a complex polytope norm. As examples for testing our technique, we first consider the set of two 2-dimensional matrices recently analyzed by Blondel, Nesterov and Theys to disprove the finiteness conjecture, and then a set of 3-dimensional matrices arising in the zero-stability analysis of the 4-step BDF formula for ordinary differential equations.     

An algorithm for finding the shortest element of a polyhedral set with application to lagrangian duality

An algorithm is developed which finds the point in a compact polyhedral set with smallest Euclidean norm. At each iteration the algorithm requires knowledge of only those vertices of the set which are adjacent to a current reference vertex. This feature is shown to permit the adoption of the technique to find iteratively the shortest subgradient (i.e. the direction of steepest ascent) of the lagrangian dual function for large scale linear programs. Procedures are presented for finding the direction of steepest ascent in both the equality constraint and the inequality constraint cases of lagrangian duality.     

Efficient algorithm for finding the inverse and the group inverse of FLSr-circulant matrix

An efficient algorithm for finding the inverse and the group inverse of the FLSr-circulant matrix is presented by Euclidean algorithm. Extension is made to compute the inverse of the FLSr-retrocirculant matrix by using the relationship between an FLSr-circulant matrix and an FLSr-retrocirculant matrix. Finally, some examples are given.     

A bound for the condition of a hyperbolic eigenvector matrix

The hyperbolic eigenvector matrix is a matrix X which simultaneously diagonalizes the pair (H,J), where H is Hermitian positive definite and J = diag(±1) such that X*HX = Δ and X*JX = J. We prove that the spectral condition of X, κ(X), is bounded byK(X)√minK(D^*HD), where the minimum is taken over all non-singular matrices D which commute with J. This bound is attainable and it can be simply computed. Similar results hold for other signature matrices J, like in the discretized Klein—Gordon equation.     

Convergence theory for nonconvex stochastic programming with an application to mixed logit

Monte Carlo methods have extensively been used and studied in the area of stochastic programming. Their convergence properties typically consider global minimizers or first-order critical points of the sample average approximation (SAA) problems and minimizers of the true problem, and show that the former converge to the latter for increasing sample size. However, the assumption of global minimization essentially restricts the scope of these results to convex problems. We review and extend these results in two directions: we allow for local SAA minimizers of possibly nonconvex problems and prove, under suitable conditions, almost sure convergence of local second-order solutions of the SAA problem to second-order critical points of the true problem. We also apply this new theory to the estimation of mixed logit models for discrete choice analysis. New useful convergence properties are derived in this context, both for the constrained and unconstrained cases, and associated estimates of the simulation bias and variance are proposed. Research Fellow of the Belgian National Fund for Scientific Research     

The $$$$-means algorithm for 3D shapes with an application to apparel design

Clustering of objects according to shapes is of key importance in many scientific fields. In this paper we focus on the case where the shape of an object is represented by a configuration matrix of landmarks. It is well known that this shape space has a finite-dimensional Riemannian manifold structure (non-Euclidean) which makes it difficult to work with. Papers about clustering on this space are scarce in the literature. The basic foundation of the \(k\)-means algorithm is the fact that the sample mean is the value that minimizes the Euclidean distance from each point to the centroid of the cluster to which it belongs, so, our idea is integrating the Procrustes type distances and Procrustes mean into the \(k\)-means algorithm to adapt it to the shape analysis context. As far as we know, there have been just two attempts in that way. In this paper we propose to adapt the classical \(k\)-means Lloyd algorithm to the context of Shape Analysis, focusing on the three dimensional case. We present a study comparing its performance with the Hartigan-Wong \(k\)-means algorithm, one that was previously adapted to the field of Statistical Shape Analysis. We demonstrate the better performance of the Lloyd version and, finally, we propose to add a trimmed procedure. We apply both to a 3D database obtained from an anthropometric survey of the Spanish female population conducted in this country in 2006. The algorithms presented in this paper are available in the Anthropometry R package, whose most current version is always available from the Comprehensive R Archive Network.     

A test for the bidirectional stochastic order with an application to quality control theory

A test for the bidirectional stochastic ordering is developed in this paper. The main properties of such a test are investigated. The asymptotic distribution of the statistic of the test is obtained under conditions which allow the construction of critical regions with a specific level of significance. It is also proved that the test is consistent on the whole set of alternatives. An application of such a test to quality control theory is developed.     

Guarantees for the success frequency of an algorithm for finding Dodgson-election winners

In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the Θ ₂ ^p level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates—although the number of voters may still be polynomial in the number of candidates—a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it “knows” that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.     

An algorithm for finding an approximate solution to the Weber problem on a line with forbidden gaps

Under study is the problem of optimal location of interconnected objects on a line with forbidden gaps. The task is to minimize the total cost of links between objects and between objects and zones. The properties of the problem are found that allowed us to reduce the initial continuous problem to a discrete problem. Some algorithm for obtaining an approximate solution is developed, and the results of a computational experiment are given.     

A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)

We propose an algorithm for finding the so-called principal solution of the Sylvester matrix equation over max-plus algebra. The derivation of our algorithm is based on the concept of tropical tensor product introduced by Butkovi? and Fiedler. Our algorithm reduces the computational cost of finding the principal solution from quartic to cubic. It also reduces the space complexity from quartic to quadratic. Since matrix–matrix multiplication is the most important ingredient of our proposed technique, we show how to use column-oriented matrix multiplications in order to speed-up MATLAB implementation of our algorithm. Finally, we illustrate our results and discuss the connection with the residuation theory.     

A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Given a positive integer $k$ and an undirected edge-weighted connected simple graph $G$ with at least $k$ edges of positive weight, we wish to partition the graph into $k$ edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible.     

Generalizations of the centroid with an application in stochastic geometry

The centroid of a subset of with positive volume is a well‐known characteristic. An interesting task is to generalize its definition to at least some sets of zero volume. In the presented paper we propose two possible ways how to do that. The first is based on the Hausdorff measure of an appropriate dimension. The second is given by the limit of centroids of ε‐neighbourhoods of the particular set when ε goes to 0. For both generalizations we discuss their existence and basic properties. Then we focus on sufficient conditions of existence of the second generalization and on conditions when both generalizations coincide. It turns out that they can be formulated with the help of the Minkowski content, rectifiability, and self‐similarity. Since the centroid is often used in stochastic geometry as a centre function for certain particle processes, we present properties that are needed for both generalizations to be valid centre functions. Finally, we also show their continuity on compact convex m‐sets with respect to the Hausdorff metric topology.     

On an algorithm for finding the electric potential distribution in the DG-MOSFET transistor

An efficient numerical algorithm for finding the electric potential distribution in the DG-MOSFET transistor is proposed and discussed in detail. The class of hydrodynamic models describing the charge transport in semiconductors includes the Poisson equation for the electric potential. Since the equations of hydrodynamic models are nonlinear and involve small parameters and specific conditions on the boundary of the DG-MOSFET transistor domain, the numerical solution of the Poisson equation meets significant difficulties. An original algorithm is proposed that is based on the stabilization method and the idea of schemes without saturation and helps to cope with these difficulties.     

Rate of convergence of transport processes with an application to stochastic differential equations

Summary We obtain a rate of convergence of uniform transport processes to Brownian motion, which we apply to the Wong and Zakai approximation of stochastic integrals.The research of both authors was supported by a NSERC Canada Grant and by an EMR Canada Grant of M. Csörgö at Carleton University, Ottawa