Mathematical Software (TOMS)


Search Issue
enter search term and/or author name


ACM Transactions on Mathematical Software (TOMS), Volume 37 Issue 3, September 2010

Computing Tutte Polynomials
Gary Haggard, David J. Pearce, Gordon Royle
Article No.: 24
DOI: 10.1145/1824801.1824802

The Tutte polynomial of a graph, also known as the partition function of the q-state Potts model is a 2-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. It contains several other...

A Code Based on the Two-Stage Runge-Kutta Gauss Formula for Second-Order Initial Value Problems
Severiano González-Pinto, Rogel Rojas-Bello
Article No.: 25
DOI: 10.1145/1824801.1824803

A code based on the two-stage Gauss formula (order four) for second-order initial value problems of a special type is developed. This code can be used to obtain a low- to medium-precision integration for a wide range of problems in the class of...

Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants
Pedro Gonnet
Article No.: 26
DOI: 10.1145/1824801.1824804

We present two new adaptive quadrature routines. Both routines differ from previously published algorithms in many aspects, most significantly in how they represent the integrand, how they treat nonnumerical values of the integrand, how they deal...

Adaptive Projection Subspace Dimension for the Thick-Restart Lanczos Method
Ichitaro Yamazaki, Zhaojun Bai, Horst Simon, Lin-Wang Wang, Kesheng Wu
Article No.: 27
DOI: 10.1145/1824801.1824805

The Thick-Restart Lanczos (TRLan) method is an effective method for solving large-scale Hermitian eigenvalue problems. The performance of the method strongly depends on the dimension of the projection subspace used at each restart. In this...

Unified Tables for Exponential and Logarithm Families
Christopher Kumar Anand, Anuroop Sharma
Article No.: 28
DOI: 10.1145/1824801.1824806

Accurate table methods allow for very accurate and efficient evaluation of elementary functions. We present new single-table approaches to logarithm and exponential evaluation, by which we mean that a single table of values works for both...

An Interoperable, Data-Structure-Neutral Component for Mesh Query and Manipulation
Carl Ollivier-Gooch, Lori Diachin, Mark S. Shephard, Timothy Tautges, Jason Kraftcheck, Vitus Leung, Xiaojuan Luo, Mark Miller
Article No.: 29
DOI: 10.1145/1824801.1864430

Much of the effort required to create a new simulation code goes into developing infrastructure for mesh data manipulation, adaptive refinement, design optimization, and so forth. This infrastructure is an obvious target for code reuse, except...

MLD2P4: A Package of Parallel Algebraic Multilevel Domain Decomposition Preconditioners in Fortran 95
Pasqua D’Ambra, Daniela Di Serafino, Salvatore Filippone
Article No.: 30
DOI: 10.1145/1824801.1824808

Domain decomposition ideas have long been an essential tool for the solution of PDEs on parallel computers. In recent years many research efforts have been focused on recursively employing domain decomposition methods to obtain multilevel...

Parallel Colt: A High-Performance Java Library for Scientific Computing and Image Processing
Piotr Wendykier, James G. Nagy
Article No.: 31
DOI: 10.1145/1824801.1824809

Major breakthroughs in chip and software design have been observed for the last nine years. In October 2001, IBM released the world’s first multicore processor: POWER4. Six years later, in February 2007, NVIDIA made a public release of CUDA...

Parallel Solvers for Sylvester-Type Matrix Equations with Applications in Condition Estimation, Part I: Theory and Algorithms
Robert Granat, Bo Kågström
Article No.: 32
DOI: 10.1145/1824801.1824810

Parallel ScaLAPACK-style algorithms for solving eight common standard and generalized Sylvester-type matrix equations and various sign and transposed variants are presented. All algorithms are blocked variants based on the Bartels--Stewart method...

Algorithm 904: The SCASY Library—Parallel Solvers for Sylvester-Type Matrix Equations with Applications in Condition Estimation, Part II
Robert Granat, Bo Kågström
Article No.: 33
DOI: 10.1145/1824801.1824811

We continue our presentation of parallel ScaLAPACK-style algorithms for solving Sylvester-type matrix equations. In Part II, we present SCASY (SCAlable SYlvester solvers), a state-of-the-art HPC software library for solving 44 sign and transpose...

Algorithm 905: SHEPPACK: Modified Shepard Algorithm for Interpolation of Scattered Multivariate Data
William I. Thacker, Jingwei Zhang, Layne T. Watson, Jeffrey B. Birch, Manjula A. Iyer, Michael W. Berry
Article No.: 34
DOI: 10.1145/1824801.1824812

Scattered data interpolation problems arise in many applications. Shepard’s method for constructing a global interpolant by blending local interpolants using local-support weight functions usually creates reasonable approximations. SHEPPACK...

Algorithm 906: elrint3d—A Three-Dimensional Nonadaptive Automatic Cubature Routine Using a Sequence of Embedded Lattice Rules
Tiancheng Li, Ian Robinson
Article No.: 35
DOI: 10.1145/1824801.1824813

A three-dimensional automatic cubature routine, called elrint3d, is described and numerical results are presented that demonstrate its applicability across a wide range of domains and integrand types. The underlying algorithm is based on a...

Algorithm 907: KLU, A Direct Sparse Solver for Circuit Simulation Problems
Timothy A. Davis, Ekanathan Palamadai Natarajan
Article No.: 36
DOI: 10.1145/1824801.1824814

KLU is a software package for solving sparse unsymmetric linear systems of equations that arise in circuit simulation applications. It relies on a permutation to Block Triangular Form (BTF), several methods for finding a fill-reducing ordering...

Algorithm 908: Online Exact Summation of Floating-Point Streams
Yong-Kang Zhu, Wayne B. Hayes
Article No.: 37
DOI: 10.1145/1824801.1824815

We present a novel, online algorithm for exact summation of a stream of floating-point numbers. By “online” we mean that the algorithm needs to see only one input at a time, and can take an arbitrary length input stream of such inputs...