An acceleration method for Ten Berge et al.’s algorithm for orthogonal INDSCAL

INDSCAL (INdividual Differences SCALing) is a useful technique for investigating both common and unique aspects of K similarity data matrices. The model postulates a common stimulus configuration in a low-dimensional Euclidean space, while representing differences among the K data matrices by differential weighting of dimensions by different data sources. Since Carroll and Chang proposed their algorithm for INDSCAL, several issues have been raised: non-symmetric solutions, negative saliency weights, and the degeneracy problem. Orthogonal INDSCAL (O-INDSCAL) which imposes orthogonality constraints on the matrix of stimulus configuration has been proposed to overcome some of these difficulties. Two algorithms have been proposed for O-INDSCAL, one by Ten Berge, Knol, and Kiers, and the other by Trendafilov. In this paper, an acceleration technique called minimal polynomial extrapolation is incorporated in Ten Berge et al.’s algorithm. Simulation studies are conducted to compare the performance of the three algorithms (Ten Berge et al.’s original algorithm, the accelerated algorithm, and Trendafilov’s). Possible extensions of the accelerated algorithm to similar situations are also suggested.     

An approximation algorithm for quadratic dynamic systems based on N. Chomsky’s grammar for Taylor’s formula

Single-step methods for the approximate solution of the Cauchy problem for dynamic systems are discussed. It is shown that a numerical integration algorithm with a high degree of accuracy based on Taylor’s formula can be proposed in the case of quadratic systems. An explicit estimate is given for the remainder. The algorithm is based on N. Chomsky’s generative grammar for the language of terms of Taylor’s formula.     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.     

An exponential lower bound for Cunningham’s rule

In this paper we give an exponential lower bound for Cunningham’s least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.     

An axiom system for Lingenberg’s metric-Euclidean planes

We show that Lingenbergs metric-Euclidean planes are the rectangular planes of Karzel and Stanik which satisfy the axiom If two of the perpendicular bisectors of a triangle exist, then so does the third.This paper was written while the author was at the Institute of Mathematics of University of Biaystok with a Fulbright grant. I thank the Polish-U.S. Fulbright Commission for the grant, Professor Krzysztof Pramowski for the hospitality, and Ewa Walecka for drawing the figures.     

An extension of Babbage’s criterion for primality

Let n > 1 and k > 1 be positive integers. We show that if $$\left( {\begin{array}{*{20}c} {n + m} \\ n \\ \end{array} } \right) \equiv 1 (\bmod k)$$ for each integer m with 0 ≤ m ≤ n ? 1, then k is a prime and n is a power of this prime. In particular, this assertion under the hypothesis that n = k implies that n is a prime. This was proved by Babbage, and thus our result may be considered as a generalization of this criterion for primality.     

Euler’s elastica-based algorithm for Parallel MRI reconstruction using SENSitivity Encoding

Optimization Letters - SENSitivity Encoding (SENSE) is an effective mathematical formulation for reconstructing under-sampled MRI data obtained in Parallel Magnetic Resonance Imaging (Parallel...     

Fine tuning Nesterov’s steepest descent algorithm for differentiable convex programming

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.     

One modification of Gomory’s algorithm

The problem of constructing optimum cuts in the Gomory method for integer linear programming (ILP) problems is considered. Algorithms for finding cuts are described, and their complexity is assessed. The modified Gomory algorithm is compared to a standard Gomory algorithm.     

A new FDTD scheme for Maxwell’s equations in Kerr-type nonlinear media

Numerical Algorithms - In this paper, we develop a totally new direct finite difference solver for solving the Maxwell’s equations in Kerr-type nonlinear media. The direct method is free of...     

An ABC inequality for Mahler’s measure

We prove an upper bound for the Mahler measure of the Wronskian of a collection of N linearly independent polynomials with complex coefficients. If the coefficients of the polynomials are algebraic numbers we obtain an inequality for the absolute Weil heights of the roots of the polynomials. This later inequality is analogous to the abc inequality for polynomials, and also has applications to Diophantine problems.     

An Analogue of Beurling’s Theorem for NA Groups

In this paper, we prove Beurling’s theorem for NA groups, from which we derive some other versions of uncertainty principles.     

An Analogue of Nakayama’s Conjecture for Johnson Schemes

Nakayamas Conjecture is one of the most famous theorems for representation theory of symmetric groups. Two general irreducible characters of a symmetric group belong to the same p-block if and only if the p-cores of the young diagrams corresponding to them are the same. The conjecture was first proven in 1947 by Brauer and Robinson. We consider an analogue of Nakayamas Conjecture for Johnson schemes.Received January 28, 2004     

An exponential lower bound for Zadeh’s pivot rule

Mathematical Programming - The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural,...     

An extension of Fujita’s non-extendability theorem for Grassmannians

In this paper we study smooth complex projective varieties X containing a Grassmannian of lines ${{\mathbb G}(1, r)}$ which appears as the zero locus of a section of a rank two nef vector bundle E. Among other things we prove that the bundle E cannot be ample.     

An Analogue of Bochner’s Theorem for Damek-Ricci Spaces

We characterize the image of radial positive measures θ’s on a harmonic NA group S which satisfies ∫ _S ? ₀(x)?dθ(x)<∞ under the spherical transform, where ? ₀ is the elementary spherical function.