Almost Primitive Elements of Free lie Algebras of Small Ranks

Let K be a field, X = {x1, . . . , xn}, and let L(X) be the free Lie algebra over K with the set X of free generators. A. G. Kurosh proved that subalgebras of free nonassociative algebras are free, A. I. Shirshov proved that subalgebras of free Lie algebras are free. A subset M of nonzero elements of the free Lie algebra L(X) is said to be primitive if there is a set Y of free generators of L(X), L(X) = L(Y ), such that M ? Y (in this case we have |Y | = |X| = n). Matrix criteria for a subset of elements of free Lie algebras to be primitive and algorithms to construct complements of primitive subsets of elements with respect to sets of free generators have been constructed. A nonzero element u of the free Lie algebra L(X) is said to be almost primitive if u is not a primitive element of the algebra L(X), but u is a primitive element of any proper subalgebra of L(X) that contains it. A series of almost primitive elements of free Lie algebras has been constructed. In this paper, for free Lie algebras of rank 2 criteria for homogeneous elements to be almost primitive are obtained and algorithms to recognize homogeneous almost primitive elements are constructed.     

Almost primitive elements of free nonassociative (anty)commutative algebras of small rank

Criteria for homogeneous elements to be almost primitive are obtained and algorithms to recognize homogeneous almost primitive elements are constructed for free nonassociative commutative and anticommutative algebras of rank 1 and 2.     

An Interior-Point Method for Approximate Positive Semidefinite Completions

Given a nonnegative, symmetric matrix of weights, H, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix, A, with respect to the weighting H. This extends the notion of exact matrix completion problems in that, H _ij =0 corresponds to the element A _ij being unspecified (free), while H _ij large in absolute value corresponds to the element A _ij being approximately specified (fixed).We present optimality conditions, duality theory, and two primal-dual interior-point algorithms. Because of sparsity considerations, the dual-step-first algorithm is more efficient for a large number of free elements, while the primal-step-first algorithm is more efficient for a large number of fixed elements.Included are numerical tests that illustrate the efficiency and robustness of the algorithms     

Relations among Lie-series transformations and isomorphisms between free Lie algebras

We study the subgroup generated by the exponentials of formal Lie series. We show three different ways to represent elements of this subgroup. These elements induce Lie-series transformations. Relations among these family of transformations furnish algorithms of composition. Starting from the Lazard elimination theorem and the Witt's formula, we show isomorphisms between some submodules of free Lie algebras. Combining different results, we also show that the homogeneous terms of the Hausdorff series H(a,b) freely generate the free Lie algebra L(a,b) without a line.     

New algorithms for selection

New algorithms are presented to select the k largest elements, and give their respective order, of a totally ordered set of n elements, when k is small compared to n. The performance of these algorithms improves over that of previously known algorithms. One of these algorithms is optimal for a wide range of values of n and k. The algorithms can be modified to select the k th largest element only. The performance of the modified algorithms improves, for asymptotic values of n, over that of previously known algorithms for selecting the k th largest element.     

Primitive Elements and Automorphisms of Free Algebras of Schreier Varieties

In this article, we review results on primitive elements of free algebras of main types of Schreier varieties of algebras. A variety of linear algebras over a field is Schreier if any subalgebra of a free algebra of this variety is free in the same variety of algebras. A system of elements of a free algebra is primitive if it is a subset of some set of free generators of this algebra. We consider free nonassociative algebras, free commutative and anti-commutative nonassociative algebras, free Lie algebras and superalgebras, and free Lie p-algebras and p-superalgebras. We present matrix criteria for systems of elements of elements. Primitive elements distinguish automorphisms: endomorphisms sending primitive elements to primitive elements are automorphisms. We give a series of examples of almost primitive elements (an element of a free algebra is almost primitive if it is not a primitive element of the whole algebra, but it is a primitive element of any proper subalgebra which contains it). We also consider generic elements and Δ-primitive elements. Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 74, Algebra-15, 2000.     

