Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
HONEI: A collection of libraries for numerical computations targeting multiple processor architectures.
No full textWe present HONEI, an open-source collection of libraries offering a hardware oriented approach to numerical calculations. HONEI abstracts the hardware, and applications written on top of HONEI can be executed on a wide range of computer architectures such as CPUs, GPUs and the Cell processor. We demonstrate the flexibility and performance of our approach with two test applications, a Finite Element multigrid solver for the Poisson problem and a robust and fast simulation of shallow water waves. By linking against HONEI's libraries, we achieve a two-fold speedup over straight forward C++ code using HONEI's SSE backend, and additional 3--4 and 4--16 times faster execution on the Cell and a GPU. A second important aspect of our approach is that the full performance capabilities of the hardware under consideration can be exploited by adding optimised application-specific operations to the HONEI libraries. HONEI provides all necessary infrastructure for development and evaluation of such kernels, significantly simplifying their development
Classification of all associative mono-n-ary algebras with 2 elements
No full textWe consider algebras with a single n-ary operation and generalized associativity. We prove that (up to isomorphism) there are exactly 5 of these associative mono-n-ary algebras with 2 elements for even n (at least 2) and 6 for odd n (at least 3). These algebras are described explicitly. It is shown that a similar result is impossible for algebras with at least 4 elements. An application concerning the assignment of a control bit to a string is given. Note that the main result of this paper also easily follows from the paper of Zupnik [9], therefore this technical report has not been published
Eigenschaften kleinster dominierender Mengen und Dominanzzahlen von Damengraphen
No full textWe consider the problem of determining the size gamma (Q_n) of a minimum dominating set and the size i(Q_n) of an independent minimum dominating set of the queens graph Q_n . Every vertex v in V(Q_n) of the graph Q_n corresponds to a square of the (nxn) chessboard and two squares are adjacent if and only if they are in the same row, column, or diagonal. We show that every p-cover of Q_n , n>=19, occupies both long diagonals that go through two corner squares and thus this condition in an alternative characterization of p-covers is nonrestrictive. We introduce a generalization of p-covers, namely orthodox covers, and show their relevance by stating some corresponding minimum dominating sets. For n==6(mod 8),n>=96, we show that there is no non-orthodox cover D of Q_n of size #D=n/2. In conjunction with a necessary condition for the existence of an orthodox cover of size n/2, in many cases the lower bound is raised to n/2 + 1, proving new domination numbers. Specifying appropriate dominating sets we show: gamma (Q_n) = (n+1)/2 for n = 43, 55, 83, 99, 107, 133, 137, 141, 143, 145, 149, 153, 157, 161, 163, 165, 169, 173, 177, 181, 183, 185, 189, 193, 197, 213, 221, and i(Q_n) = (n+1)/2 for n = 117, 121, 129, 141, 145, 157, 161, 165, 177, 185, 189. We provide a computer proof of gamma (Q_n) = i(Q_n) = n/2 + 1 for n = 20, 22, 24, 26, 28, 32, 34, 36, 38, 40, 42, 44, 46, 102, 110, 118, i(Q_n) = (n+1)/2 + 1 for n = 19, 23, 27, 31, and gamma (Q_n) = n/2 + 1 for n = 26, 134, 142, 150, 158, 166, 174, 182, 190, 198, 214, and 222
A Note on the Complexity of Sliding Shortest Paths
No full textWe address a shortest path problem in a given uncapacited and undirected network N=(V,E) with positive edge costs. In addition we are given a single source-destination pair (s,t), a shortest path p{st} connecting s and t and a new edge e =(p,q). The task is to find a minimum number of edges Ec and the minimum weight increase for each edge e in Ec such that the shortest path p{st} between s and t traverses edge e. We show that the problem is NP-hard and give a heuristic scheme for the problem
Engineering the Fast-Multipole-Multilevel Method for multicore and SIMD architectures
Get PDFIn this thesis, we present a new variant of the Fast-Mulitpole-Multilevel Method, which is used to draw large graphs. Based on the original approach by Stefan Hachul, a new algo- rithm is presented, which is optimized primarily for practical speed. In order to achieve this, special processor instructions are used to accelerate computations with complex num- bers. In addition, parts of the algorithm are executed in parallel to benefit from the widely spread multicore architectures. Besides these two rather technical improvements, we de- scribe a new construction method for a spatial space decomposition data structure, called the quadtree. The algorithm exploits the binary representation of the coordinates and shifts most of the work to the sorting of the input. Furthermore, we introduce another problem from computational geometry, the well-separated pair decomposition, and success- fully apply it in order to simplify parts of the algorithm. The resulting algorithm is able to compete in speed and layout quality even with a recently published graphics processor accelerated implementation
Compact and Extended Formulations for Range Assignment Problems
No full textWe devise two new integer programming models for range assignment problems arising in wireless network design. Building on an arbitrary set of feasible network topologies, e.g., all spanning trees, we explicitly model the power consumption at a given node as a weighted maximum over edge variables. We show that the standard ILP model is an extended formulation of the new models. For all models, we derive complete polyhedral descriptions in the unconstrained case where all topologies are allowed. These results give rise to tight relaxations even in the constrained case. We can show experimentally that the compact formulations compare favorably to the standard approach
GEODUAL: Fun with Geometric Duality
No full textWe present GEODUAL, a software for creating and solving geometric instances of the Minimum Spanning Tree problem, the Perfect Matching problem, and the Traveling Salesman problem, along with visual proofs of optimality
Kreuzzahlrätsel: Sudokus waren gestern
No full textKreuzzahlrätsel sind eine spannende Abwandlung von Kreuzworträtseln, deren Lösung auch für den Computer eine harte Nuss darstellt. Wir haben uns im letzten Jahr mit diesen Rätseln im Rahmen des informatiCups [1] beschäftigt, einem Wettbewerb der GI für Studierende, der am 15. September erneut ausgeschrieben worden ist
On the Subgroup Distance Problem
No full textWe investigate the computational complexity of finding an element of a permutation group H subset S_n with a minimal distance to a given pi in S_n , for different metrics on S_n . We assume that H is given by a set of generators, such that the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [Pinch, 2006]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l_p distance, Lee's Distance, Kendall's tau, and Ulam's Distance. Moreover, we give an NP-hardness proof for the l_oo distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixed-parameter and maximization problems
Modelling and simulation of nitrogen regulation in Corynebacterium glutamicum
No full textModelling the dynamic behaviour of biochemical systems at a molecular level aims at understanding and predicting the interactions of macromolecules inside the cell. Models of small subsystems based on differential equations not only prepare the way for the long-term goal of understanding a whole cell, but are inherently valuable due to their ability to predict the behaviour of the subsystem for varying external conditions or parameters. Nitrogen supply is essential for prokaryotes, thus the nitrogen uptake is an interesting target for model building. The goal is to provide new information about interactions of the relevant proteins by performing various simulations. A model based on piecewise linear differential equations is formulated for the nitrogen uptake in {it Corynebacterium glutamicum}. We theoretically derive a model for biochemical networks and introduce a general method for the parameter estimation which is also applicable in the case of very short time series. This approach is applied to a special system concerning the nitrogen uptake using Western blot experiments. The equations are set up for the main components of this system, the optimization problem for parameter estimation is formulated and solved, and simulations for the evaluation of the model as well as for predictions are carried out. We show that model building based on differential equations can also in case of few measurements lead to a satisfactory model which provides valuable insights into the way its network components function. For example, we are able to make predictions about the maximal value of the time course as well as the steady-state level of the signal transduction protein GlnK in case of restricted activity of the proteases when considering the transition of nitrogen starvation to nitrogen excess or vice versa