Mathematical Software (TOMS)


Search Issue
enter search term and/or author name


ACM Transactions on Mathematical Software (TOMS), Volume 43 Issue 3, January 2017

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,...