Search ACM DL

Search Issue

enter search term and/or author name

**Systematic Alias Sampling**: An Efficient and Low-Variance Way to Sample from a Discrete Distribution

Ilari Vallivaara, Katja Poikselkä, Pauli Rikula, Juha Röning

Article No.: 18

DOI: 10.1145/2935745

In this article, we combine the Alias method with the concept of systematic sampling, a method commonly used in particle filters for efficient low-variance resampling. The proposed method allows very fast sampling from a discrete distribution:...

**Parallel Memory-Efficient Adaptive Mesh Refinement on Structured Triangular Meshes with Billions of Grid Cells**

Oliver Meister, Kaveh Rahnema, Michael Bader

Article No.: 19

DOI: 10.1145/2947668

We present sam(oa)^{2}, a software package for a dynamically adaptive, parallel solution of 2D partial differential equations on triangular grids created via newest vertex bisection. An element order imposed by the Sierpinski space-filling...

**IEEE754 Precision- k base-β Arithmetic Inherited by Precision-m Base-β Arithmetic for k < m**

Siegfried M. Rump

Article No.: 20

DOI: 10.1145/2785965

Suppose an *m*-digit floating-point arithmetic in base β ≥ 2 following the IEEE754 arithmetic standard is available. We show how a *k*-digit arithmetic with *k* < *m* can be inherited solely using *m*-digit...

**PSelInv—A Distributed Memory Parallel Algorithm for Selected Inversion**: The Symmetric Case

Mathias Jacquelin, Lin Lin, Chao Yang

Article No.: 21

DOI: 10.1145/2786977

We describe an efficient parallel implementation of the selected inversion algorithm for distributed memory computer systems, which we call PSelInv. The PSelInv method computes selected elements of a general sparse matrix *A* that can be...

**GPU-Accelerated Generation of Correctly Rounded Elementary Functions**

Pierre Fortin, Mourad Gouicem, Stef Graillat

Article No.: 22

DOI: 10.1145/2935746

The IEEE 754-2008 standard recommends the correct rounding of some elementary functions. This requires solving the Table Maker’s Dilemma (TMD), which implies a huge amount of CPU computation time. In this article, we consider accelerating...

**An Efficient Representation Format for Fuzzy Intervals Based on Symmetric Membership Functions**

Manuel Marin, David Defour, Federico Milano

Article No.: 23

DOI: 10.1145/2939364

This article addresses the execution cost of arithmetic operations with a focus on fuzzy arithmetic. Thanks to an appropriate representation format for fuzzy intervals, we show that it is possible to halve the number of operations and divide by 2...

**Firedrake**: Automating the Finite Element Method by Composing Abstractions

Florian Rathgeber, David A. Ham, Lawrence Mitchell, Michael Lange, Fabio Luporini, Andrew T. T. Mcrae, Gheorghe-Teodor Bercea, Graham R. Markall, Paul H. J. Kelly

Article No.: 24

DOI: 10.1145/2998441

Firedrake is a new tool for automating the numerical solution of partial differential equations. Firedrake adopts the domain-specific language for the finite element method of the FEniCS project, but with a pure Python runtime-only implementation...

**Algorithm 968**: DISODE45: A Matlab Runge-Kutta Solver for Piecewise Smooth IVPs of Filippov Type

Manuel Calvo, Juan I. Montijano, Luis Rández

Article No.: 25

DOI: 10.1145/2907054

In this article, an adaptive Runge-Kutta code, based on the DOPRI5(4) pair for solving initial value problems (IVPs) for differential systems with piecewise smooth solutions (PWS) is presented and the algorithms used in the code are described. The...

**Algorithm 969**: Computation of the Incomplete Gamma Function for Negative Values of the Argument

Amparo Gil, Diego Ruiz-Antolín, Javier Segura, Nico M. Temme

Article No.: 26

DOI: 10.1145/2972951

An algorithm for computing the incomplete gamma function γ^{*}(*a*, *z*) for real values of the parameter *a* and negative real values of the argument *z* is presented. The algorithm combines the use of series...

**Algorithm 970**: Optimizing the NIST Statistical Test Suite and the Berlekamp-Massey Algorithm

Marek Sýs, Zdeněk Říha, Vashek Matyáš

Article No.: 27

DOI: 10.1145/2988228

The NIST Statistical Test Suite (NIST STS) is one of the most popular tools for the analysis of randomness. This test battery is widely used, but its implementation is quite inefficient. A complete randomness analysis using the NIST STS can take...

**Algorithm 971**: An Implementation of a Randomized Algorithm for Principal Component Analysis

Huamin Li, George C. Linderman, Arthur Szlam, Kelly P. Stanton, Yuval Kluger, Mark Tygert

Article No.: 28

DOI: 10.1145/3004053

Recent years have witnessed intense development of randomized methods for low-rank approximation. These methods target principal component analysis and the calculation of truncated singular value decompositions. The present article presents an...

**Algorithm 972**: jMarkov: An Integrated Framework for Markov Chain Modeling

Juan F. Pérez, Daniel F. Silva, Julio C. Góez, Andrés Sarmiento, Andrés Sarmiento-Romero, Raha Akhavan-Tabatabaei, Germán Riaño

Article No.: 29

DOI: 10.1145/3009968

Markov chains (MC) are a powerful tool for modeling complex stochastic systems. Whereas a number of tools exist for *solving* different types of MC models, the first step in MC modeling is to define the model parameters. This step is,...