Rehabilitation of the Gauss-Jordan algorithm

Summary In this paper a Gauss-Jordan algorithm with column interchanges is presented and analysed. We show that, in contrast with Gaussian elimination, the Gauss-Jordan algorithm has essentially differing properties when using column interchanges instead of row interchanges for improving the numerical stability. For solutions obtained by Gauss-Jordan with column interchanges, a more satisfactory bound for the residual norm can be given. The analysis gives theoretical evidence that the algorithm yields numerical solutions as good as those obtained by Gaussian elimination and that, in most practical situations, the residuals are equally small. This is confirmed by numerical experiments. Moreover, timing experiments on a Cyber 205 vector computer show that the algorithm presented has good vectorisation properties.     

Fibrations of bigroupoids

Using Brown's construction (J. Algebra 15 (1970) 103) of an exact 6-term sequence for a fibration of groupoids we show how an exact 9-term sequence can be associated to a fibration of bigroupoids. Applications to topology and algebra are given.     

Analysis of two-sample truncated data using generalized logistic models

Parallel to Cox's [JRSS B34 (1972) 187-230] proportional hazards model, generalized logistic models have been discussed by Anderson [Bull. Int. Statist. Inst. 48 (1979) 35-53] and others. The essential assumption is that the two densities ratio has a known parametric form. A nice property of this model is that it naturally relates to the logistic regression model for categorical data. In astronomic, demographic, epidemiological, and other studies the variable of interest is often truncated by an associated variable. This paper studies generalized logistic models for the two-sample truncated data problem, where the two lifetime densities ratio is assumed to have the form exp{α+φ(x;β)}. Here φ is a known function of x and β, and the baseline density is unspecified. We develop a semiparametric maximum likelihood method for the case where the two samples have a common truncation distribution. It is shown that inferences for β do not depend the nonparametric components. We also derive an iterative algorithm to maximize the semiparametric likelihood for the general case where different truncation distributions are allowed. We further discuss how to check goodness of fit of the generalized logistic model. The developed methods are illustrated and evaluated using both simulated and real data.     

Unavoidable Traces Of Set Systems

Sauer, Shelah, Vapnik and Chervonenkis proved that if a set system on n vertices contains many sets, then the set system has full trace on a large set. Although the restriction on the size of the groundset cannot be lifted, Frankl and Pach found a trace structure that is guaranteed to occur in uniform set systems even if we do not bound the size of the groundset. In this note we shall give three sequences of structures such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.     

Higher Order Peak Algebras

Using the theory of noncommutative symmetric functions, we introduce the higher order peak algebras (Sym(N))_N≥1, a sequence of graded Hopf algebras which contain the descent algebra and the usual peak algebra as initial cases (N=1 and N=2). We compute their Hilbert series, introduce and study several combinatorial bases, and establish various algebraic identities related to the multisection of formal power series with noncommutative coefficients. Received November 19, 2004     

On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

Long Abelian ideals

We study Abelian ideals of a Borel subalgebra consisting of long roots. It is shown that methods of Cellini and Papi can be extended to this situation. A uniform expression for the number of long Abelian ideals is given. We also show that there is a one-to-one correspondence between the long Abelian ideals and B-stable commutative subalgebras in the little adjoint representation of the Langlands dual Lie algebra.     

Normalization of complex-valued planar vector fields which degenerate along a real curve

Taking as a start point the recent article of Meziani [7], we present several results concerning the normalization of a class of complex vector fields in the plane which degenerate along a real curve. We mainly deal with operators with finite regularity and analyze both the local situation as well as the case of normalization near a circle. Some related questions (e.g., on semi-global solvability and on the normalization of a class of generalized Mizohata operators) are also discussed.