A “build-down” scheme for linear programming

We propose a build-down scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis candidate set including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from. As these methods iterate, is eventually built-down to a set that contains only the optimal basic columns.     

Local rigidity for complex hyperbolic lattices and Hodge theory

We prove general local rigidity results for cocompact complex hyperbolic lattices using Hodge theory.     

Combinatorial partitions of finite posets and lattices —Ramsey lattices

It is proved that for every finite latticeL there exists a finite latticeL such that for every partition of the points ofL into two classes there exists a lattice embeddingf:LL such that the points off(L) are in one of the classes.This property is called point-Ramsey property of the class of all finite lattices. In fact a stronger theorem is proved which implies the following: for everyn there exists a finite latticeL such that the Hasse-diagram (=covering relation) has chromatic number >n. We discuss the validity of Ramseytype theorems in the classes of finite posets (where a full discussion is given) and finite distributive lattices. Finally we prove theorems which deal with partitions of lattices into an unbounded number of classes.Presented by G. Grätzer.     

A convergent and precise finite element scheme for Landau–Lifschitz–Gilbert equation

In this paper, we propose a new scheme for the numerical integration of the Landau–Lifschitz–Gilbert (LLG) equations in their full complexity, in particular including stray-field interactions. The scheme is consistent up to order 2 (in time), and unconditionally stable. It combines a linear inner iteration with a non-linear renormalization stage for which a rigorous proof of convergence of the numerical solution toward a weak solution is given, when both space and time stepsizes tend to \(0\) . A numerical implementation of the scheme shows its performance on physically relevant test cases. We point out that to the knowledge of the authors this is the first finite element scheme for the LLG equations which enjoys such theoretical and practical properties.     

Polynomial-Time Homology for Simplicial Eilenberg–MacLane Spaces

In an earlier paper of ?adek, Vok?ínek, Wagner, and the present authors, we investigated an algorithmic problem in computational algebraic topology, namely, the computation of all possible homotopy classes of maps between two topological spaces, under suitable restriction on the spaces. We aim at showing that, if the dimensions of the considered spaces are bounded by a constant, then the computations can be done in polynomial time. In this paper we make a significant technical step towards this goal: we show that the Eilenberg–MacLane space $K(\mathbb{Z},1)$ , represented as a simplicial group, can be equipped with polynomial-time homology (this is a polynomial-time version of effective homology considered in previous works of the third author and co-workers). To this end, we construct a suitable discrete vector field, in the sense of Forman’s discrete Morse theory, on $K(\mathbb{Z},1)$ . The construction is purely combinatorial and it can be understood as a certain procedure for reducing finite sequences of integers, without any reference to topology. The Eilenberg–MacLane spaces are the basic building blocks in a Postnikov system, which is a “layered” representation of a topological space suitable for homotopy-theoretic computations. Employing the result of this paper together with other results on polynomial-time homology, in another paper we obtain, for every fixed k, a polynomial-time algorithm for computing the kth homotopy group π _k (X) of a given simply connected space X, as well as the first k stages of a Postnikov system for X, and also a polynomial-time version of the algorithm of ?adek et al. mentioned above.     

A cell functional minimization scheme for domain decomposition method on non-orthogonal and non-matching meshes

We are interested in a robust and accurate domain decomposition algorithm with interface conditions of Robin type on non-matching multiblock grids using a cell functional minimization scheme, which has a good performance on non-orthogonal meshes. In order to treat the non-matching grids at the interface, we introduce the \(L^2\) projection operator to ensure weak continuity of the primary unknown and of the normal flux across the non-matching interface. Furthermore, we prove the wellposedness of local and global problems and obtain as well an error estimate of first order in a discrete \(H^{1}\) -norm only using the \(L^{2}\) projection operator on the non-matching interface, as done in the matching case. Numerical results are presented in confirmation of the theoretical results.     

A new look at the Jordan-Hölder theorem for semimodular lattices

We show that in a semimodular lattice L of finite length, from any prime interval we can reach any maximal chain C by an up- and a down-perspectivity. Therefore, C is a congruence-determining sublattice of L.     

A proof of Frankl’s union-closed sets conjecture for dismantlable lattices

For a lattice L, let Princ(L) denote the ordered set of principal congruences of L. In a pioneering paper, G. Grätzer characterized the ordered set Princ(L) of a finite lattice L; here we do the same for a countable lattice. He also showed that every bounded ordered set H is isomorphic to Princ(L) of a bounded lattice L. We prove a related statement: if an ordered set H with a least element is the union of a chain of principal ideals (equivalently, if 0 \({\in}\) H and H has a cofinal chain), then H is isomorphic to Princ(L) of some lattice L.     

A classification algorithm for integrable two-dimensional lattices via Lie—Rinehart algebras

Theoretical and Mathematical Physics - We study the problem of the integrable classification of nonlinear lattices depending on one discrete and two continuous variables. By integrability, we mean...     

Simplicial complexes and Macaulay’s inverse systems

