ACM DL

Mathematical Software (TOMS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Mathematical Software (TOMS), Volume 32 Issue 2, June 2006

Accumulating Householder transformations, revisited
Thierry Joffrain, Tze Meng Low, Enrique S. Quintana-Ortí, Robert van de Geijn, Field G. Van Zee
Pages: 169-179
DOI: 10.1145/1141885.1141886
A theorem related to the accumulation of Householder transformations into a single orthogonal transformation known as the compact WY transform is presented. It provides a simple characterization of the computation of this transformation and suggests...

Improving the performance of reduction to Hessenberg form
Gregorio Quintana-Ortí, Robert van de Geijn
Pages: 180-194
DOI: 10.1145/1141885.1141887
In this article, a modification of the blocked algorithm for reduction to Hessenberg form is presented that improves performance by shifting more computation from less efficient matrix-vector operations to highly efficient matrix-matrix operations....

An efficient overloaded implementation of forward mode automatic differentiation in MATLAB
Shaun A. Forth
Pages: 195-222
DOI: 10.1145/1141885.1141888
The Mad package described here facilitates the evaluation of first derivatives of multidimensional functions that are defined by computer codes written in MATLAB. The underlying algorithm is the well-known forward mode of automatic differentiation...

Optimizing FIAT with level 3 BLAS
Robert C. Kirby
Pages: 223-235
DOI: 10.1145/1141885.1141889
Our previous work on FIAT (Finite Element Automatic Tabulator) developed a “computational representation theory ” that allowed us to construct arbitrary order instances of a wide range of finite elements, many of which are infrequently...

Computing machine-efficient polynomial approximations
Nicolas Brisebarre, Jean-Michel Muller, Arnaud Tisserand
Pages: 236-256
DOI: 10.1145/1141885.1141890
Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly...

Sequential reservoir sampling with a nonuniform distribution
M. Kolonko, D. Wäsch
Pages: 257-273
DOI: 10.1145/1141885.1141891
We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of...

A Matlab package for automatically generating Runge-Kutta trees, order conditions, and truncation error coefficients
Frank Cameron
Pages: 274-298
DOI: 10.1145/1141885.1141892
In designing parts of Runge-Kutta methods, order conditions and truncation error coefficients (TECs) are needed. Order conditions and TECs are typically presented as a set of trees combined with rules for producing algebraic expressions from the...

FILIB++, a fast interval library supporting containment computations
Michael Lerch, German Tischler, Jürgen Wolff Von Gudenberg, Werner Hofschuster, Walter Krämer
Pages: 299-324
DOI: 10.1145/1141885.1141893
filib++ is an extension of the interval library filib originally developed at the University of Karlsruhe. The most important aim of filib is the fast computation of guaranteed bounds for interval versions of a comprehensive set of...

Error bounds from extra-precise iterative refinement
James Demmel, Yozo Hida, William Kahan, Xiaoye S. Li, Sonil Mukherjee, E. Jason Riedy
Pages: 325-351
DOI: 10.1145/1141885.1141894
We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to...

Algorithm 854: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II
Peter Benner, Daniel Kressner
Pages: 352-373
DOI: 10.1145/1141885.1141895
This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal symplectic decompositions, implying numerical backward...