Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComparative computational results for some vertex and facet enumeration codes
292
0
0.0
(
0
)
Added by
David Avis
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We report some computational results comparing parallel and sequential codes for vertex/facet enumeration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. We tested one code (lrs) based on pivoting and four codes (cddr+, ppl, normaliz, PORTA) based on the double description method. normaliz employs parallelization as do the codes plrs and mplrs which are based on lrs. We tested these codes using various hardware configurations with up to 1200 cores. Major speedups were obtained by parallelization, particularly by the code mplrs which uses MPI and can operate on clusters of machines.
rate research
Read More
We describe a new parallel implementation, mplrs, of the vertex enumeration code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C++. plrs uses the Boost library and runs on a shared memory machine. In developing mplrs we discovered a method of balancing the parallel tree search, called budgeting, that greatly improves parallelization beyond the bottleneck encountered previously at around 32 cores. This method can be readily adapted for use in other reverse search enumeration codes. We also report some preliminary computational results comparing parallel and sequential codes for vertex/facet enumeration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested.
The adoption of neural networks and deep learning in non-Euclidean domains has been hindered until recently by the lack of scalable and efficient learning frameworks. Existing toolboxes in this space were mainly motivated by research and education use cases, whereas practical aspects, such as deploying and maintaining machine learning models, were often overlooked. We attempt to bridge this gap by proposing TensorFlow RiemOpt, a Python library for optimization on Riemannian manifolds in TensorFlow. The library is designed with the aim for a seamless integration with the TensorFlow ecosystem, targeting not only research, but also streamlining production machine learning pipelines.
In this paper, we address computational questions surrounding the enumeration of non-isomorphic Andre planes for any prime power order. We are particularly focused on providing a complete enumeration of all such planes for relatively small orders (up to 125), as well as developing computationally efficient ways to count the number of isomorphism classes for other orders where enumeration is infeasible. Andre planes of all dimensions over their kernel are considered.
Computation of the vertices of the convex hull of a set $S$ of $n$ points in $mathbb{R} ^m$ is a fundamental problem in computational geometry, optimization, machine learning and more. We present All Vertex Triangle Algorithm (AVTA), a robust and efficient algorithm for computing the subset $overline S$ of all $K$ vertices of $conv(S)$, the convex hull of $S$. If $Gamma_*$ is the minimum of the distances from each vertex to the convex hull of the remaining vertices, given any $gamma leq gamma_* = Gamma_*/R$, $R$ the diameter of $S$, $AVTA$ computes $overline S$ in $O(nK(m+ gamma^{-2}))$ operations. If $gamma_*$ is unknown but $K$ is known, AVTA computes $overline S$ in $O(nK(m+ gamma_*^{-2})) log(gamma_*^{-1})$ operations. More generally, given $t in (0,1)$, AVTA computes a subset $overline S^t$ of $overline S$ in $O(n |overline S^t|(m+ t^{-2}))$ operations, where the distance between any $p in conv(S)$ to $conv(overline S^t)$ is at most $t R$. Next we consider AVTA where input is $S_varepsilon$, an $varepsilon$ perturbation of $S$. Assuming a bound on $varepsilon$ in terms of the minimum of the distances of vertices of $conv(S)$ to the convex hull of the remaining point of $S$, we derive analogous complexity bounds for computing $overline S_varepsilon$. We also analyze AVTA under random projections of $S$ or $S_varepsilon$. Finally, via AVTA we design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models AVTA leads to significantly better reconstruction of the topic-word matrix than state of the art approaches~cite{arora2013practical, bansal2014provable}. For non-negative matrix AVTA is competitive with existing methods~cite{arora2012computing}. Empirically AVTA is robust and can handle larger amounts of noise than existing methods.
Important computational physics problems are often large-scale in nature, and it is highly desirable to have robust and high performing computational frameworks that can quickly address these problems. However, it is no trivial task to determine whether a computational framework is performing efficiently or is scalable. The aim of this paper is to present various strategies for better understanding the performance of any parallel computational frameworks for solving PDEs. Important performance issues that negatively impact time-to-solution are discussed, and we propose a performance spectrum analysis that can enhance ones understanding of critical aforementioned performance issues. As proof of concept, we examine commonly used finite element simulation packages and software and apply the performance spectrum to quickly analyze the performance and scalability across various hardware platforms, software implementations, and numerical discretizations. It is shown that the proposed performance spectrum is a versatile performance model that is not only extendable to more complex PDEs such as hydrostatic ice sheet flow equations, but also useful for understanding hardware performance in a massively parallel computing environment. Potential applications and future extensions of this work are also discussed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
