Search

High-performance sparse matrix-matrix (SpMM) multiplication is paramount for science and industry, as the ever-increasing sizes of data prohibit using dense data structures. Yet, existing hardware, such as Tensor Cores (TC), is ill-suited for SpMM, as it imposes strict constraints on data structures that cannot be met by unstructured sparsity found in many applications. To address this, we introduce (S)parse (Ma)trix Matrix (T)ensor Core-accelerated (SMaT): a novel SpMM library that utilizes TCs for unstructured sparse matrices. Our block-sparse library leverages the low-level CUDA MMA (matrix-matrix-accumulate) API, maximizing the performance offered by modern GPUs. Algorithmic optimizations such as sparse matrix permutation further improve performance by minimizing the number of non-zero blocks. The evaluation on NVIDIA A100 shows that SMaT outperforms SotA libraries (DASP, cuSPARSE, and Magicube) by up to 125x (on average 2.6x). SMaT can be used to accelerate many workloads in scientific computing, large-model training, inference, and others., Comment: Accepted by 2024 International Conference on High Performance Computing, Networking, Storage and Analysis, 2023 (SC'24)

We define reduced and essential Banach algebras associated to a twisted \'{e}tale (not necessarily Hausdorff) groupoid $(\mathcal{G},\mathcal{L})$ and extend some fundamental results from $C^*$-algebras to this context. For instance, we prove that for topologically free and minimal groupoids every essential Banach algebra is simple, and we give conditions under which reduced algebras are essential (for example Hausdorffness of $\mathcal{G}$ is sufficient). This in particular solves the simplicity problem posed recently by Gardella-Lupini for $L^p$-operator algebras associated to $\mathcal{G}$. In addition, using either the $n$-filling or locally contracting condition we give pure infiniteness criteria for essential simple Banach algebras associated to $(\mathcal{G},\mathcal{L})$. This extends the corresponding $C^*$-algebraic results that were previously known to hold in the untwisted Hausdorff case. The results work nicely, and allow for characterisation of the generalized intersection property, in the realm of $L^P$-operator algebras where $P \subseteq [1,\infty]$ is a non-empty set of parameters. Such algebras cover in particular $L^p$-operator algebras, for $p\in [1,\infty]$, and their Banach $*$-algebra versions. We apply our results to Banach algebra crossed products by twisted partial group actions, Roe-type Banach algebras with coefficients in finite-rank operators on a Banach space, twisted tight $L^P$-operator algebras of inverse semigroups, graph $L^P$-operator algebras, and algebras associated to self-similar group actions on graphs. We also interpret our results in terms of twisted inverse semigroup actions and their crossed products., Comment: Comments welcome

We extend the theory of Fourier--Stieltjes algebras to the category of twisted actions by \'etale groupoids on arbitrary C*-bundles, generalizing theories constructed previously by B\'{e}dos and Conti for twisted group actions on unital C*-algebras, and by Renault and others for groupoid C*-algebras, in each case motivated by the classical theory of Fourier--Stieltjes algebras of discrete groups. To this end we develop a toolbox including, among other things, a theory of multiplier C*-correspondences, multiplier C*-correspondence bundles, Busby--Smith twisted groupoid actions, and the associated crossed products, equivariant representations and Fell's absorption theorems. For a fixed \'etale groupoid $G$ a Fourier--Stieltjes multiplier is a family of maps acting on fibers, arising from an equivariant representation. It corresponds to a certain fiber-preserving strict completely bounded map between twisted full (or reduced) crossed products. We establish a KSGNS-type dilation result which shows that the correspondence above restricts to a bijection between positive-definite multipliers and a particular class of completely positive maps. Further we introduce a subclass of Fourier multipliers, that enjoys a natural absorption property with respect to Fourier--Stieltjes multipliers and gives rise to `reduced to full' multiplier maps on crossed products. Finally we provide several applications of the theory developed, for example to the approximation properties, such as weak containment or nuclearity, of the crossed products and actions in question, and discuss outstanding open problems., Comment: 76 pages

The field of natural language processing (NLP) has witnessed significant progress in recent years, with a notable focus on improving large language models' (LLM) performance through innovative prompting techniques. Among these, prompt engineering coupled with structures has emerged as a promising paradigm, with designs such as Chain-of-Thought, Tree of Thoughts, or Graph of Thoughts, in which the overall LLM reasoning is guided by a structure such as a graph. As illustrated with numerous examples, this paradigm significantly enhances the LLM's capability to solve numerous tasks, ranging from logical or mathematical reasoning to planning or creative writing. To facilitate the understanding of this growing field and pave the way for future developments, we devise a general blueprint for effective and efficient LLM reasoning schemes. For this, we conduct an in-depth analysis of the prompt execution pipeline, clarifying and clearly defining different concepts. We then build the first taxonomy of structure-enhanced LLM reasoning schemes. We focus on identifying fundamental classes of harnessed structures, and we analyze the representations of these structures, algorithms executed with these structures, and many others. We refer to these structures as reasoning topologies, because their representation becomes to a degree spatial, as they are contained within the LLM context. Our study compares existing prompting schemes using the proposed taxonomy, discussing how certain design choices lead to different patterns in performance and cost. We also outline theoretical underpinnings, relationships between prompting and other parts of the LLM ecosystem such as knowledge bases, and the associated research challenges. Our work will help to advance future prompt engineering techniques.

We generalize the well known $C^*$-algebraic result of Kawamura-Tomiyama and Archbold-Spielberg for crossed products of discrete transformation groups to the realm of Banach algebras and twisted actions. Namely we show that topological freeneess is equivalent to the intersection property for all reduced twisted Banach algebra crossed products coming from subgroups, and in the untwisted case to a generalized intersection property for a full $L^p$-operator algebra crossed product for some (and hence any) $p\in [1,\infty]$. This gives efficient simplicity criteria for various Banach algebra crossed products. We also use it to identify the prime ideal space of some crossed products as the quasi-orbit space of the action. For amenable actions we prove that the full and reduced twisted $L^p$-operator algebras coincide., Comment: 25 pages

We introduce Banach algebras associated to a twisted \'etale groupoid $(\mathcal{G},\mathcal{L})$ and to twisted inverse semigroup actions. This provides a unifying framework for numerous recent papers on $L^p$-operator algebras and the theory of groupoid $C^*$-algebras. We prove a disintegration theorem that allows us to study Banach algebras associated to $(\mathcal{G},\mathcal{L})$ as universal Banach algebras generated by $C_0(X)$ and a twisted inverse semigroup $S$ of partial isometries subject to some relations. Our theory works best when the groupoid is ample or when the target of a representation is a dual Banach algebra $B$, so for instance $B=B(E)$ where $E$ is a reflexive Banach space. In particular, it implies that in the constructions of $L^p$-analogues of Cuntz or graph algebras, by Phillips and Corti\~{n}as--Rodr\'{\i}guez, the use of \emph{spatial partial isometries} is not an assumption, in fact it is forced by the relations. We establish fundamental norm estimates and hierarchy for full and reduced $L^p$-operator algebras for $(\mathcal{G},\mathcal{L})$ and $p \in [1,\infty]$, whose special cases have been studied recently by Gardella--Lupini, Choi--Gardella--Thiel and Hetland--Ortega. We also introduce tight inverse semigroup Banach algebras that cover ample groupoid Banach algebras, and we discuss Banach algebras associated to twisted partial group actions, twisted Renault--Deaconu groupoids and directed graphs. Our Banach Cuntz algebras are related to the construction of Daws--Horv\'{a}th. We aim for a high degree of generality throughout: our results cover non-Hausdorff \'{e}tale groupoids and both real and complex algebras. Some of our results seem to be absent from the literature even for $C^*$-algebras., Comment: The definition of a groupoid Banach algebra now involves a specified inverse semigroup, which allows us to correct a problem in Proposition 4.21 of the previous version. A question concerning the real case (Remark 2.13 of the previous version) is now solved. Updates to the rest of the manuscript reflect these two main changes

Important graph mining problems such as Clustering are computationally demanding. To significantly accelerate these problems, we propose ProbGraph: a graph representation that enables simple and fast approximate parallel graph mining with strong theoretical guarantees on work, depth, and result accuracy. The key idea is to represent sets of vertices using probabilistic set representations such as Bloom filters. These representations are much faster to process than the original vertex sets thanks to vectorizability and small size. We use these representations as building blocks in important parallel graph mining algorithms such as Clique Counting or Clustering. When enhanced with ProbGraph, these algorithms significantly outperform tuned parallel exact baselines (up to nearly 50x on 32 cores) while ensuring accuracy of more than 90% for many input graph datasets. Our novel bounds and algorithms based on probabilistic set representations with desirable statistical properties are of separate interest for the data analytics community., Comment: Best Paper Award at ACM/IEEE Supercomputing'22 (SC22)

GaN nanowires (NWs) grown by molecular beam epitaxy on Ti films sputtered on Al$_{2}$O$_{3}$ are studied by X-ray diffraction (XRD) and grazing incidence small-angle X-ray scattering (GISAXS). XRD, performed both in symmetric Bragg reflection and at grazing incidence, reveals Ti, Ti$_{3}$O, Ti$_{3}$Al, and TiO$_x$N$_y$ crystallites with in-plane and out-of-plane lattice parameters intermediate between those of Al$_{2}$O$_{3}$ and GaN. These topotaxial crystallites in Ti film, formed due to interfacial reactions and N exposure, possess fairly little misorientation with respect to Al$_{2}$O$_{3}$. As a result, GaN NWs grow on the top TiN layer possessing a high degree of epitaxial orientation with respect to the substrate. The measured GISAXS intensity distributions are modeled by the Monte Carlo method taking into account the orientational distributions of NWs, a variety of their cross-sectional shapes and sizes, and roughness of their side facets. The cross-sectional size distributions of the NWs and the relative fractions of $(1\bar{1}00)$ and $(11\bar{2}0)$ side facets are determined.

Multilinear algebra kernel performance on modern massively-parallel systems is determined mainly by data movement. However, deriving data movement-optimal distributed schedules for programs with many high-dimensional inputs is a notoriously hard problem. State-of-the-art libraries rely on heuristics and often fall back to suboptimal tensor folding and BLAS calls. We present Deinsum, an automated framework for distributed multilinear algebra computations expressed in Einstein notation, based on rigorous mathematical tools to address this problem. Our framework automatically derives data movement-optimal tiling and generates corresponding distributed schedules, further optimizing the performance of local computations by increasing their arithmetic intensity. To show the benefits of our approach, we test it on two important tensor kernel classes: Matricized Tensor Times Khatri-Rao Products and Tensor Times Matrix chains. We show performance results and scaling on the Piz Daint supercomputer, with up to 19x speedup over state-of-the-art solutions on 512 nodes.

Our initial data is a transfer operator $L$ for a continuous, countable-to-one map $\varphi:\Delta \to X$ defined on an open subset of a locally compact Hausdorff space $X$. Then $L$ may be identified with a `potential', i.e. a map $\varrho:\Delta\to X$ that need not be continuous unless $\varphi$ is a local homeomorphism. We define the crossed product $C_0(X)\rtimes L$ as a universal $C^*$-algebra with explicit generators and relations, and give an explicit faithful representation of $C_0(X)\rtimes L$ under which it is generated by weighted composition operators. We explain its relationship with Exel-Royer's crossed products, quiver $C^*$-algebras of Muhly and Tomforde, $C^*$-algebras associated to complex or self-similar dynamics by Kajiwara and Watatani, and groupoid $C^*$-algebras associated to Deaconu-Renault groupoids. We describe spectra of core subalgebras of $C_0(X)\rtimes L$ and use it to characterise simplicity of $C_0(X)\rtimes L$ and prove the uniqueness theorem for $C_0(X)\rtimes L$. We give efficient criteria for $C_0(X)\rtimes L$ to be a Kirchberg algebra, and we discuss relationship between KMS states on the core subalgebra of $C_0(X)\rtimes L$ and conformal measures for $\varphi$., Comment: 38 pages

C is the lingua franca of programming and almost any device can be programmed using C. However, programming mod-ern heterogeneous architectures such as multi-core CPUs and GPUs requires explicitly expressing parallelism as well as device-specific properties such as memory hierarchies. The resulting code is often hard to understand, debug, and modify for different architectures. We propose to lift C programs to a parametric dataflow representation that lends itself to static data-centric analysis and enables automatic high-performance code generation. We separate writing code from optimizing for different hardware: simple, portable C source code is used to generate efficient specialized versions with a click of a button. Our approach can identify parallelism when no other compiler can, and outperforms a bespoke parallelized version of a scientific proxy application by up to 21%.

Let $A\subseteq B$ be a $C^*$-inclusion. We give efficient conditions under which $A$ separates ideals in $B$, and $B$ is purely infinite if every positive element in $A$ is properly infinite in $B$. We specialise to the case when $B$ is a crossed product for an inverse semigroup action by Hilbert bimodules or a section $C^*$-algebra of a Fell bundle over an \'etale, possibly non-Hausdorff, groupoid. Then our theory works provided $B$ is the recently introduced essential crossed product and the action is essentially exact and residually aperiodic or residually topologically free. These last notions are developed in the article., Comment: An error in the earlier version of Proposition 4.2 is fixed (we thank Alcides Buss, Diego Mart\'inez and Jonathan Taylor for pointing it to us). To appear in Journal of Noncommutative Geometry

Matrix factorizations are among the most important building blocks of scientific computing. State-of-the-art libraries, however, are not communication-optimal, underutilizing current parallel architectures. We present novel algorithms for Cholesky and LU factorizations that utilize an asymptotically communication-optimal 2.5D decomposition. We first establish a theoretical framework for deriving parallel I/O lower bounds for linear algebra kernels, and then utilize its insights to derive Cholesky and LU schedules, both communicating N^3/(P*sqrt(M)) elements per processor, where M is the local memory size. The empirical results match our theoretical analysis: our implementations communicate significantly less than Intel MKL, SLATE, and the asymptotically communication-optimal CANDMC and CAPITAL libraries. Our code outperforms these state-of-the-art libraries in almost all tested scenarios, with matrix sizes ranging from 2,048 to 262,144 on up to 512 CPU nodes of the Piz Daint supercomputer, decreasing the time-to-solution by up to three times. Our code is ScaLAPACK-compatible and available as an open-source library., Comment: 15 pages (including references), 11 figures. arXiv admin note: substantial text overlap with arXiv:2010.05975

Link prediction is one of the central problems in graph mining. However, recent studies highlight the importance of higher-order network analysis, where complex structures called motifs are the first-class citizens. We first show that existing link prediction schemes fail to effectively predict motifs. To alleviate this, we establish a general motif prediction problem and we propose several heuristics that assess the chances for a specified motif to appear. To make the scores realistic, our heuristics consider - among others - correlations between links, i.e., the potential impact of some arriving links on the appearance of other links in a given motif. Finally, for highest accuracy, we develop a graph neural network (GNN) architecture for motif prediction. Our architecture offers vertex features and sampling schemes that capture the rich structural properties of motifs. While our heuristics are fast and do not need any training, GNNs ensure highest accuracy of predicting motifs, both for dense (e.g., k-cliques) and for sparse ones (e.g., k-stars). We consistently outperform the best available competitor by more than 10% on average and up to 32% in area under the curve. Importantly, the advantages of our approach over schemes based on uncorrelated link prediction increase with the increasing motif size and complexity. We also successfully apply our architecture for predicting more arbitrary clusters and communities, illustrating its potential for graph mining beyond motif analysis.

Determining I/O lower bounds is a crucial step in obtaining communication-efficient parallel algorithms, both across the memory hierarchy and between processors. Current approaches either study specific algorithms individually, disallow programmatic motifs such as recomputation, or produce asymptotic bounds that exclude important constants. We propose a novel approach for obtaining precise I/O lower bounds on a general class of programs, which we call Simple Overlap Access Programs (SOAP). SOAP analysis covers a wide variety of algorithms, from ubiquitous computational kernels to full scientific computing applications. Using the red-blue pebble game and combinatorial methods, we are able to bound the I/O of the SOAP-induced Computational Directed Acyclic Graph (CDAG), taking into account multiple statements, input/output reuse, and optimal tiling. To deal with programs that are outside of our representation (e.g., non-injective access functions), we describe methods to approximate them with SOAP. To demonstrate our method, we analyze 38 different applications, including kernels from the Polybench benchmark suite, deep learning operators, and -- for the first time -- applications in unstructured physics simulations, numerical weather prediction stencil compositions, and full deep neural networks. We derive tight I/O bounds for several linear algebra kernels, such as Cholesky decomposition, improving the existing reported bounds by a factor of two. For stencil applications, we improve the existing bounds by a factor of up to 14. We implement our method as an open-source tool, which can derive lower bounds directly from provided C code., Comment: 13 pages, 4 figures, published at Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21)

Simple graph algorithms such as PageRank have been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such as clustering or maximal clique listing. These algorithms are memory-bound and thus could be accelerated by hardware techniques such as Processing-in-Memory (PIM). However, they also come with nonstraightforward parallelism and complicated memory access patterns. In this work, we address this problem with a simple yet surprisingly powerful observation: operations on sets of vertices, such as intersection or union, form a large part of many complex graph mining algorithms, and can offer rich and simple parallelism at multiple levels. This observation drives our cross-layer design, in which we (1) expose set operations using a novel programming paradigm, (2) express and execute these operations efficiently with carefully designed set-centric ISA extensions called SISA, and (3) use PIM to accelerate SISA instructions. The key design idea is to alleviate the bandwidth needs of SISA instructions by mapping set operations to two types of PIM: in-DRAM bulk bitwise computing for bitvectors representing high-degree vertices, and near-memory logic layers for integer arrays representing low-degree vertices. Set-centric SISA-enhanced algorithms are efficient and outperform hand-tuned baselines, offering more than 10x speedup over the established Bron-Kerbosch algorithm for listing maximal cliques. We deliver more than 10 SISA set-centric algorithm formulations, illustrating SISA's wide applicability., Comment: Proceedings of the 54th IEEE/ACM International Symposium on Microarchitecture (MICRO'21), 2021

We propose GraphMineSuite (GMS): the first benchmarking suite for graph mining that facilitates evaluating and constructing high-performance graph mining algorithms. First, GMS comes with a benchmark specification based on extensive literature review, prescribing representative problems, algorithms, and datasets. Second, GMS offers a carefully designed software platform for seamless testing of different fine-grained elements of graph mining algorithms, such as graph representations or algorithm subroutines. The platform includes parallel implementations of more than 40 considered baselines, and it facilitates developing complex and fast mining algorithms. High modularity is possible by harnessing set algebra operations such as set intersection and difference, which enables breaking complex graph mining algorithms into simple building blocks that can be separately experimented with. GMS is supported with a broad concurrency analysis for portability in performance insights, and a novel performance metric to assess the throughput of graph mining algorithms, enabling more insightful evaluation. As use cases, we harness GMS to rapidly redesign and accelerate state-of-the-art baselines of core graph mining problems: degeneracy reordering (by up to >2x), maximal clique listing (by up to >9x), k-clique listing (by 1.1x), and subgraph isomorphism (by up to 2.5x), also obtaining better theoretical performance bounds.

Function-as-a-Service (FaaS) is one of the most promising directions for the future of cloud services, and serverless functions have immediately become a new middleware for building scalable and cost-efficient microservices and applications. However, the quickly moving technology hinders reproducibility, and the lack of a standardized benchmarking suite leads to ad-hoc solutions and microbenchmarks being used in serverless research, further complicating metaanalysis and comparison of research solutions. To address this challenge, we propose the Serverless Benchmark Suite: the first benchmark for FaaS computing that systematically covers a wide spectrum of cloud resources and applications. Our benchmark consists of the specification of representative workloads, the accompanying implementation and evaluation infrastructure, and the evaluation methodology that facilitates reproducibility and enables interpretability. We demonstrate that the abstract model of a FaaS execution environment ensures the applicability of our benchmark to multiple commercial providers such as AWS, Azure, and Google Cloud. Our work facilities experimental evaluation of serverless systems, and delivers a standardized, reliable and evolving evaluation methodology of performance, efficiency, scalability and reliability of middleware FaaS platforms., Comment: Extended version of the paper accepted at Middleware 2021

Dense linear algebra kernels, such as linear solvers or tensor contractions, are fundamental components of many scientific computing applications. In this work, we present a novel method of deriving parallel I/O lower bounds for this broad family of programs. Based on the X-partitioning abstraction, our method explicitly captures inter-statement dependencies. Applying our analysis to LU factorization, we derive COnfLUX, an LU algorithm with the parallel I/O cost of $N^3 / (P \sqrt{M})$ communicated elements per processor -- only $1/3\times$ over our established lower bound. We evaluate COnfLUX on various problem sizes, demonstrating empirical results that match our theoretical analysis, communicating asymptotically less than Cray ScaLAPACK or SLATE, and outperforming the asymptotically-optimal CANDMC library. Running on $1$,$024$ nodes of Piz Daint, COnfLUX communicates 1.6$\times$ less than the second-best implementation and is expected to communicate 2.1$\times$ less on a full-scale run on Summit., Comment: 13 pages without references, 12 figures, submitted to PPoPP 2021: 26th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

We prove implications among the conditions in the title for an inclusion of a C*-algebra A in a C*-algebra B, and we also relate this to several other properties in case B is a crossed product for an action of a group, inverse semigroup or an \'etale groupoid on A. We show that an aperiodic C*-inclusion has a unique pseudo-expectation. If, in addition, the unique pseudo-expectation is faithful, then A supports B in the sense of the Cuntz preorder. The almost extension property implies aperiodicity, and the converse holds if B is separable. A crossed product inclusion has the almost extension property if and only if the dual groupoid of the action is topologically principal. Topologically free actions are always aperiodic. If A is separable or of Type I, then topological freeness, aperiodicity and having a unique pseudo-expectation are equivalent to the condition that A detects ideals in all intermediate C*-algebras. If, in addition, B is separable, then all these conditions are equivalent to the almost extension property., Comment: Title modified and figure 1 moved to the introduction, what has been imposed by the editors

We introduce the Haagerup property for twisted groupoid $C^*$-dynamical systems in terms of naturally defined positive-definite operator-valued multipliers. By developing a version of `the Haagerup trick' we prove that this property is equivalent to the Haagerup property of the reduced crossed product $C^*$-algebra with respect to the canonical conditional expectation $E$. This extends a theorem of Dong and Ruan for discrete group actions, and implies that a given Cartan inclusion of separable $C^*$-algebras has the Haagerup property if and only if the associated Weyl groupoid has the Haagerup property in the sense of Tu. We use the latter statement to prove that every separable $C^*$-algebra which has the Haagerup property with respect to some Cartan subalgebra satisfies the Universal Coefficient Theorem. This generalises a recent result of Barlak and Li on the UCT for nuclear Cartan pairs., Comment: 40 pages; v2 introduces many small corrections and updates references. The final version of the paper will appear in the Journal of Functional Analysis

Data movement is the dominating factor affecting performance and energy in modern computing systems. Consequently, many algorithms have been developed to minimize the number of I/O operations for common computing patterns. Matrix multiplication is no exception, and lower bounds have been proven and implemented both for shared and distributed memory systems. Reconfigurable hardware platforms are a lucrative target for I/O minimizing algorithms, as they offer full control of memory accesses to the programmer. While bounds developed in the context of fixed architectures still apply to these platforms, the spatially distributed nature of their computational and memory resources requires a decentralized approach to optimize algorithms for maximum hardware utilization. We present a model to optimize matrix multiplication for FPGA platforms, simultaneously targeting maximum performance and minimum off-chip data movement, within constraints set by the hardware. We map the model to a concrete architecture using a high-level synthesis tool, maintaining a high level of abstraction, allowing us to support arbitrary data types, and enables maintainability and portability across FPGA devices. Kernels generated from our architecture are shown to offer competitive performance in practice, scaling with both compute and memory resources. We offer our design as an open source project to encourage the open development of linear algebra and I/O minimizing algorithms on reconfigurable hardware platforms.

Synchronization overheads pose a major challenge as applications advance towards extreme scales. In current large-scale algorithms, synchronization as well as data communication delay the parallel computations at each time step in a time-dependent partial differential equation (PDE) solver. This creates a new scaling wall when moving towards exascale. We present a weakly-synchronous algorithm based on novel asynchrony-tolerant (AT) finite-difference schemes that relax synchronization at a mathematical level. We utilize remote memory access programming schemes that have been shown to provide significant speedup on modern supercomputers, to efficiently implement communications suitable for AT schemes, and compare to two-sided communications that are state-of-practice. We present results from simulations of Burgers' equation as a model of multi-scale strongly non-linear dynamical systems. Our algorithm demonstrate excellent scalability of the new AT schemes for large-scale computing, with a speedup of up to $3.3$x in communication time and $2.19$x in total runtime. We expect that such schemes can form the basis for exascale PDE algorithms.

We study the spectrum of operators $aT\in B(H)$ on a Hilbert space $H$ where $T$ is an isometry and $a$ belongs to a commutative $C^*$-subalgebra $C(X)\cong A\subseteq B(H)$ such that the formula $L(a)=T^*aT$ defines a faithful transfer operator on $A$. Based on the analysis of the $C^*$-algebra $C^*(A,T)$ generated by the operators $aT$, $a\in A$, we give dynamical conditions implying that the spectrum $\sigma(aT)$ is invariant under rotation around zero, $\sigma(aT)$ coincides with essential spectrum $\sigma_{ess}(aT)$ or that $\sigma(aT)=\{z\in \mathbb{C}: |z|\leq r(aT)\}$ is a disk. We extend classical Ruelle's result and prove that for a general expanding map $\varphi:X\to X$ and continuous $c:X\to [0,\infty)$ the spectral logarythm of a Ruelle-Perron-Frobenious operator $\mathcal{L}_cf(y)=\sum_{x\in \varphi^{-1}(y)} c(x)f(x)$ is equal to the topological pressure $P(\ln c,\varphi)$. As a consequence we get the variational principle for the spectral radius: $$ r(aT)=\max_{\mu\in \text{Erg}(X,\varphi)} \exp\left(\int_{{X}}\ln(\vert a\vert\sqrt{\varrho })\,d\mu +\frac{h_{\varphi}(\mu)}{2} \right), $$ where $\text{Erg}(X,\varphi)$ stands for ergodic Borel probability measures, $h_{\varphi}(\mu)$ is the Kolmogorov-Sinai entropy, and $\varrho:X\to [0,1]$ is the cocycle associated to $L$. In particular, we clarify the relationship between the Kolmogorov-Sinai entropy and $t$-entropy introduced by Antonevich, Bakhtin and Lebedev., Comment: 37 pages, some typos fixed, accepted for publication in the Israel Journal of Mathematics

We propose COSMA: a parallel matrix-matrix multiplication algorithm that is near communication-optimal for all combinations of matrix dimensions, processor counts, and memory sizes. The key idea behind COSMA is to derive an optimal (up to a factor of 0.03\% for 10MB of fast memory) sequential schedule and then parallelize it, preserving I/O optimality. To achieve this, we use the red-blue pebble game to precisely model MMM dependencies and derive a constructive and tight sequential and parallel I/O lower bound proofs. Compared to 2D or 3D algorithms, which fix processor decomposition upfront and then map it to the matrix dimensions, it reduces communication volume by up to $\sqrt{3}$ times. COSMA outperforms the established ScaLAPACK, CARMA, and CTF algorithms in all scenarios up to 12.8x (2.2x on average), achieving up to 88\% of Piz Daint's peak performance. Our work does not require any hand tuning and is maintained as an open source implementation., Comment: 18 pages, 29 figures, short version submitted to the SC'19 conference

We characterise Exel's noncommutative Cartan subalgebras in several ways using uniqueness of conditional expectations, relative commutants, or purely outer inverse semigroup actions. We describe in which sense the crossed product decomposition for a noncommutative Cartan subalgebra is unique. We relate the property of being a noncommutative Cartan subalgebra to aperiodic inclusions and effectivity of dual groupoids. In particular, we extend Renault's characterisation of commutative Cartan subalgebras., Comment: This version is accepted for publication in the Transactions of the American Mathematical Society. Proposition 4.8 is reformulated (due to a previous gap in the proof). As a consequence, we replaced almost faithful by faithful in a few places

We study simplicity and pure infiniteness criteria for C*-algebras associated to inverse semigroup actions by Hilbert bimodules and to Fell bundles over etale not necessarily Hausdorff groupoids. Inspired by recent work of Exel and Pitts, we introduce essential crossed products for which there are such criteria. In our approach the major role is played by a generalised expectation with values in the local multiplier algebra. We give a long list of equivalent conditions characterising when the essential and reduced C*-algebras coincide. Our most general simplicity and pure infiniteness criteria apply to aperiodic C*-inclusions equipped with supportive generalised expectations. We thoroughly discuss the relationship between aperiodicity, detection of ideals, purely outer inverse semigroup actions, and non-triviality conditions for dual groupoids., Comment: Version accepted for publication (a number of small changes, references to more recent work added)

We give formulas for the spectral radius of weighted endomorphisms $a\alpha: C(X,D)\to C(X,D)$, $a\in C(X,D)$, where $X$ is a compact Hausdorff space and $D$ is a unital Banach algebra. Under the assumption that $\alpha$ generates a partial dynamical system $(X,\varphi)$, we establish two kinds of variational principles for $r(a\alpha)$: using linear extensions of $(X,\varphi)$ and using Lyapunov exponents associated with ergodic measures for $(X,\varphi)$. This requires considering (twisted) cocycles over $(X,\varphi)$ with values in an arbitrary Banach algebra $D$, and thus our analysis can not be reduced to any of mutliplicative ergodic theorems known so far. The established variational principles apply not only to weighted endomorphisms but also to a vast class of operators acting on Banach spaces that we call abstract weighted shifts associated with $\alpha: C(X,D)\to C(X,D)$. In particular, they are far reaching generalizations of formulas obtained by Kitover, Lebedev, Latushkin, Stepin and others. They are most efficient when $D=\mathcal{B}(F)$, for a Banach space $F$, and endomorphisms of $\mathcal{B}(F)$ induced by $\alpha$ are inner isometric. As a by product we obtain a dynamical variational principle for an arbitrary operator $b\in \mathcal{B}(F)$ and that it's spectral radius is always a Lyapunov exponent in some direction $v\in F$, when $F$ is reflexive., Comment: 37 pages. This is a version accepted in Trans. Amer. Math. Soc. (added some more examples and section 6 "Concluding remarks and potential applications")

Based on differential thermal analysis (DTA) and X-ray powder diffraction (XRD), a description of the system Nd$_2$O$_3$--Lu$_2$O$_3$--Sc$_2$O$_3$ was obtained by thermodynamic assessment. Four fields of primary crystallization could be identified; from melt compositions close to the Lu$_2$O$_3$--Sc$_2$O$_3$ edge the rare-earth oxide C-phase crystallizes first, which is stable down to room temperature. From Nd$_2$O$_3$ rich melts the X-phase forms, which is stable only at high temperatures. An additional field, where the alternative high-temperature phase H solidifies as primary product touches the Nd$_2$O$_3$--Lu$_2$O$_3$ edge of the concentration triangle. From melts close to the composition NdScO$_3$, the P-phase (perovskite) can be crystallized and mixed crystals with second end member NdLuO$_3$ have been grown from the melt. Crystals of this mixed perovskite were grown by the micro-pulling-down and Czochralski methods., Comment: 16 pages, 8 figures, submitted to J. Crystal Growth

Let $A$ and $B$ be $C^*$-algebras with $A\subseteq M(B)$. Exploiting the duality between sober spaces and spatial locales, and the adjunction between restriction and induction for ideals in $A$ and $B$, we identify conditions that allow to define a quasi-orbit space and a quasi-orbit map for $A\subseteq M(B)$. These objects generalise classical notions for group actions. We characterise when the quasi-orbit space is an open quotient of the primitive ideal space of $A$ and when the quasi-orbit map is open and surjective. We apply these results to cross section $C^*$-algebras of Fell bundles over locally compact groups, regular $C^*$-inclusions, tensor products, relative Cuntz--Pimsner algebras, and crossed products for actions of locally compact Hausdorff groupoids and quantum groups., Comment: Locale-theoretical notation changed, an error in a previous version of Lemma 3.10 removed, and a number of small changes implemented

We study conditions that ensure uniqueness theorems of Cuntz-Krieger type for relative Cuntz-Pimsner algebras $\mathcal{O}(J,X)$ associated to a $C^*$-correspondence $X$ over a $C^*$-algebra $A$. We give general sufficient conditions phrased in terms of a multivalued map $\widehat{X}$ acting on the spectrum $\widehat{A}$ of $A$. When $X(J)$ is of Type I we construct a directed graph dual to $X$ and prove a uniqueness theorem using this graph. When $X(J)$ is liminal, we show that topological freeness of this graph is equivalent to the uniqueness property for $\mathcal{O}(J,X)$, as well as to an algebraic condition, which we call $J$-acyclicity of $X$. As an application we improve the Fowler-Raeburn uniqueness theorem for the Toeplitz algebra $\mathcal{T}_X$. We give new simplicity criteria for $\mathcal{O}_X$. We generalize and enhance uniqueness results for relative quiver $C^*$-algebras of Muhly and Tomforde. We also discuss applications to crossed products by endomorphisms., Comment: We have updated the list of references, fixed some typos and made other minor improvements. This is the version that will be published