A new look at the Padé table and the different methods for computing its elements

In this paper a survey is given of several algorithms for the computation of the Padé table of a formal power series. Those algorithms are studied which are based on certain relationships between adjacent elements in the Padé table. A new proof for the algorithms of Baker, Longman and for Gragg's variant of the qd-algorithm is given. A variant of Watson's algorithm is derived. The techniques used in this survey give some new ideas concerning the structure of the Padé table and the different ways to compute the elements of the table.     

Joint Distributions for Movements of Elements in Sattolo's and the Fisher-Yates Algorithm

Sattolo's algorithm creates a random cyclic permutation by interchanging pairs of elements in an appropriate manner; the Fisher-Yates algorithm produces random (not necessarily cyclic) permutations in a very similar way. The distributions of the movements of the elements in these two algorithms have already been treated quite extensively in past works. In this paper, we are interested in the joint distribution of two elements j and k; we are able to compute the bivariate generating functions explicitly, although it is quite involved. From it, moments and limiting distributions can be deduced. Furthermore, we compute the probability that elements i and j ever change places in both algorithms.     

Amalgamated products of groups: measures of random normal forms

Let $ G = A\mathop { * }\limits_C B $ be an amalgamated product of finite rank free groups A, B, and C. We introduce atomic measures and corresponding asymptotic densities on a set of normal forms of elements in G. We also define two strata of normal forms: the first one consists of regular (or stable) normal forms, and the second stratum is formed by singular (or unstable) normal forms. In a series of previous works about classical algorithmic problems, it was shown that standard algorithms work fast on elements of the first stratum and nothing is known about their work on the second stratum. In this paper, we give probabilistic and asymptotic estimates of these strata.     

Design and analysis of predictive sorting algorithms

The focus of this research is the class of sequential algorithms, called predictive sorting algorithms, for sorting a given set ofn elements using pairwise comparisons. The order in which these pairwise comparisons are made is defined by a fixed sequence of all unordered pairs of distinct integers {1, 2, ...,n} called a sort sequence. A predictive sorting algorithm associated with a sort sequence specifies pairwise comparisons of elements in the input set in the order defined by the sort sequence, except that the comparisons whose outcomes can be inferred from the preceding pairs of comparisons are not performed. In this paper predictive sorting algorithms are obtained, based on known sorting algorithms, and are shown to be required on the averageO(n logn) comparisons.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

Super greedy type algorithms

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy algorithms. We call such greedy algorithms super greedy type algorithms. The super greedy type algorithms are computationally simpler than their analogues from the standard greedy algorithms. In this article, we propose the Weak Super Greedy Algorithm (WSGA) and the Weak Orthogonal Super Greedy Algorithm with Thresholding (WOSGAT). Their performance (rate of convergence) are studied as well under M-coherent dictionaries.     

Operator splitting for the numerical solution of free surface flow at low capillary numbers

Free surface flows are pervasive in engineering and biomedical applications. In many interesting cases—particularly when small length scales are involved—surface forces (capillarity) dominate the flow dynamics. In these cases, computing the flow together with the shape of the surfaces, requires specialized solution techniques. This article investigates the capabilities of an operator splitting/finite elements method at handling accurately incompressible viscous flow with free surfaces at low capillary numbers. The test case of flow in the downstream section of a slot coater is used for three reasons: (1) it is an established benchmark; (2) it represents an idealized, yet industrially relevant flow; (3) high-fidelity results obtained with monolithic algorithms are available in literature. The flow and free surface shape attained with the new operator splitting scheme agree very satisfactorily with the results obtained with monolithic solvers. Because of its inherent computational simplicity, the new operator splitting scheme is attractive for large-scale simulations, three-dimensional flows, and flows of complex fluids.     

Practical arbitrage‐free scenario tree reduction methods and their applications in financial optimization