Let Δ be a simplicial complex on V = {x ₁, . . . , x _n }, with Stanley–Reisner ideal ${I_{\Delta}\subseteq R=k[x_1,\ldots, x_n]}Let Δ be a simplicial complex on V = {x ₁, . . . , x _n }, with Stanley–Reisner ideal I_D í R=k[x₁,?, x_n]{I_{\Delta}\subseteq R=k[x_1,\ldots, x_n]} . The goal of this paper is to investigate the class of artinian algebras A=A(D,a₁,?,a_n) = R/(I_D,x₁^a₁,?,x_n^a_n){A=A(\Delta,a_1,\ldots,a_n)= R/(I_{\Delta},x_1^{a_1},\ldots,x_n^{a_n})} , where each a _i ≥ 2. By utilizing the technique of Macaulay’s inverse systems, we can explicitly describe the socle of A in terms of Δ. As a consequence, we determine the simplicial complexes, that we will call levelable, for which there exists a tuple (a ₁, . . . , a _n ) such that A(Δ, a ₁, . . . , a _n ) is a level algebra.     

The Jordan-H?lder theorem with uniqueness for groups and semimodular lattices

For subnormal subgroups ${A{\vartriangleleft}B}$ and ${C{\vartriangleleft}D}$ of a given group G, the factor B/A will be called subnormally down-and-up projective to D/C if there are subnormal subgroups ${X{\vartriangleleft}Y}$ such that ${AY = B, A \cap Y = X, CY = D}$ , and ${C \cap Y = X}$ . Clearly, ${B/A \cong D/C}$ in this case. As G. Gr?tzer and J. B. Nation have recently pointed out, the standard proof of the classical Jordan-H?lder theorem yields somewhat more than is widely known; namely, the factors of any two given composition series are the same up to subnormal down-and-up projectivity and a permutation. We prove the uniqueness of this permutation. The main result is the analogous statement for semimodular lattices. Most of the paper belongs to pure lattice theory; the group theoretical part is only a simple reference to a classical theorem of H. Wielandt.     

A parametric spline scheme for the nonlinear Schrödinger equation

We develop a numerical method based on parametric adaptive quintic spline functions for solving the nonlinear Schrödinger (NLS) equation. The truncation error is theoretically analyzed. Based on the von Neumann method and the linearization technique, stability analysis of the method is studied and the method is shown to be unconditionally stable. Two invariants of motion related to mass and momentum are calculated to determine the conservation properties of the problem. Finally, some numerical tests are presented to illustrate the method’s efficiency.     

A semi-discrete scheme for the stochastic nonlinear Schrödinger equation

Summary. We study the convergence of a semi-discretized version of a numerical scheme for a stochastic nonlinear Schrödinger equation. The nonlinear term is a power law and the noise is multiplicative with a Stratonovich product. Our scheme is implicit in the deterministic part of the equation as is usual for conservative equations. We also use an implicit discretization of the noise which is better suited to Stratonovich products. We consider a subcritical nonlinearity so that the energy can be used to obtain an a priori estimate. However, in the semi discrete case, no Ito formula is available and we have to use a discrete form of this tool. Also, in the course of the proof we need to introduce a cut-off of the diffusion coefficient, which allows to treat the nonlinearity. Then, we prove convergence by a compactness argument. Due to the presence of noise and to the implicit discretization of the noise, this is rather complicated and technical. We finally obtain convergence of the discrete solutions in various topologies. Mathematics Subject Classification (2000):35Q55, 60H15, 65M06, 65M12     

A new destructive bounding scheme for the bin packing problem

In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.     

A non-standard-Euler–Maruyama scheme

We construct a non-standard finite difference numerical scheme to approximate stochastic differential equations (SDEs) using the idea of weighed step introduced by R.E. Mickens. We prove the strong convergence of our scheme under locally Lipschitz conditions of a SDE and linear growth condition. We prove the preservation of domain invariance by our scheme under a minimal condition depending on a discretization parameter and unconditionally for the expectation of the approximate solution. The results are illustrated through the geometric Brownian motion. The new scheme shows a greater behaviour compared with the Euler–Maruyama scheme and balanced implicit methods which are widely used in the literature and applications.     

A linear,symmetric and energy-conservative scheme for the space-fractional Klein–Gordon–Schrödinger equations

In this paper, we propose an efficient numerical scheme for the space-fractional Klein–Gordon–Schrödinger (SFKGS) equations. Motivated by the “Invariant Energy Quadratization” (IEQ) approach, we introduce two auxiliary variables to transform the SFKGS system into a new equivalent system in which the time derivative is discretized by the Crank–Nicolson method, and the space discretization is based on the Fourier spectral method. Consequently, the numerical scheme shares two good features. The first feature is that the nonlinear terms are treated semi-explicitly and a linear symmetric system is solved at each time step. The second feature is the energy conservation at the discrete level. These two advantages are proved by the theoretical analysis and illustrated by a given numerical example.