1,721,177 research outputs found
Perimeter search in restricted memory
No full textAbstractIn this paper, we consider the problem of finding a minimum cost path in a graph. In particular, we consider the perimeter search technique and we investigate the possibility of using very large perimeters. We present an algorithm designed to use perimeters of arbitrary size. Our algorithm generates the perimeter incrementally and makes use of a technique called backward pruning for reducing the search effort. A qualitative analysis and experimental results show that our algorithm can effectively use perimeters of very large size
Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results
No full text
On the ordering of sparse linear systems
No full textAbstractIn this paper we consider the algorithms for transforming an n × n sparse matrix A into another matrix B such that Gaussian elimination applied to B takes time asymptotically less than n3. These algorithms take the sparse matrix A as input, and return a pair of permutation matrices P, Q such that B = PAQ has a small bandwidth, or some other desirable form. We study the average effectiveness of these algorithms by using random matrices with Θ(n) nonzero elements. We prove that with high probability these algorithms cannot produce a reduction of the asymptotic cost of the standard Gaussian elimination algorithm.We also study the effectiveness of these algorithms for ordering very sparse matrices. We show that there exist matrices with 3n nonzeros for which reordering rows and columns does not reduce the asymptotic cost of Gaussian elimination. We also prove that each matrix with at most two nonzeros in each row and in each column, can be transformed into a banded matrix with bandwidth five
Stability and Conservation Properties of Hermite-Based Approximations of the Vlasov-Poisson System
Full text linkSpectral approximation based on Hermite-Fourier expansion of the Vlasov-Poisson model for a collisionless plasma in the electrostatic limit is provided by adding high-order artificial collision operators of Lenard-Bernstein type. These differential operators are suitably designed in order to preserve the physically-meaningful invariants (number of particles, momentum, energy). In view of time-discretization, stability results in appropriate norms are presented. In this study, necessary conditions link the magnitude of the artificial collision term, the number of spectral modes of the discretization, as well as the time-step. The analysis, carried out in full for the Hermite discretization of a simple linear problem in one-dimension, is then partly extended to cover the complete nonlinear Vlasov-Poisson model
A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over Zm
No full text
EEF1A1 (eukaryotic translation elongation factor 1 alpha 1). Atlas Genet Cytogenet Oncol Haematol. May 2009 .
No full textAtlas of Genetics and Cytogenetics in Oncology and Haematolog
- …