We construct an arbitrage‐free scenario tree reduction model, from which some arbitrage‐free scenario tree reduction algorithms are designed. They ensure that the reduced scenario trees are arbitrage free. Numerical results show the practicality and efficiency of the proposed algorithms. Results for multistage portfolio selection problems demonstrate the necessity and importance for guaranteeing that the reduced scenario trees are arbitrage free, as well as the practicality of the proposed arbitrage‐free scenario tree reduction algorithms for financial optimization.     

New algorithms for discrete vector optimization based on the Graef-Younes method and cone-monotone sorting functions

Abstract

The well-known Jahn-Graef-Younes algorithm, proposed by Jahn in 2006, generates all minimal elements of a finite set with respect to an ordering cone. It consists of two Graef-Younes procedures, namely the forward iteration, which eliminates a part of the non-minimal elements, followed by the backward iteration, which is applied to the reduced set generated by the previous iteration. Without using the backward iteration, we develop new algorithms that also compute all minimal elements of the initial set, by combining the forward iteration with certain sorting procedures based on cone-monotone functions. In particular, when the ordering cone is polyhedral, computational results obtained in MATLAB allow us to compare our algorithms with the Jahn-Graef-Younes algorithm, within a bi-objective optimization problem.     

Vector greedy algorithms

Our objective is to study nonlinear approximation with regard to redundant systems. Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practical problems. Greedy-type approximations proved to be convenient and efficient ways of constructing m-term approximants. We introduce and study vector greedy algorithms that are designed with aim of constructing mth greedy approximants simultaneously for a given finite number of elements. We prove convergence theorems and obtain some estimates for the rate of convergence of vector greedy algorithms when elements come from certain classes.     

Spectral discretizations of 3-D elliptic problems and fast domain decomposition methods

An important for applications, the class of hp discretizations of second-order elliptic equations consists of discretizations based on spectral finite elements. The development of fast domain decomposition algorithms for them was restrained by the absence of fast solvers for the basic components of the method, i.e., for local interior problems on decomposition subdomains and their faces. Recently, the authors have established that such solvers can be designed using special factorized preconditioners. In turn, factorized preconditioners are constructed using an important analogy between the stiffness matrices of spectral and hierarchical basis hp-elements (coordinate functions of the latter are defined as tensor products of integrated Legendre polynomials). Due to this analogy, for matrices of spectral elements, fast solvers can be developed that are similar to those for matrices of hierarchical elements. Based on these facts and previous results on the preconditioning of other components, fast domain decomposition algorithms for spectral discretizations are obtained.     

The free Malcev superalgebra on one odd generator and related superalgebras

A base of the universal multiplicative envelope of the free Malcev superalgebra ℳ on one odd generator is constructed. Some corollaries for skew-symmetric functions and central elements in free Malcev and free alternative algebras are obtained. Moreover, a base of the Poisson-Malcev superalgebra of ℳ is constructed. As a corollary, a set of elements that spans the free alternative superalgebra on one odd generator is obtained. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 4, pp. 97–106, 2004.     

Persistency in combinatorial optimization problems on matroids

Optimization problems on matroids are generalizations of such important combinatorial optimization problems like the problem of minimum spanning tree of a graph, the bipartite matching problem, flow problems, etc. We analyze algorithms for finding the maximum weight independent set of a matroid and for finding a maximum cardinality intersection of two matroids and extend them to obtain the so-called “persistency” partition of the basic set of the matroid, where contain elements belonging to all optimum solutions; contain elements not belonging to any optimum solution; contain elements that belong to some but not to all optimum solutions.     

Strong convergence theorems of common elements for equilibrium problems and fixed point problems in banach spaces

In this paper,we consider hybrid algorithms for finding common elements of the set of common fixed points of two families quasi-φ-non-expansive mappings and the set of solutions of an equilibrium problem.We establish strong convergence theorems of common elements in uniformly smooth and strictly convex Banach spaces with the property (K).