TY - GEN A1 - Golas, Ulrike T1 - A General Attribution Concept for Models in M- adhesive Transformation Systems: Long Version N2 - Attributes are an important concept for modeling data in practical applications. Up to now there is no adequate way to define attributes for different kinds of models used in M-adhesive transformation systems, which are a special kind of graph transformation systems based on M-adhesive categories. Especially a proper representation and definition of attributes and their values as well as a suitable handling of the data does not fit well with other graph transformation formalisms. In this paper, we propose a new method to define attributes in a natural, but still formally precise and widely applicable way. We define a new kind of adhesive category, called W-adhesive, that can be used for transformations of attributes, while the underlying models are still M-adhesive ones. As a result, attributed models can be used as they are intended to be, but with a formal background and proven well-behavior. T3 - ZIB-Report - 12-22 KW - graph transformation KW - attribution KW - adhesive categories Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15547 SN - 1438-0064 ER - TY - GEN A1 - Wende, Florian A1 - Steinke, Thomas T1 - Swendsen-Wang Multi-Cluster Algorithm for the 2D/3D Ising Model on Xeon Phi and GPU N2 - Simulations of the critical Ising model by means of local update algorithms suffer from critical slowing down. One way to partially compensate for the influence of this phenomenon on the runtime of simulations is using increasingly faster and parallel computer hardware. Another approach is using algorithms that do not suffer from critical slowing down, such as cluster algorithms. This paper reports on the Swendsen-Wang multi-cluster algorithm on Intel Xeon Phi coprocessor 5110P, Nvidia Tesla M2090 GPU, and x86 multi-core CPU. We present shared memory versions of the said algorithm for the simulation of the two- and three-dimensional Ising model. We use a combination of local cluster search and global label reduction by means of atomic hardware primitives. Further, we describe an MPI version of the algorithm on Xeon Phi and CPU, respectively. Significant performance improvements over known im plementations of the Swendsen-Wang algorithm are demonstrated. T3 - ZIB-Report - 13-44 KW - Swendsen-Wang Multi-Cluster Algorithm KW - Ising Model KW - Xeon Phi KW - GPGPU KW - Connected Component Labeling Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42187 SN - 1438-0064 ER - TY - GEN A1 - Pyszkalski, Wolfgang T1 - Übersicht über die Datenhaltung im ZIB und die Möglichkeiten einer Nutzung durch Projekte N2 - Dieser Bericht beschreibt in allgemein verständlicher Form die Struktur der Datenhaltung im Zuse‐Institut Berlin (ZIB) und die aktuell verwendeten Strategien im Umgang mit immer stärker wachsenden Datenmengen, sowie der Herausforderung der Speicherung unwiederbringlicher Daten über im Grunde unbegrenzte Zeit. T3 - ZIB-Report - 13-16 KW - Langfristige Datenhaltung KW - Speichersysteme KW - Magnetband KW - Vertrauenswürdigkeit des Langzeitspeichers KW - Sicherstellung der Lesbarkeit des Bandmaterials Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42060 SN - 1438-0064 ER - TY - GEN A1 - Nägel, Arne A1 - Deuflhard, Peter A1 - Wittum, Gabriel T1 - Efficient Stiff Integration of Density Driven Flow Problems N2 - The paper investigates the efficient use of a linearly implicit stiff integrator for the numerical solution of density driven flow problems. Upon choosing a one-step method of extrapolation type (code LIMEX), the use of full Jacobians and reduced approximations are discussed. Numerical experiments include nonlinear density flow problems such as diffusion from a salt dome (2D), a (modified) Elder problem (3D), the saltpool benchmark (3D) and a real life salt dome problem (2D). The arising linear equations are solved using either a multigrid preconditioner from the software package UG4 or the sparse matrix solver SuperLU. T3 - ZIB-Report - 18-54 KW - stiff integration for PDEs KW - linearly implicit Euler discretization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70891 SN - 1438-0064 ER - TY - GEN A1 - Baum, Daniel A1 - Lindow, Norbert A1 - Hege, Hans-Christian A1 - Lepper, Verena A1 - Siopi, Tzulia A1 - Kutz, Frank A1 - Mahlow, Kristin A1 - Mahnke, Heinz-Eberhard T1 - Revealing hidden text in rolled and folded papyri N2 - Ancient Egyptian papyri are often folded, rolled up or kept as small packages, sometimes even sealed. Physically unrolling or unfolding these packages might severely damage them. We demonstrate a way to get access to the hidden script without physical unfolding by employing computed tomography and mathematical algorithms for virtual unrolling and unfolding. Our algorithmic approaches are combined with manual interaction. This provides the necessary flexibility to enable the unfolding of even complicated and partly damaged papyrus packages. In addition, it allows us to cope with challenges posed by the structure of ancient papyrus, which is rather irregular, compared to other writing substrates like metallic foils or parchment. Unfolding of packages is done in two stages. In the first stage, we virtually invert the physical folding process step by step until the partially unfolded package is topologically equivalent to a scroll or a papyrus sheet folded only along one fold line. To minimize distortions at this stage, we apply the method of moving least squares. In the second stage, the papyrus is simply flattened, which requires the definition of a medial surface. We have applied our software framework to several papyri. In this work, we present the results of applying our approaches to mockup papyri that were either rolled or folded along perpendicular fold lines. In the case of the folded papyrus, our approach represents the first attempt to address the unfolding of such complicated folds. T3 - ZIB-Report - 17-02 KW - unfolding, papyri, computed tomography Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61826 SN - 1438-0064 ER - TY - GEN A1 - Schiela, Anton T1 - A cubic regularization algorithm for nonconvex optimization in function space (in preparation) N2 - We propose a cubic regularization algorithm that is constructed to deal with nonconvex minimization problems in function space. It allows for a flexible choice of the regularization term and thus accounts for the fact that in such problems one often has to deal with more than one norm. Global and local convergence results are established in a general framework. Moreover, several variants of step computations are compared. In the context of nonlinear elasticity it turns out the a cg method applied to an augmented Hessian is more robust than truncated cg. T3 - ZIB-Report - 12-16 KW - nonconvex optimization KW - optimization in function space KW - nonlinear elasticity Y1 - 2012 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Sullivan, T. J. T1 - Cameron--Martin theorems for sequences of Cauchy-distributed random variables N2 - Given a sequence of Cauchy-distributed random variables defined by a sequence of location parameters and a sequence of scale parameters, we consider another sequence of random variables that is obtained by perturbing the location or scale parameter sequences. Using a result of Kakutani on equivalence of infinite product measures, we provide sufficient conditions for the equivalence of laws of the two sequences. T3 - ZIB-Report - 16-40 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60230 SN - 1438-0064 ER - TY - GEN A1 - Sullivan, T. J. T1 - Well-posed Bayesian inverse problems and heavy-tailed stable Banach space priors N2 - This article extends the framework of Bayesian inverse problems in infinite-dimensional parameter spaces, as advocated by Stuart (Acta Numer. 19:451–559, 2010) and others, to the case of a heavy-tailed prior measure in the family of stable distributions, such as an infinite-dimensional Cauchy distribution, for which polynomial moments are infinite or undefined. It is shown that analogues of the Karhunen–Loève expansion for square-integrable random variables can be used to sample such measures. Furthermore, under weaker regularity assumptions than those used to date, the Bayesian posterior measure is shown to depend Lipschitz continuously in the Hellinger metric upon perturbations of the misfit function and observed data. T3 - ZIB-Report - 16-30 KW - Bayesian inverse problems KW - heavy-tailed distribution KW - Karhunen–Loève expansion KW - stable distribution KW - uncertainty quantification KW - well-posedness Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59422 SN - 1438-0064 ER - TY - GEN A1 - Costa, Marta A1 - Manton, James D. A1 - Ostrovsky, Aaron D. A1 - Prohaska, Steffen A1 - Jefferis, Gregory S.X.E. T1 - NBLAST: Rapid, sensitive comparison of neuronal structure and construction of neuron family databases N2 - Neural circuit mapping is generating datasets of 10,000s of labeled neurons. New computational tools are needed to search and organize these data. We present NBLAST, a sensitive and rapid algorithm, for measuring pairwise neuronal similarity. NBLAST considers both position and local geometry, decomposing neurons into short segments; matched segments are scored using a probabilistic scoring matrix defined by statistics of matches and non-matches. We validated NBLAST on a published dataset of 16,129 single Drosophila neurons. NBLAST can distinguish neuronal types down to the finest level (single identified neurons) without a priori information. Cluster analysis of extensively studied neuronal classes identified new types and unreported topographical features. Fully automated clustering organized the validation dataset into 1052 clusters, many of which map onto previously described neuronal types. NBLAST supports additional query types including searching neurons against transgene expression patterns. Finally we show that NBLAST is effective with data from other invertebrates and zebrafish. T3 - ZIB-Report - 16-34 KW - neuroinformatics KW - NBLAST KW - neuron similarity KW - cell type KW - clustering Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59672 SN - 1438-0064 ER - TY - GEN A1 - Zhang, Wei A1 - Hartmann, Carsten A1 - Schütte, Christof T1 - Effective Dynamics Along Given Reaction Coordinates, and Reaction Rate Theory N2 - In molecular dynamics and related fields one considers dynamical descriptions of complex systems in full (atomic) detail. In order to reduce the overwhelming complexity of realistic systems (high dimension, large timescale spread, limited computational resources) the projection of the full dynamics onto some reaction coordinates is examined in order to extract statistical information like free energies or reaction rates. In this context, the effective dynamics that is induced by the full dynamics on the reaction coordinate space has attracted considerable attention in the literature. In this article, we contribute to this discussion: We first show that if we start with an ergodic diffusion processes whose invariant measure is unique then these properties are inherited by the effective dynamics. Then, we give equations for the effective dynamics, discuss whether the dominant timescales and reaction rates inferred from the effective dynamics are accurate approximations of such quantities for the full dynamics, and compare our findings to results from approaches like Zwanzig-Mori, averaging, or homogenization. Finally, by discussing the algorithmic realization of the effective dynamics, we demonstrate that recent algorithmic techniques like the ”equation-free” approach and the ”heterogeneous multiscale method” can be seen as special cases of our approach. T3 - ZIB-Report - 16-35 KW - Ergodic diffusion KW - reaction coordinate KW - effective dynamics KW - model reduction KW - equation-free KW - heterogeneous multiscale method Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59706 SN - 1438-0064 ER - TY - GEN A1 - Cockayne, Jon A1 - Oates, Chris A1 - Sullivan, T. J. A1 - Girolami, Mark T1 - Probabilistic Meshless Methods for Partial Differential Equations and Bayesian Inverse Problems N2 - This paper develops a class of meshless methods that are well-suited to statistical inverse problems involving partial differential equations (PDEs). The methods discussed in this paper view the forcing term in the PDE as a random field that induces a probability distribution over the residual error of a symmetric collocation method. This construction enables the solution of challenging inverse problems while accounting, in a rigorous way, for the impact of the discretisation of the forward problem. In particular, this confers robustness to failure of meshless methods, with statistical inferences driven to be more conservative in the presence of significant solver error. In addition, (i) a principled learning-theoretic approach to minimise the impact of solver error is developed, and (ii) the challenging setting of inverse problems with a non-linear forward model is considered. The method is applied to parameter inference problems in which non-negligible solver error must be accounted for in order to draw valid statistical conclusions. T3 - ZIB-Report - 16-31 KW - Probabilistic Numerics KW - Partial Differential Equations KW - Inverse Problems KW - Meshless Methods KW - Gaussian Processes KW - Pseudo-Marginal MCMC Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59513 SN - 1438-0064 ER - TY - GEN A1 - Deuflhard, Peter T1 - The Grand Four N2 - This paper gives a concise synopsis and some new insights concerning four affine invariant globalizations of the local Newton method. The invariance classes include: affine covariance, affine contravariance, affine conjugacy, and affine similarity. In view of algorithmic robustness, each of these classes of algorithms is particularly suitable for some corresponding problem class. T3 - ZIB-Report - 17-70 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66038 SN - 1438-0064 ER - TY - GEN A1 - Christgau, Steffen A1 - Schnor, Bettina T1 - MPI Passive Target Synchronization on a Non-Cache-Coherent Shared-Memory Processor N2 - MPI passive target synchronization offers exclusive and shared locks. These are the building blocks for the implementation of applications with Readers & Writers semantic, like for example distributed hash tables. This paper discusses the implementation of MPI passive target synchronization on a non-cache-coherent multicore, the Intel Single-Chip Cloud Computer. The considered algorithms differ in their communication style (message based versus shared memory), their data structures (centralized versus distributed) and their semantics (with/without Writer preference). It is shown that shared memory approaches scale very well and deliver good performance, even in absence of cache coherence. T3 - ZIB-Report - 19-52 KW - process synchronization KW - programming models and systems for manycores KW - MPI Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74774 SN - 1438-0064 ER - TY - GEN A1 - Ege, Yannic A1 - Foth, Christian A1 - Baum, Daniel A1 - Wirkner, Christian S. A1 - Richter, Stefan T1 - Making spherical-harmonics-based Geometric Morphometrics (SPHARM) approachable for 3D images containing large cavity openings using Ambient Occlusion - a study using hermit crab claw shape variability N2 - An advantageous property of mesh-based geometric morphometrics (GM) towards landmark-based approaches, is the possibility of precisely examining highly irregular shapes and highly topographic surfaces. In case of spherical-harmonics-based GM the main requirement is a completely closed mesh surface, which often is not given, especially when dealing with natural objects. Here we present a methodological workflow to prepare 3D segmentations containing large cavity openings for the conduction of spherical-harmonics-based GM. This will be exemplified with a case study on claws of hermit crabs (Paguroidea, Decapoda, Crustacea), whereby joint openings – between manus and “movable finger” – typify the large-cavity-opening problem. We found a methodology including an ambient-occlusion-based segmentation algorithm leading to results precise and suitable to study the inter- and intraspecific differences in shape of hermit crab claws. Statistical analyses showed a significant separation between all examined diogenid and pagurid claws, whereas the separation between all left and right claws did not show significance. Additionally, the procedure offers other benefits. It is easy to reproduce and creates sparse variance in the data, closures integrate smoothly into the total structures and the algorithm saves a significant amount of time. T3 - ZIB-Report - 20-09 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-77744 SN - 1438-0064 ER - TY - GEN A1 - Clausecker, Robert T1 - The Quality of Heuristic Functions for IDA* N2 - The aim of this thesis is to deepen our understand of how IDA* heuristics influence the number of nodes expanded during search. To this end, we develop Korf's formula for the number of expanded nodes into a heuristic quality η which expresses the quality of a heuristic function as a constant factor on the number of expanded nodes, independent of a particular problem instance. We proceed to show how to compute η for some common kinds of heuristics and how to estimate η by means of a random sample for arbitrary heuristics. Using the value of η for some concrete examples, we then inspect for which parts of the search space the values of h(v) are particularly critical to the performance of the heuristic, allowing us to build better heuristics for future problems. This report originally appeared as a master thesis at Humboldt University of Berlin. T3 - ZIB-Report - 20-17 KW - IDA* heuristic search sampling random walks Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78489 SN - 1438-0064 ER - TY - GEN A1 - Taentzer, Gabriele A1 - Golas, Ulrike T1 - Local Confluence Analysis for Amalgamated Graph Transformation: Long Version N2 - Amalgamated graph transformation allows to define schemes of rules coinciding in common core activities and differing over additional parallel independent activities. Consequently, a rule scheme is specified by a kernel rule and a set of extending multi-rules forming an interaction scheme. Amalgamated transformations have been increasingly used in various modeling contexts. Critical Pair Analysis (CPA) can be used to show local confluence of graph transformation systems. It is an open challenge to lift the CPA to amalgamated graph transformation systems, especially since infinite many pairs of amalgamated rules occur in general. As a first step towards an efficient local confluence analysis of amalgamated graph transformation systems, we show that the analysis of a finite set of critical pairs suffices to prove local confluence. T3 - ZIB-Report - 15-29 KW - amalgamated graph transformation KW - parallel independence KW - critical pair analysis Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54943 SN - 1438-0064 ER - TY - GEN A1 - Schäfer, Patrick T1 - Bag-Of-SFA-Symbols in Vector Space (BOSS VS) N2 - Time series classification mimics the human understanding of similarity. When it comes to larger datasets, state of the art classifiers reach their limits in terms of unreasonable training or testing times. One representative example is the 1-nearest-neighbor DTW classifier (1-NN DTW) that is commonly used as the benchmark to compare to and has several shortcomings: it has a quadratic time and it degenerates in the presence of noise. To reduce the computational complexity lower bounding techniques or recently a nearest centroid classifier have been introduced. Still, execution times to classify moderately sized datasets on a single core are in the order of hours. We present our Bag-Of-SFA-Symbols in Vector Space (BOSS VS) classifier that is robust and accurate due to invariance to noise, phase shifts, offsets, amplitudes and occlusions. We show that it is as accurate while being multiple orders of magnitude faster than state of the art classifiers. Using the BOSS VS allows for mining massive time series datasets and real-time analytics. T3 - ZIB-Report - 15-30 KW - Time Series KW - Classification KW - Data Mining Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54984 SN - 1438-0064 ER - TY - GEN A1 - Aboulhassan, Amal A1 - Baum, Daniel A1 - Wodo, Olga A1 - Ganapathysubramanian, Baskar A1 - Amassian, Aram A1 - Hadwiger, Markus T1 - A Novel Framework for Visual Detection and Exploration of Performance Bottlenecks in Organic Photovoltaic Solar Cell Materials N2 - Current characterization methods of the so-called Bulk Heterojunction (BHJ), which is the main material of Organic Photovoltaic (OPV) solar cells, are limited to the analysis of global fabrication parameters. This reduces the efficiency of the BHJ design process, since it misses critical information about the local performance bottlenecks in the morphology of the material. In this paper, we propose a novel framework that fills this gap through visual characterization and exploration of local structure-performance correlations. We also propose a formula that correlates the structural features with the performance bottlenecks. Since research into BHJ materials is highly multidisciplinary, our framework enables a visual feedback strategy that allows scientists to build intuition about the best choices of fabrication parameters. We evaluate the usefulness of our proposed system by obtaining new BHJ characterizations. Furthermore, we show that our approach could substantially reduce the turnaround time. T3 - ZIB-Report - 15-20 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54353 SN - 1438-0064 ER - TY - GEN A1 - Aboulhassan, Amal A1 - Sicat, Ronell A1 - Baum, Daniel A1 - Wodo, Olga A1 - Hadwiger, Markus T1 - Comparative Visual Analysis of Structure-Performance Relations in Complex Bulk-Heterojunction Morphologies N2 - The structure of Bulk-Heterojunction (BHJ) materials, the main component of organic photovoltaic solar cells, is very complex, and the relationship between structure and performance is still largely an open question. Overall, there is a wide spectrum of fabrication configurations resulting in different BHJ morphologies and correspondingly different performances. Current state- of-the-art methods for assessing the performance of BHJ morphologies are either based on global quantification of morphological features or simply on visual inspection of the morphology based on experimental imaging. This makes finding optimal BHJ structures very challenging. Moreover, finding the optimal fabrication parameters to get an optimal structure is still an open question. In this paper, we propose a visual analysis framework to help answer these questions through comparative visualization and parameter space exploration for local morphology features. With our approach, we enable scientists to explore multivariate correlations between local features and performance indicators of BHJ morphologies. Our framework is built on shape-based clustering of local cubical regions of the morphology that we call patches. This enables correlating the features of clusters with intuition-based performance indicators computed from geometrical and topological features of charge paths. T3 - ZIB-Report - 17-16 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63239 SN - 1438-0064 ER - TY - GEN A1 - Rohr, Ulrich-Peter A1 - Herrmann, Pia A1 - Ilm, Katharina A1 - Zhang, Hai A1 - Lohmann, Sabine A1 - Reiser, Astrid A1 - Muranyi, Andrea A1 - Smith, Janice A1 - Burock, Susen A1 - Osterland, Marc A1 - Leith, Katherine A1 - Singh, Shalini A1 - Brunhoeber, Patrick A1 - Bowermaster, Rebecca A1 - Tie, Jeanne A1 - Christie, Michael A1 - Wong, Hui-Li A1 - Waring, Paul A1 - Shanmugam, Kandavel A1 - Gibbs, Peter A1 - Stein, Ulrike T1 - Prognostic value of MACC1 and proficient mismatch repair status for recurrence risk prediction in stage II colon cancer patients: the BIOGRID studies N2 - Background We assessed the novel MACC1 gene to further stratify stage II colon cancer patients with proficient mismatch repair (pMMR). Patients and methods Four cohorts with 596 patients were analyzed: Charité 1 discovery cohort was assayed for MACC1 mRNA expression and MMR in cryo-preserved tumors. Charité 2 comparison cohort was used to translate MACC1 qRT- PCR analyses to FFPE samples. In the BIOGRID 1 training cohort MACC1 mRNA levels were related to MACC1 protein levels from immunohistochemistry in FFPE sections; also analyzed for MMR. Chemotherapy-naïve pMMR patients were stratified by MACC1 mRNA and protein expression to establish risk groups based on recurrence-free survival (RFS). Risk stratification from BIOGRID 1 was confirmed in the BIOGRID 2 validation cohort. Pooled BIOGRID datasets produced a best effect-size estimate. Results In BIOGRID 1, using qRT-PCR and immunohistochemistry for MACC1 detection, pMMR/MACC1-low patients had a lower recurrence probability versus pMMR/MACC1-high patients (5-year RFS of 92% and 67% versus 100% and 68%, respectively). In BIOGRID 2, longer RFS was confirmed for pMMR/MACC1-low versus pMMR/MACC1-high patients (5-year RFS of 100% versus 90%, respectively). In the pooled dataset, 6.5% of patients were pMMR/MACC1-low with no disease recurrence, resulting in a 17% higher 5-year RFS (95% CI (12.6-21.3%)) versus pMMR/MACC1-high patients (P=0.037). Outcomes were similar for pMMR/MACC1-low and deficient MMR (dMMR) patients (5-year RFS of 100% and 96%, respectively). Conclusions MACC1 expression stratifies colon cancer patients with unfavorable pMMR status. Stage II colon cancer patients with pMMR/MACC1-low tumors have a similar favorable prognosis to those with dMMR with potential implications for the role of adjuvant therapy. T3 - ZIB-Report - 17-28 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64184 SN - 1438-0064 ER - TY - GEN A1 - Koltai, Péter A1 - Schütte, Christof T1 - A multi scale perturbation expansion approach for Markov state modeling of non-stationary molecular dynamics N2 - We investigate metastable dynamical systems subject to non-stationary forcing as they appear in molecular dynamics for systems driven by external fields. We show, that if the strength of the forcing is inversely proportional to the length of the slow metastable time scales of the unforced system, then the effective behavior of the forced system on slow time scales can be described by a low-dimensional reduced master equation. Our construction is explicit and uses the multiscale perturbation expansion method called two-timing, or method of multiple scales. The reduced master equation—a Markov state model—can be assembled by constructing two equilibrium Markov state models; one for the unforced system, and one for a slightly perturbed one. T3 - ZIB-Report - 17-49 KW - Markov state model KW - non-equilibrium molecular dynamics KW - two timescale master equation KW - non-stationary forcing KW - metastability Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64868 SN - 1438-0064 ER - TY - GEN A1 - Wolf, Thomas A1 - Amadi, Chimaobi T1 - Rational Solutions of Underdetermined Polynomial Equations N2 - In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work provides a method to compute rational solutions of single polynomial equations that are typically large with 10^2 ... 10^5 terms and that are heavily underdetermined. It was possible to obtain this functionality by adding a number of new modules for a new type of splitting of equations to the existing package CRACK that is normally used to solve polynomial algebraic and differential systems of equations. T3 - ZIB-Report - 17-33 KW - underdetermined polynomial systems, rational solutions, computer algebra, recreational mathematics Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64488 SN - 1438-0064 ER - TY - GEN A1 - Willenbockel, Christian Tobias A1 - Schütte, Christof T1 - Variational Bayesian Inference and Model Selection for the Stochastic Block Model with Irrelevant Vertices N2 - Real World networks often exhibit a significant number of vertices which are sparsely and irregularly connected to other vertices in the network. For clustering theses networks with a model based algorithm, we propose the Stochastic Block Model with Irrelevant Vertices (SBMIV) for weighted net- works. We propose an original Variational Bayesian Expectation Maximiza- tion inference algorithm for the SBMIV which is an advanced version of our Blockloading algorithm for the Stochastic Block Model. We introduce a model selection criterion for the number of clusters of the SBMIV which is based on the lower variational bound of the model likelihood. We propose a fully Bayesian inference process, based on plausible informative priors, which is independent of other algorithms for preprocessing start values for the cluster assignment of vertices. Our inference methods allow for a multi level identification of irrelevant vertices which are hard to cluster reliably ac- cording to the SBM. We demonstrate that our methods improve on the normal Stochastic Block model by applying it to to Earthquake Networks which are an example of networks with a large number of sparsely and irregularly con- nected vertices. T3 - ZIB-Report - 16-01 KW - Clustering KW - Variational Bayes EM KW - Model Selection, KW - Stochastic Block Model KW - Networks KW - unsupervised classification KW - Noise Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57003 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin T1 - Challenges in Atomistic-to-Continuum Coupling T2 - ZIB Report N2 - This paper is concerned with the design, analysis, and implementation of concurrent coupling approaches where different (atomic and continuous) models are used simultaneously within a single simulation process. Thereby, several problems or pitfalls can happen, for example, the reflection of molecular movements at the “boundary” between the atomic and continuum regions which leads to an unphysical increase in energy in the atomic model. We investigate the problems with the aim of giving an introduction into this field and preventing errors for scientists starting their research towards multiscale methods. Y1 - 2010 U6 - https://doi.org/10.1155/2015/834517 VL - 2010 ET - 10-12 ER - TY - GEN A1 - Koltai, Peter A1 - Ciccotti, Giovanni A1 - Schütte, Christof T1 - On metastability and Markov state models for non-stationary molecular dynamics BT - 2016 Editor's Choice of The Journal of Chemical Physics T2 - The Journal of Chemical Physics N2 - We utilize the theory of coherent sets to build Markov state models for non- equilibrium molecular dynamical systems. Unlike for systems in equilibrium, “meta- stable” sets in the non-equilibrium case may move as time evolves. We formalize this concept by relying on the theory of coherent sets, based on this we derive finite-time non-stationary Markov state models, and illustrate the concept and its main differences to equilibrium Markov state modeling on simple, one-dimensional examples. T3 - ZIB-Report - 16-11 KW - coherent set, KW - Markov state model KW - non-equilibrium molecular dynamics KW - metastability Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57869 SN - 1438-0064 VL - 174103 ET - 145 ER - TY - GEN A1 - Clausecker, Robert T1 - Notes on the Construction of Pattern Databases N2 - This report aims to explain and extend pattern databases as a tool in finding optimal solutions to combination puzzles. Using sliding tile puzzles as an example, an overview over techniques to construct and use pattern databases is given, analysed, and extended. As novel results, zero aware additive pattern databases and PDB catalogues are introduced. This report originally appeared as a bachelor thesis at Humboldt University of Berlin under the title Notes on the Construction of Tablebases. T3 - ZIB-Report - 17-59 KW - pattern-database 15-puzzle 24-puzzle ida* heuristic-search pdb-catalogue zpdb Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65586 SN - 1438-0064 ER - TY - GEN A1 - Mokhtari, Zahra A1 - Patterson, Robert I. A. A1 - Höfling, Felix T1 - Spontaneous trail formation in populations of auto-chemotactic walkers N2 - We study the formation of trails in populations of self-propelled agents that make oriented deposits of pheromones and also sense such deposits to which they then respond with gradual changes of their direction of motion. Based on extensive off-lattice computer simulations aiming at the scale of insects, e.g., ants, we identify a number of emerging stationary patterns and obtain qualitatively the non-equilibrium \add{state} diagram of the model, spanned by the strength of the agent--pheromone interaction and the number density of the population. In particular, we demonstrate the spontaneous formation of persistent, macroscopic trails, and highlight some behaviour that is consistent with a dynamic phase transition. This includes a characterisation of the mass of system-spanning trails as a potential order parameter. We also propose a dynamic model for a few macroscopic observables, including the sub-population size of trail-following agents, which captures the early phase of trail formation. T3 - ZIB-Report - 21-36 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84466 SN - 1438-0064 ER - TY - GEN A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem N2 - We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 SN - 1438-0064 ER - TY - GEN A1 - Pulaj, Jonad A1 - Raymond, Annie A1 - Theis, Dirk T1 - New Conjectures For Union-Closed Families N2 - The Frankl conjecture, also known as the union-closed sets conjecture, states that there exists an element in at least half of the sets of any (non-empty) union-closed family. From an optimization point of view, one could instead prove that 2a is an upper bound to the number of sets in a union-closed family with n elements where each element is in at most a sets, where a and n are non-negative integers. Formulating these problems as integer programs we observe that computed optimal values do not vary with n. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we partially prove the new conjectures and discuss possible approaches to solve them completely. T3 - ZIB-Report - 15-57 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56804 SN - 1438-0064 ER - TY - GEN A1 - Hartmann, Carsten A1 - Richter, Lorenz A1 - Schütte, Christof A1 - Zhang, Wei T1 - Variational characterization of free energy: Theory and algorithms N2 - The article surveys and extends variational formulations of the thermodynamic free energy and discusses their information-theoretic content from the perspective of mathematical statistics. We revisit the well-known Jarzynski equality for nonequilibrium free energy sampling within the framework of importance sampling and Girsanov change-of-measure transformations. The implications of the different variational formulations for designing efficient stochastic optimization and nonequilibrium simulation algorithms for computing free energies are discussed and illustrated. T3 - ZIB-Report - 17-52 KW - Importance sampling KW - Donsker-Varadhan principle KW - thermodynamic free energy KW - nonequilibrium molecular dynamics KW - stochastic approximation KW - cross-entropy method Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65045 SN - 1438-0064 ER -