Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFixed point forms of the parallel symmetric sandpile model
114
0
0.0
(
0
)
Added by
Tran Thi Thu Huong
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper presents a generalization of the sandpile model, called the parallel symmetric sandpile model, which inherits the rules of the symmetric sandpile model and implements them in parallel. In this new model, at each step the collapsing of the collapsible columns happens at the same time and one collapsible column is able to collapse on the left or on the right but not both. We prove that the set of forms of fixed points of the symmetric sandpile model is the same as the one of that model using parallel update scheme by constructing explicitly the way (in the parallel update scheme) to reach the form of an arbitrary fixed point of the sequential model.
rate research
Read More
We study maps on the set of permutations of n generated by the Renyi-Foata map intertwined with other dihedral symmetries (of a permutation considered as a 0-1 matrix). Iterating these maps leads to dynamical systems that in some cases exhibit interesting orbit structures, e.g., every orbit size being a power of two, and homomesic statistics (ones which have the same average over each orbit). In particular, the number of fixed points (aka 1-cycles) of a permutation appears to be homomesic with respect to three of these maps, even in one case where the orbit structures are far from nice. For the most interesting such Foatic action, we give a heap analysis and recursive structure that allows us to prove the fixed-point homomesy and orbit properties, but two other cases remain conjectural.
The split common fixed point problems has found its applications in various branches of mathematics both pure and applied. It provides us a unified structure to study a large number of nonlinear mappings. Our interest here is to apply these mappings and propose some iterative methods for solving the split common fixed point problems and its variant forms, and we prove the convergence results of these algorithms. As a special case of the split common fixed problems, we consider the split common fixed point equality problems for the class of finite family of quasi-nonexpansive mappings. Furthermore, we consider another problem namely split feasibility and fixed point equality problems and suggest some new iterative methods and prove their convergence results for the class of quasi-nonexpansive mappings. Finally, as a special case of the split feasibility and fixed point equality problems, we consider the split feasibility and fixed point problems and propose Ishikawa-type extra-gradients algorithms for solving these split feasibility and fixed point problems for the class of quasi-nonexpansive mappings in Hilbert spaces. In the end, we prove the convergence results of the proposed algorithms. Results proved in this chapter continue to hold for different type of problems, such as; convex feasibility problem, split feasibility problem and multiple-set split feasibility problems.
We propose a new self-organizing algorithm for fixed-charge network flow problems based on ghost image (GI) processes as proposed in Glover (1994) and adapted to fixed-charge transportation problems in Glover, Amini and Kochenberger (2005). Our self-organizing GI algorithm iteratively modifies an idealized representation of the problem embodied in a parametric ghost image, enabling all steps to be performed with a primal network flow algorithm operating on the parametric GI. Computational tests are carried out on an extensive set of benchmark problems which includes the previous largest set in the literature, comparing our algorithm to the best methods previously proposed for fixed-charge transportation problems, though our algorithm is not specialized to this class. We also provide comparisons for additional more general fixed-charge network flow problems against Cplex 12.8 to demonstrate that the new self-organizing GI algorithm is effective on large problem instances, finding solutions with statistically equivalent objective values at least 700 times faster. The attractive outcomes produced by the current GI/TS implementation provide a significant advance in our ability to solve fixed-cost network problems efficiently and invites its use for larger instances from a variety of application domains.
We propose efficient parallel algorithms and implementations on shared memory architectures of LU factorization over a finite field. Compared to the corresponding numerical routines, we have identified three main difficulties specific to linear algebra over finite fields. First, the arithmetic complexity could be dominated by modular reductions. Therefore, it is mandatory to delay as much as possible these reductions while mixing fine-grain parallelizations of tiled iterative and recursive algorithms. Second, fast linear algebra variants, e.g., using Strassen-Winograd algorithm, never suffer from instability and can thus be widely used in cascade with the classical algorithms. There, trade-offs are to be made between size of blocks well suited to those fast variants or to load and communication balancing. Third, many applications over finite fields require the rank profile of the matrix (quite often rank deficient) rather than the solution to a linear system. It is thus important to design parallel algorithms that preserve and compute this rank profile. Moreover, as the rank profile is only discovered during the algorithm, block size has then to be dynamic. We propose and compare several block decomposition: tile iterative with left-looking, right-looking and Crout variants, slab and tile recursive. Experiments demonstrate that the tile recursive variant performs better and matches the performance of reference numerical software when no rank deficiency occur. Furthermore, even in the most heterogeneous case, namely when all pivot blocks are rank deficient, we show that it is possbile to maintain a high efficiency.
The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$, one of the most basic non-product domains, and establish hypercontractive inequalities on it. Our inequalities are most effective for the class of emph{global functions} on $S_n$, which are functions whose $2$-norm remains small when restricting $O(1)$ coordinates of the input, and assert that low-degree, global functions have small $q$-norms, for $q>2$. As applications, we show: 1. An analog of the level-$d$ inequality on the hypercube, asserting that the mass of a global function on low-degrees is very small. We also show how to use this inequality to bound the size of global, product-free sets in the alternating group $A_n$. 2. Isoperimetric inequalities on the transposition Cayley graph of $S_n$ for global functions, that are analogous to the KKL theorem and to the small-set expansion property in the Boolean hypercube. 3. Hypercontractive inequalities on the multi-slice, and stabili
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
